Comments 14
Круто. Внятно и толково изложили материал, знать и разбираться в котором должен в идеале уметь любой программист.
0
Хорошо написано!
0
Еще можно указать, что если на входе у алгоритма рациональные числа, то сравнить результат с нулем можно с помощью многомодульной арифметики — посчитать значение в конечных полях по нескольким небольшим простым модулям (5-10 чисел в окрестности 32749 подойдут), и если каждый результат оказался либо равным нулю, либо неопределенным (из-за деления на 0), то наши точки наверняка лежат на прямой, и интервальная арифметика ничего не даст. Если же результат отличен от нуля, можно запускать интервальную, а потом и длинную арифметику. Многомодульная арифметика работает гораздо быстрее, чем длинная рациональная. К сожалению, определять с ее помощью знак числа напрямую не очень просто, обычно это делают, когда известно, что результат — целое число (а промежуточные значения рациональны). Например, при вычислении определителя целочисленных матриц.
+2
В общем случае проверка на равенство с нулем ничего не дает: вероятность того, что три произвольные точки лежат на одной прямой, ничтожна. А как посчитать знак выражения в модульной арифметике, я пока представить не могу.
Вообще, смысл статьи как раз в том, что подавляющее большинство ответов будут определяться floating-point арифметикой, а до последнего шага (который вовсе не обязательно считать в рациональной арифметике, есть множество относительно быстрых алгоритмов) дойдет несколько входов из сотен миллионов. То есть среднее время будет очень близко к минимальному.
Может, я неверно понял ваш комментарий?
Вообще, смысл статьи как раз в том, что подавляющее большинство ответов будут определяться floating-point арифметикой, а до последнего шага (который вовсе не обязательно считать в рациональной арифметике, есть множество относительно быстрых алгоритмов) дойдет несколько входов из сотен миллионов. То есть среднее время будет очень близко к минимальному.
Может, я неверно понял ваш комментарий?
0
Нет, все правильно. Но вероятность того, что точки окажутся на одной прямой, или в одной плоскости, в некоторых случаях огромна. Например, если решается задача, связанная с разбиениями пространства на многогранники. Там постоянно возникают вопросы: образуют ли такие-то точки одну грань, проходит ли очередная плоскость через уже построенную вершину, являются ли два многогранника соседними (хранить эту информацию в виде какого-нибудь мультиграфа намного сложнее, чем держать просто набор координат вершин и плоскостей). Чаще всего хватает правильного выбора эпсилона, но в ответственных случаях могут потребоваться точные ответы.
0
Часть картинок умерло. Обновите статью, пожалуйста.
0
Sign up to leave a comment.
Точное вычисление геометрических предикатов