Калькулятор должен показывать результат математического выражения, которое вы ввели, и это намного, намного сложнее, чем кажется. То, что я собираюсь вам рассказать, — это величайшая история о разработке приложения-калькулятора. Взгляните на калькулятор iOS. Что-нибудь заметили? Он показывает неверный результат. (10^100) + 1 − (10^100) равно 0, а не 1. В Android всё правильно. И история о том, как это произошло, совершенно безумна.

Google нанял Ханса-Дж. Боэма, известного как «сборщик мусора Боэма». Им нужен был элитный программист, чтобы исправить ошибки в сборке мусора и параллельном программировании. Он возглавил работу по определению семантики общих переменных C++. Но затем ему дали невыполнимую задачу: написать приложение-калькулятор.

Даже для него это, должно быть, было непросто. Цель приложения-калькулятора — давать вам правильные ответы. Числа с плавающей запятой неточны — они не могут представлять 0,3 или 10^100. Это означает, что калькулятор, основанный на числах с плавающей запятой, подобен дому, построенному на песке.

Это стоит повторить: чтобы давать правильные ответы на математические выражения, калькулятор должен представлять числа. И почти все числа не могут быть представлены в формате IEEE с плавающей запятой. Даже простые операции с числами с плавающей запятой требуют тщательного обдумывания для получения точного ответа.
Например, алгоритм суммирования Кэхана значительно уменьшает численную погрешность при сложении последовательности чисел с плавающей запятой конечной точности, по сравнению с обычным (наивным) подходом. Алгоритм работает за счет того, что поддерживает отдельную "бегущую компенсацию" (running compensation) - переменную, которая накапливает маленькие ошибки. Это фактически позволяет увеличить точность суммы на величину точности компенсационной переменной.
Первое решение: большие числа
Некоторых проблем можно избежать, если использовать большие числа. Большинство числовых типов всегда занимают 2 или 4 байта. Но не большие числа. Это целые числа без ограничений. Они занимают столько памяти, сколько нужно. Это решает проблему с примером (10^100) + 1 - (10^100). Но большие числа — это целые числа. А как насчёт дробей?

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

Математика — это гораздо больше, чем дроби. А как насчёт π или √2? Калькулятор, основанный на дробях произвольной точности, всё равно не сможет вычислить окружность круга, поскольку π нельзя выразить в виде дроби. Если ваш калькулятор не справляется с математикой 9-го класса, то зачем он нужен?

Алгебраическая арифметика
Алгебраическая арифметика приблизила бы его к цели. Забудьте о представлении чисел в виде числителей и знаменателей. Вы можете представить их в виде полиномиального уравнения, которому они удовлетворяют. Для √2 это будет x² - 2 = 0. (Плюс вы бы запомнили, что вам нужен положительный корень.)

Теперь математические операции реализовать немного сложнее:
-
для сложения вы создаёте новый многочлен, корнем которого является сумма исходных многочленов
-
для умножения вы используете композицию многочленов и результирующие многочлены
Угадайте, что? Этого всё равно недостаточно для Бёма. Это работает только для алгебраических чисел. Но не даёт нам π.
Конструктивные действительные числа
Так что Бёму ничего не оставалось, кроме как углубиться в тему. Пришло время взяться за дело всерьёз. Мы начали с целых чисел (бигнум), перешли к рациональным числам, затем к алгебраическим числам. Что дальше? Конструктивные вещественные числа (строго говоря, мы рассматриваем конструктивные способы построения вещественных чисел).

Поэтому Бём начал изучать «рекурсивную вещественную арифметику» (RRA). Если у вас есть выражение и вы знаете, насколько точным должен быть ответ, RRA даст вам ответ с точностью не ниже заданной.
Конструктивные вещественные числа — это числа, которые вы можете вычислять всё точнее и точнее. Вы никогда не сможете назвать мне все десятичные дроби числа π. Но если я попрошу вас назвать рациональное число в пределах 0,01 от числа π, вы можете назвать мне 3,14. Число π находится в пределах 0,01 от числа 3,14, так что это правильный ответ.

Теперь предположим, что я прошу вас найти число в пределах 0,01 от 2π. Вы знаете, как вычислить цифры числа π. (3,14159...) Затем вы можете взять некоторые из них и умножить на 2. Но сколько цифр вам нужно взять, чтобы ваш ответ был в пределах 0,01 от 2π?
Если умножить число на 2, ошибка удвоится. Я попросил вычислить 2π с точностью до 0,01, поэтому вам нужно вычислить π с точностью до 0,005. Допустим, вы получили 3,141, что действительно меньше 0,005 от π. Умножьте это число на 2, и готово!

Как работает RRA
Каждое число в RRA представлено в виде функции, которая принимает рациональное число и возвращает рациональное. Рациональное число, которое она принимает, — это требуемая погрешность. Рациональное число, которое она возвращает, гарантированно находится в пределах этой погрешности от вещественные числа, которое оно представляет.

Это означает, что RRA прост в использовании. Вы указываете, насколько точным должен быть ответ, и он рекурсивно определяет, какая точность нужна во всех промежуточных вычислениях. Он без проблем обрабатывает выражения, содержащие π или √2. Очень важно для калькулятора.
Новые проблемы
Вы думаете: «Конечно, Бём остановился бы здесь». Просто установил «точность вывода» на количество цифр, отображаемых калькулятором, верно? Тогда все цифры, отображаемые калькулятором, будут верными. Так что теперь калькулятор всегда показывает правильный ответ!
Но не так быстро. Когда пользователи вводят «1-1», ответ равен 0, поэтому вы хотите показать «0». Но RRA сообщит вам только, что «1-1 находится в пределах погрешности округления 0,0000000000000». Отображение 0,0000000000000 на экране, когда ответ равен ровно 0, было бы ужасным пользовательским опытом.

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

Вы можете проверить, что два числа RRA не равны. Вы можете вычислять их с большей и большей точностью, пока не увидите, в чём они различаются. Но если числа равны, вы будете вычислять их с большей и большей точностью бесконечно. Это не приведёт к завершению.
Помните: если бы калькулятор показал 0 для e^(-10000), это было бы неправильно. Это не 0. Должно быть 0,00000... и вы можете прокручивать, пока не увидите первую цифру. Но при вводе sin(π) ДОЛЖНО быть 0. sin(π) равен ровно 0. RRA не может нам это показать!
Или вы можете просто не давать ответа, как это делает калькулятор в iOS

Таким образом, точный ответ невозможно получить с помощью конструктивных вещественных чисел. Но Бём и его коллеги поняли, что возможно. Им не нужно работать со всеми конструктивными действительными числами. Им нужно работать только с числами, которые можно выразить с помощью операций, доступных на калькуляторе.
Прорыв
Постановка задачи состояла в том, чтобы определить, равны ли два конструктивных вещественных числа. Это было невозможно решить. Они упростили задачу и приблизились к решению, ограничив способы построения чисел:
-
Четыре основные арифметические операции и квадратные корни
-
Тригонометрические функции sin, cos и tan и их обратные величины
-
Экспоненциальные и (натуральные) логарифмические функции
Это гораздо меньший набор чисел, чем все конструктивные вещественные числа. И на самом деле кто-то уже исследовал именно эту задачу. Их звали Дэн Ричардсон и Джон Фитч, и они решили её в 1994 году.

Их решение было абсолютно верным. Авторы разработали полуалгоритм, который сначала сводит проблему к проверке эквивалентности элементарных констант, а затем решает её. Особенность алгоритма в том, что он всегда даёт правильный ответ при завершении и гарантированно завершается, если только задача не содержит контрпример к гипотезе Шануэля.
Звучит идеально. Но есть одна проблема. Алгоритм слишком медленный. 1 не равно 1 - e^(e^(-1000)). Но чтобы алгоритм Ричардсона и Фитча это обнаружил, потребовалось бы больше шагов, чем атомов во Вселенной. Калькулятор на Android должен работать быстрее.
Они поняли, что это не конец света, если они показывают «0,000000...» в случае, когда ответ равен ровно 0, хотя это и не идеальный пользовательский опыт. Они просто не могут показать «0» в случае, когда ответ равен 0,0000001.
RRA даёт вам всю мощь конструктивных вещественные чисел, но недостатком является то, что получение точных ответов становится невозможным. Рациональная арифметика даёт точные ответы, но не может выразить π. Можно ли объединить их сильные стороны?
Всё это и много другое — ТГ «Математика не для всех»
Автор: andreybrylb