Pull to refresh

Comments 14

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


Это относится не только к числам с плавающей точкой.
Еще можно указать, что если на входе у алгоритма рациональные числа, то сравнить результат с нулем можно с помощью многомодульной арифметики — посчитать значение в конечных полях по нескольким небольшим простым модулям (5-10 чисел в окрестности 32749 подойдут), и если каждый результат оказался либо равным нулю, либо неопределенным (из-за деления на 0), то наши точки наверняка лежат на прямой, и интервальная арифметика ничего не даст. Если же результат отличен от нуля, можно запускать интервальную, а потом и длинную арифметику. Многомодульная арифметика работает гораздо быстрее, чем длинная рациональная. К сожалению, определять с ее помощью знак числа напрямую не очень просто, обычно это делают, когда известно, что результат — целое число (а промежуточные значения рациональны). Например, при вычислении определителя целочисленных матриц.
В общем случае проверка на равенство с нулем ничего не дает: вероятность того, что три произвольные точки лежат на одной прямой, ничтожна. А как посчитать знак выражения в модульной арифметике, я пока представить не могу.

Вообще, смысл статьи как раз в том, что подавляющее большинство ответов будут определяться floating-point арифметикой, а до последнего шага (который вовсе не обязательно считать в рациональной арифметике, есть множество относительно быстрых алгоритмов) дойдет несколько входов из сотен миллионов. То есть среднее время будет очень близко к минимальному.

Может, я неверно понял ваш комментарий?
Нет, все правильно. Но вероятность того, что точки окажутся на одной прямой, или в одной плоскости, в некоторых случаях огромна. Например, если решается задача, связанная с разбиениями пространства на многогранники. Там постоянно возникают вопросы: образуют ли такие-то точки одну грань, проходит ли очередная плоскость через уже построенную вершину, являются ли два многогранника соседними (хранить эту информацию в виде какого-нибудь мультиграфа намного сложнее, чем держать просто набор координат вершин и плоскостей). Чаще всего хватает правильного выбора эпсилона, но в ответственных случаях могут потребоваться точные ответы.
Я понял, спасибо. Дам ссылку в статье на ваш комментарий.
Часть картинок умерло. Обновите статью, пожалуйста.
Не вижу. Может, дело в том, что к статье давно не обращались и latex-renderer не успел сгенерировать формулы? Сейчас, вроде бы, всё хорошо.
Хм. Похоже, что проблема в мобильном приложении. В браузере нормально. Сейчас напишу баг-репорт.
А всё равно, может быть сделать картинки?
Sign up to leave a comment.

Articles