Даже математики ошибаются / forpes.ru

Главная
Даже математики ошибаются

Даже математики ошибаются

09.08.2024 08:46

slepyshkov 2 5900 Источник

Мы знаем, что математика — наука точная. Значит ли это, что GeoGebra — программное обеспечение для интерактивного изучения математики — столь же точно? Проанализируем же исходный код проекта с помощью PVS-Studio!

Введение

Помните изучение программирования в университете? Умножение векторов и матриц, расчёт полиномов, интерполяция, экстраполяция... Что насчёт того, чтобы посмотреть применение этих страшных формул в настоящем проекте, а не в очередной лабораторной работе? А что насчёт поиска проблем в такой кодовой базе? Предлагаю запустить PVS-Studio и открыть учебники математики. Зачем учебники? Сейчас покажу.

Математические трудности

Одна из основных трудностей при изучении исходного кода программ данного калибра — попытка понять, что происходит. При просмотре отчёта анализатора часто возникали вопросы о действительности наличия или отсутствия проблем в части срабатываний.

Рассмотрим, например, следующий фрагмент:

@Override
public void compute() {
  ....
  if (cumulative != null && cumulative.getBoolean()) {
    ....
  } else {
    ....
    branchAtoMode = fv.wrap().subtract(a).multiplyR(2)
      .divide(bEn.subtract(a).multiply(modeEn.subtract(a)));
    branchModeToB = fv.wrap().subtract(b).multiplyR(2)                
      .divide(bEn.subtract(a).multiply(modeEn.subtract(b)));
      rightBranch = new MyDouble(kernel, 0);
  }
  ....
}

Получаем следующее предупреждение PVS-Studio:

V6072 Two similar code fragments were found. Perhaps, this is a typo and 'b' variable should be used instead of 'a'. AlgoTriangularDF.java 145, AlgoTriangularDF.java 146, AlgoTriangularDF.java 147, AlgoTriangularDF.java 148

Действительно ли это опечатка? После небольшого исследования и найденной необходимой формулы можем спокойно заявить — всё написано верно.

Объяснение фрагмента.

Во фрагменте рассчитывается треугольное распределение (triangular distribution), а именно функция плотности вероятности (probability density function, PDF) для этого распределения. Находим формулу:

Теперь по коду:

fv — function variable (переменная функции). wrap возвращает wrapper, после чего проводятся уже необходимые математические операции. Из интересного — наличие методов multiply и multiplyR. R во втором методе означает right и, фактически, меняет местами операнды (поскольку не всякая операция умножения коммутативна).

В результате в branchAToMode записывается результат вычисления второго выражения, а в branchModeToB — четвёртого.

Также замечаем, что в branchModeToB поменяли знаки в числителе и знаменателе, получив следующее выражение:

Значение выражения, безусловно, не поменялось.

Потому для разбора некоторых полученных предупреждений пришлось изучать математический материал. И не столь тяжело убедиться, действительно ли произошла ошибка при написании кода, сколь понять, что должно было быть на её месте.

Ошибки

Потерянный сегмент

Начинаем с простого. Посмотрим на следующий метод:

private void updateSide(int index, int newBottomPointsLength) {
  ....
  GeoSegmentND[] s = new GeoSegmentND[4];
  GeoSegmentND segmentBottom = outputSegmentsBottom.getElement(index);
  s[0] = segmentBottom;
  s[1] = segmentSide1;
  s[2] = segmentSide2;
  s[2] = segmentSide3;
  polygon.setSegments(s);
  polygon.calcArea();
}

Обнаруживаем, что кто-то забыл заменить s[2] на s[3]. Эффект последней строки во всей своей красе. Легендарная и уж слишком распространённая ошибка copy-paste. В результате получаем, что четвёртый элемент массива отсутствует и является null!

V6033 An item with the same key '2' has already been changed. AlgoPolyhedronNetPrism.java 376, AlgoPolyhedronNetPrism.java 377

Что там по значениям?

А теперь попробуйте найти проблему в следующем фрагменте:

static synchronized HashMap<String, String> getGeogebraMap() {
  ....
  geogebraMap.put("−", "-");
  geogebraMap.put("⊥", "# ");
  geogebraMap.put("∼", "~ ");
  geogebraMap.put("′", "# ");
  geogebraMap.put("≤", Unicode.LESS_EQUAL + "");
  geogebraMap.put("&ge;", Unicode.GREATER_EQUAL + "");
  geogebraMap.put("&infin;", Unicode.INFINITY + "");
  ....
  geogebraMap.put("∏", "# ");
  geogebraMap.put("&Product;", "# ");
  geogebraMap.put("〉", "# ");
  geogebraMap.put("&rangle;", "# ");
  geogebraMap.put("&rarr;", "# ");
  geogebraMap.put("&rArr;", "# ");
  geogebraMap.put("&RightAngleBracket;", "# ");
  geogebraMap.put("&rightarrow;", "# ");
  geogebraMap.put("&Rightarrow;", "# ");
  geogebraMap.put("&RightArrow;", "# ");
  geogebraMap.put("&sdot;", "* ");
  geogebraMap.put("∼", "# ");
  geogebraMap.put("∝", "# ");
  geogebraMap.put("&Proportional;", "# ");
  geogebraMap.put("&propto;", "# ");
  geogebraMap.put("⊂", "# ");
  ....
  return geogebraMap;
}

Какой великолепный вид! Читать это — сплошное удовольствие, а это лишь малая часть, ведь данный метод начинается на строке 66 и заканчивается на 404. Мы также получаем целых 50 срабатываний диагностики V6033. Быстро посмотрим одно из этих предупреждений:

V6033 An item with the same key '"∼"' has already been added. MathMLParser.java 229, MathMLParser.java 355

Уберём лишние фрагменты и посмотрим конкретно на выражения из предупреждения:

geogebraMap.put("&sim;", "~ ");
....
geogebraMap.put("&sim;", "# ");

Интересно. Что насчёт расстояния между этими вызовами методов? 126 строк. Успехов обнаружить такое вручную!

Большая часть — дубликаты и по ключу, и по значению, но несколько случаев аналогичны примеру сверху, где значение переписывается на иное. Какое из двух должно использоваться?

Окружности и эллипсы

@Override
protected boolean updateForItSelf() {
  ....
  if (conic.getType() == GeoConicNDConstants.CONIC_SINGLE_POINT) {
    ....
  } else {
    if (visible != Visible.FRUSTUM_INSIDE) {
      ....
      switch (conic.getType()) {
        case GeoConicNDConstants.CONIC_CIRCLE:
          updateEllipse(brush);                     // <=
          break;
        case GeoConicNDConstants.CONIC_ELLIPSE:
          updateEllipse(brush);                     // <=
          break;
        case GeoConicNDConstants.CONIC_HYPERBOLA:
          updateHyperbola(brush);
          break;
        case GeoConicNDConstants.CONIC_PARABOLA:
          updateParabola(brush);
          break;
        case GeoConicNDConstants.CONIC_DOUBLE_LINE:
          createTmpCoordsIfNeeded();
          brush.segment(tmpCoords1.setAdd3(m, tmpCoords1.setMul3(d, minmax[0])),
              tmpCoords2.setAdd3(m, tmpCoords2.setMul3(d, minmax[1])));
          break;
        case GeoConicNDConstants.CONIC_INTERSECTING_LINES:
        case GeoConicNDConstants.CONIC_PARALLEL_LINES:
          updateLines(brush);
          break;
        default:
          break;
      }
    }
  }
}

Что для эллипса, что для окружности вызывается метод для эллипса. Можно, конечно, предположить, что это не ошибочно ввиду того, что окружность — это эллипс. Однако в этом классе также присутствует метод updateCircle. Так как должно быть? Попробуем зайти чуть глубже.

Всё происходит в классе DrawConic3D. Методы для эллипса и для окружности:

protected void updateCircle(PlotterBrush brush) {
  if (visible == Visible.CENTER_OUTSIDE) {
    longitude = brush.calcArcLongitudesNeeded(e1, alpha,
          getView3D().getScale());
    brush.arc(m, ev1, ev2, e1, beta - alpha, 2 * alpha, longitude);
  } else {
    longitude = brush.calcArcLongitudesNeeded(e1, Math.PI,
          getView3D().getScale());
    brush.circle(m, ev1, ev2, e1, longitude);
  }
}
protected void updateEllipse(PlotterBrush brush) {
  if (visible == Visible.CENTER_OUTSIDE) {
    brush.arcEllipse(m, ev1, ev2, e1, e2, beta - alpha, 2 * alpha);
  } else {
    brush.arcEllipse(m, ev1, ev2, e1, e2, 0, 2 * Math.PI);
  }
}

Делаем выводы, и они... придают не так много уверенности. Да, тела методов разные, но, в общем и целом, ничего здесь не кричит, что мы рискуем образованием на экране неприемлемых геометрических объектов в случае неверного вызова метода.

Может есть другие улики? Целая одна! Метод updateCircle ни разу не используется в проекте. В то же время *updateEllipse *используется 4 раза: два раза в первом фрагменте, и ещё два — уже в классе-наследнике класса DrawConic3D – DrawConicSection3D:

@Override
protected void updateCircle(PlotterBrush brush) {
  updateEllipse(brush);
}

@Override
protected void updateEllipse(PlotterBrush brush) {
  // ....
  } else {
    super.updateEllipse(brush);
  }
}

Данный updateCircle также не используется. Что оставляет updateEllipse лишь с вызовом в собственном переопределении и в updateForItSelf — во фрагменте, который мы и рассматривали изначально. В виде схемы структуру можно представить так:

С одной стороны, кажется, что разработчики и правда хотели использовать универсальный метод отрисовки окружности в виде updateEllipse. С другой стороны, странно, что в DrawConicSection3D есть метод updateCircle, вызывающий updateEllipse. Но сам updateCircle никогда не вызовется.

Сложно предположить, как должен выглядеть исправленный код, если ошибка в нём действительно присутствует. Например, если в DrawConicSection3D updateCircle должен вызывать updateEllipse, а в DrawConic3D нужен более оптимизированный алгоритм для круга, то исправленная схема может выглядеть так:

По итогу есть ощущение, что updateCircle был однажды написан и с тех пор потерян, а мы, вполне вероятно, нашли его предполагаемое место жительства. Либо это следы оставшегося рефакторинга и о бездомном методе забыли. В любом случае, стоит сделать этот код понятнее, чтобы такого количества вопросов не возникало.

А у нас они возникли благодаря одному из предупреждений PVS-Studio. Оно, кстати, следующее:

V6067 Two or more case-branches perform the same actions. DrawConic3D.java 212, DrawConic3D.java 215

Порядок ненайденного объекта

private void updateOrdering(GeoElement geo, ObjectMovement movement) {
  ....
  switch (movement) {
    ....
    case FRONT:
      ....
      if (index == firstIndex) {
        if (index != 0) { 
          geo.setOrdering(orderingDepthMidpoint(index));
        }
        else { 
          geo.setOrdering(drawingOrder.get(index - 1).getOrdering() - 1);
        }
      }
    ....
  }
  ....
}

Получаем следующее предупреждение:

V6025 Index 'index - 1' is out of bounds. LayerManager.java 393

Выходит любопытно, ведь в блоке else переменная index гарантированно приобретает значение 0, а, следовательно, мы получаем -1 как аргумент для метода get. Результат? Ловим IndexOutOfBoundsException.

Треугольники

@Override
protected int getGLType(Type type) {
  switch (type) {
  case TRIANGLE_STRIP:
    return GL.GL_TRIANGLE_STRIP;
  case TRIANGLE_FAN:
    return GL.GL_TRIANGLE_STRIP;     // <=
  case TRIANGLES:
    return GL.GL_TRIANGLES;
  case LINE_LOOP:
    return GL.GL_LINE_LOOP;
  case LINE_STRIP:
    return GL.GL_LINE_STRIP;
  }

  return 0;
}

Код новый, а ошибка уже знакомая. Вполне очевидно, что вместо GL.GL_TRIANGLE_STRIP должен быть GL.GL_TRIANGLE_FAN. Методы может чем-то и похожие, но результат всё же дают разный. Об этом можно прочитать в спойлере.

V6067 Two or more case-branches perform the same actions. RendererImplShadersD.java 243, RendererImplShadersD.java 245

Для любопытных про Triangle Strip и Triangle Fan.

Для описания набора треугольников требуется сохранять координаты трёх вершин каждого из них. Таким образом, при наличии N треугольников потребуется 3N сохранённых вершин. Если треугольники соединены (что крайне актуально при описании многогранных объектов с помощью полигональной сетки), то можно использовать Triangle Strip или Triangle Fan, которые позволяют описать такой набор треугольников, используя N + 2 вершин.

Забегая вперёд, отметим, что Triangle Fan был удалён в Direct3D 10. В OpenGL 4.6 этот примитив всё ещё существует.

Triangle Fan использует одну общую — центральную — вершину, а также последнюю и новую. Например, посмотрим на следующий пример:

Для его описания потребуется запись (A, B, C, D, E, F, G). Треугольников 5, вершин для записи — 7.

Triangle Strip же использует две последние вершины и новую. Например, этой же последовательностью вершин можно получить следующее изображение:

Потому использование неверного примитива приведёт к радикально разным результатам.

Перетирая значения

public static void addToJsObject(JsPropertyMap<Object> jsMap, Map<String, Object> map) {
  for (Entry<String, Object> entry : map.entrySet()) {
    Object object = entry.getValue();
      if (object instanceof Integer) {
        jsMap.set(entry.getKey(), unbox((Integer) object));
      } if (object instanceof String[]) {                          // <=
        JsArray<String> clean = JsArray.of();
        for (String s: (String[]) object) {
          clean.push(s);
        }
        jsMap.set(entry.getKey(), clean);
    } else {                                                       // <=
      jsMap.set(entry.getKey(), object);                           // <=
    }
  }
}

Если не всматриваться, то проблему можно сразу и не увидеть. Однако можем ускориться и просто посмотреть на сообщение анализатора:

V6086 Suspicious code formatting. 'else' keyword is probably missing. ScriptManagerW.java 209

Вот и вышли на более интересную ошибку. Проверка* object instanceof String[]* проводится вне зависимости от результата проверки object instanceof Integer, что, возможно, и не так страшно, однако здесь также есть блок else, который будет выполняться после провалившейся проверки на String[], из-за чего в jsMap значение по ключу entry.getKey() будет переписано, если object был Integer.

Можем посмотреть на аналогичную ситуацию, хотя и потенциальные последствия понять несколько труднее:

public void bkspCharacter(EditorState editorState) {
  int currentOffset = editorState.getCurrentOffsetOrSelection();
  if (currentOffset > 0) {
    MathComponent prev = editorState.getCurrentField()
        .getArgument(currentOffset - 1);
    if (prev instanceof MathArray) {
      MathArray parent = (MathArray) prev;
      extendBrackets(parent, editorState);
    } if (prev instanceof MathFunction) {                          // <=
      bkspLastFunctionArg((MathFunction) prev, editorState);
    } else {                                                       // <=
      deleteSingleArg(editorState);
    }
  } else {
    RemoveContainer.withBackspace(editorState);
  }
}

V6086 Suspicious code formatting. 'else' keyword is probably missing. InputController.java 854

Практически верно

Часто ли приходится писать множество однотипных проверок? Легко ли в них опечататься? Посмотрим на примере следующего метода:

public boolean contains(BoundingBox other) {
  return !(isNull() || other.isNull()) && other.minx >= minx
      && other.maxy <= maxx && other.miny >= miny
      && other.maxy <= maxy;
}

V6045 Possible misprint in expression 'other.maxy <= maxx'. BoundingBox.java 139

Находим опечатку — исправляем. Ответ однозначен: должно быть other.maxx <= maxx.

Перепутанные числа

public PointDt[] calcVoronoiCell(TriangleDt triangle, PointDt p) {
  ....
  // find the neighbor triangle
  if (!halfplane.next_12().isHalfplane()) {
    neighbor = halfplane.next_12();
  } else if (!halfplane.next_23().isHalfplane()) {
    neighbor = halfplane.next_23();
  } else if (!halfplane.next_23().isHalfplane()) { // <=
    neighbor = halfplane.next_31();
  } else {
    Log.error("problem in Delaunay_Triangulation");
    // TODO fix added by GeoGebra
    // should we do something else?
    return null;
  }
  ....
}

Смотрим предупреждение:

V6003 The use of 'if (A) {...} else if (A) {...}' pattern was detected. There is a probability of logical error presence. DelaunayTriangulation.java 678, DelaunayTriangulation.java 680

Не нужно даже разбираться, что происходит с полуплоскостями, ведь очевидно, что должна быть проверка !halfplane.next_31().isHalfplane().

Не та операция

public static ExpressionNode get(
    ExpressionValue left, ExpressionValue right, 
    Operation operation, FunctionVariable fv, 
    Kernel kernel0
) {
  ....
  switch (operation) {
    ....
    case VEC_FUNCTION:
      break;
    case ZETA:
      break;
    case DIRAC:
      return new ExpressionNode(kernel0, left, Operation.DIRAC, fv);
    case HEAVISIDE:
      return new ExpressionNode(kernel0, left, Operation.DIRAC, fv);
    default:
      break;
  }
  ....
}

Вероятно, вместо Operation.DIRAC во втором случае должно быть Operation.HEAVISIDE. Или нет? Данный метод вызывается для получения производной. Некоторое время поиска информации и с HEAVISIDE получилось разобраться: использование Operation.DIRAC для него верно. Что насчёт производной от самого Dirac? Вот это понять уже оказалось не так просто. Возможно, следует довериться разработчикам и подавить срабатывание. Хотя оставить какой-нибудь пояснительный комментарий было бы неплохо, что, к слову, и было сделано в некоторых других случаях:

case FACTORIAL:
  // x! -> psi(x+1) * x!
  return new ExpressionNode(kernel0, left.wrap().plus(1),
      Operation.PSI, null)
          .multiply(new ExpressionNode(kernel0, left,
              Operation.FACTORIAL, null))
          .multiply(left.derivative(fv, kernel0));

case GAMMA:
  // gamma(x) -> gamma(x) psi(x)
  return new ExpressionNode(kernel0, left, Operation.PSI, null)
      .multiply(new ExpressionNode(kernel0, left, Operation.GAMMA,
          null))
      .multiply(left.derivative(fv, kernel0));

А провести такое исследование нас замотивировало сообщение уже полюбившейся диагностики V6067:

V6067 Two or more case-branches perform the same actions. Derivative.java 442, Derivative.java 444

Выходит интересный прецедент, так как с одной стороны мы столкнулись с потенциально ложным срабатыванием анализатора. С другой же, его пользу нельзя исключать в любом случае, поскольку не только это часто действительно бывает ошибка, но и вне зависимости от результатов такой код следует проверять глазами и либо исправлять ошибку, либо оставлять поясняющие комментарии, – тогда срабатывание можно просто подавить.

Вектор или точка?

private static GeoElement doGetTemplate(Construction cons,
    GeoClass listElement) {
  switch (listElement) {
  case POINT:
    return new GeoPoint(cons);
  case POINT3D:
    return (GeoElement) cons.getKernel().getGeoFactory().newPoint(3, cons);
  case VECTOR:
    return new GeoVector(cons);
  case VECTOR3D:
    return (GeoElement) cons.getKernel().getGeoFactory().newPoint(3, cons);
  }
  return new GeoPoint(cons);
}

Предупреждение угадать несложно:

V6067 Two or more case-branches perform the same actions. PointNDFold.java 38, PointNDFold.java 43

Вместо cons.getKernel().getGeoFactory().newPoint(3, cons) во втором случае возможно предполагалось использование cons.getKernel().getGeoFactory().newVector(3, cons). Для повышения уверенности необходимо вновь залезть глубже. Что же, ныряем.

*getGeoFactory() *возвращает GeoFactory, находим методы *newPoint *и newVector:

public GeoPointND newPoint(int dimension, Construction cons) {
  return new GeoPoint(cons);
}
public GeoVectorND newVector(int dimension, Construction cons) {
  return new GeoVector(cons);
}

Выглядит странно. Аргумент dimension вовсе не используется. Что здесь происходит? Конечно же наследование! Находим класс-наследник GeoFactory3D и смотрим, что происходит в нём.

@Override
public GeoVectorND newVector(int dimension, Construction cons) {
  if (dimension == 3) {
    return new GeoVector3D(cons);
  }
  return new GeoVector(cons);
}
@Override
public GeoPointND newPoint(int dimension, Construction cons) {
  return dimension == 3 ? new GeoPoint3D(cons) : new GeoPoint(cons);
}

Превосходно, теперь во всей красе наблюдается создание четырёх разных объектов. Возвращаемся к фрагменту с возможной ошибкой. Для POINT и POINT3D создаются соответствующие объекты классов GeoPoint и GeoPoint3D. Для VECTOR создаётся GeoVector, но GeoVector3D остаётся забытым и плачет в углу.

Конечно, использование фабрики в двух случаях и прямой вызов конструкторов в оставшихся двух выглядят крайне странно. Остатки рефакторинга или некое временное решение, что закрепится до конца существования Вселенной? Во всяком случае, думаю, что если ответственность за создание объектов была передана другому классу, то необходимо эту ответственность отдавать до конца.

Не досчитываемся квадриллионных

@Override
final public void update() {
  ....
  switch (angle.getAngleStyle()) {
    ....
    case EuclidianStyleConstants.RIGHT_ANGLE_STYLE_L:
      // Belgian offset |_
      if (square == null) {
        square = AwtFactory.getPrototype().newGeneralPath();
      } else {
        square.reset();
      }
      length = arcSize * 0.7071067811865;                   // <=
      double offset = length * 0.4;
      square.moveTo(
          coords[0] + length * Math.cos(angSt)
              + offset * Math.cos(angSt)
              + offset * Math.cos(angSt + Kernel.PI_HALF),
          coords[1]
              - length * Math.sin(angSt)
                  * view.getScaleRatio()
              - offset * Math.sin(angSt)
              - offset * Math.sin(angSt + Kernel.PI_HALF));
      ....
      break;
    }
}

Где предупреждение? Да вот же оно:

V6107 The constant 0.7071067811865 is being utilized. The resulting value could be inaccurate. Consider using Math.sqrt(0.5). DrawAngle.java 303

Всего обнаружено 4 таких фрагмента. Более точное значение: 0.7071067811865476 — попробуйте заучить. Последние три числа опущены. Критично ли? Точности скорее всего достаточно, однако использование преопределённых констант или Math.sqrt(0.5) — как для этого случая — не только поможет в восстановлении утерянных чисел, но и исключит риск опечатки, равно как и заметно увеличит читаемость кода. Возможно, что при виде 0.707... кто-то сразу понимает, что это за магическое число такое, но согласитесь, что иногда можно снизить концентрацию магии в пользу читаемости кода.

Заключение

Небольшое математическое приключение закончилось. Как мы можем заметить, даже после познания многих трудностей геометрии простые ошибки при написании кода не исключаются! Хорошо, если код написан недавно, и программист может всё ещё удерживать в памяти свои изначальные намерения. Тогда результат разбора таких проблем становится очевидным, а вот спустя долгое время понять необходимость исправлений уже не так просто.

По этой причине крайне эффективно использовать анализатор непосредственно при написании кода, а не осуществлять единовременные запуски время от времени, подобно тому, как сделал я для анализа этого проекта. Особенно, когда воспользоваться анализатором PVS-Studio можно уже сегодня.

Другие наши публикации на близкую тематику

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Evgenii Slepyshkov. Even great mathematicians make mistakes.

Комментарии (2)

Ababaj
11.08.2024 07:35
#27151258
А причем тут математики?

Maccimo
11.08.2024 07:35
#27152120
А вы сообщили разработчикам? А патч отправили? ;)

А теперь попробуйте найти проблему в следующем фрагменте:

Вижу проблему в редакторе Хабрахабра.
Он часть HTML Entities заменил на символы, хотя в коде этого делать не должен.

V6107 The constant 0.7071067811865 is being utilized. The resulting value could be inaccurate. Consider using Math.sqrt(0.5). DrawAngle.java 303

Почему именно квадратный корень?
Число похоже на что-то из таблиц Брадиса, да и контекст шепчет, что логичнее предлагать какой-нибудь синус 45 градусов.

Было бы интересно узнать про то, как работают эвристики, предлагающие выражения на замену.
Возможно даже отдельной статьёй.