Приложение-калькулятор? Да каждый может написать такое

Неправда.

Калькулятор должен показать вам результат введенного вами математического выражения. Это намного, намного сложнее, чем кажется.

То, что я вам сейчас расскажу, — величайшая история разработки приложений для калькуляторов, которую когда-либо рассказывали. Изображение выше — это калькулятор в iOS. Заметили что-нибудь?

В нем ошибка.

(10^100) + 1 — (10^100) — это 1, а не 0.

В Android все правильно. И история о том, как это так, совершенно безумна.

Компания Google наняла Ханса-Я. Боэма, известного по «сборщику мусора Боэма».

Им нужен был элитный кодер, чтобы исправить ситуацию со сборкой мусора и параллельным программированием. Он возглавил работу по определению семантики общих переменных в C++.

Но потом перед ним поставили невыполнимую задачу: написать приложение для калькулятора.

Даже для него это, должно быть, было непростой задачей.

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

Это означает, что калькулятор, построенный на числах с плавающей запятой, подобен дому, построенному на песке.

Стоит повторить. Чтобы давать правильные ответы на математические выражения, калькулятор должен представлять числа.

И почти все числа не могут быть выражены в формате IEEE с плавающей запятой.

Даже простые операции с числами с плавающей запятой требуют тщательного оперирования для получения точного ответа.

Некоторых проблем можно избежать, если использовать длинную арифметику.

Большинство числовых типов всегда имеют размер 2 или 4 байта. Это не так для больших чисел. Это целые числа без границ. Они растут в памяти по мере необходимости.

Это решает проблему с (10^100) + 1 - (10^100). Но большие числа — это целые числа. А как насчет дробей?

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

Математика гораздо глубже, чем дроби. Как насчет π или √2?

Калькулятор, работающий с дробями произвольной точности, все равно не сможет определить окружность круга, поскольку π не выражается в виде дроби.

Если ваш калькулятор не может справиться с математикой 9-го класса, что в нем хорошего?

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

Для √2 это будет x² - 2 = 0 (к тому же вы будете помнить, что вам нужен положительный корень).

Теперь математические операции становятся немного сложнее в реализации:

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

Угадайте, что? Для Боэма это все еще недостаточно хорошо. Это работает только для алгебраических чисел. Это не дает нам π. Поэтому Боэму ничего не оставалось, как углубиться еще глубже. Пришло время серьезных вещей.

Мы начали с целых чисел (больших чисел), перешли к рациональным числам, затем к алгебраическим. Что дальше?

К вещественным числам.

Поэтому Боэм начал рассматривать «рекурсивную вещественную арифметику» (Recursive Real Arithmetic, 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… и позволять вам прокручивать, пока вы не увидите, где число меняется.

Но он ДОЛЖЕН показывать 0, когда вы вводите sin(π). sin(π) — это ровно 0.

RRA не дает нам способа сказать, что sin(π) равен  ровно нулю.

Или вы можете просто не давать ответ вообще, как это делает калькулятор iOS :)

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

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

К ним относятся:

• Четыре основных арифметических действия и квадратные корни.
• Тригонометрические функции sin, cos и tan и их инверсии.
• Экспоненциальные функции и функции (натурального) логарифма

Это гораздо меньший набор чисел, чем все вещественные числа. И на самом деле, кто-то уже исследовал именно эту проблему. Их звали Дэн Ричардсон и Джон Фитч, и они решили ее в 1994 году.

Их решение абсолютно верно. Если только одно из чисел не является контрпримером к гипотезе Шануэля. Но в реальности этого не произойдет. Гипотеза Шануэля — одна из самых важных в теории чисел, и пока никто не нашел контрпримера.

Звучит идеально. Но есть одна проблема. Это слишком медленно.

1 не равно 1 - e^(-e^1000). Но чтобы алгоритм Ричардсона и Фитча это обнаружил, потребовалось бы больше шагов, чем атомов во Вселенной.

Им нужно было что-то более быстрое. Их первоначальная задача состояла в том, чтобы проверить, равны ли два конструктивных вещественных числа. Решить это оказалось невозможно.

Они упростили задачу и приблизились к решению, ограничив способ определять числа. Это сделало задачу решаемой, но медленной.

Могут ли они упростить ее снова?

Они поняли, что это не конец света, если они покажут «0.000000…» в случае, когда ответ равен 0, хотя это и не идеальный UX. Они просто не могут показать «0» в случае, когда ответ равен 0,0000001.

Может быть, можно было использовать более быстрый и консервативный алгоритм? Тогда они придумали нечто поистине гениальное.

RRA дает вам всю мощь конструктивных действительных чисел, но с тем недостатком, что получение точных ответов становится невозможным.

Рациональная арифметика дает точные ответы, но не может выразить π. Можно ли объединить их сильные стороны?

Они поняли, что если пользователь просто вводит 6 * 9 или 8 / 3, то вся мощь RRA не нужна. В этих случаях достаточно рациональной арифметики.

RRA нужна только тогда, когда рациональных чисел недостаточно. Используйте ее, когда в дело вступают числа вроде π или √2, а в остальных случаях используйте рациональные числа.

Рациональные числа точны, но не могут представить π. Числа RRA могут представлять числа типа π, но не могут быть точными.

Решение: представить все числа в виде рационального числа, умноженного на RRA.

Но этого недостаточно. Как только в процесс вовлекаются числа RRA, результат обязательно будет неточным.

Но даже для иррациональных чисел RRA иногда может оказаться излишним.

RRA представляет π как функцию, которая может возвращать рациональные числа, произвольно близкие к π (точно так же, как все числа в RRA представлены как функции).

Вы говорите: «Мне нужно π в пределах 0,001», и RRA говорит вам: «Хорошо, это 3,141».

Иногда требуется RRA.

Но в этом случае можно также просто иметь специальное представление для π, которое мы специально используем вместо его функции RRA.

Мы называем это символьным представлением, поскольку это все равно что записать символ для π, а не бесконечную последовательность цифр

Теперь можно приступать к готовке. Но давайте сделаем это не только для π. Очевидно, что нам нужно символическое представление для действительного числа 1.

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

Они выбрали символические представления для √arg, eᵃʳᵍ, ln(arg), log₁₀(arg), sin(πarg), tan(πarg) и др (где arg — некоторое рациональное число).

Итак, их окончательное представление для чисел: рациональное умноженное на вещественное, где вещественное — это либо вещественное RRA, либо символическое вещественное.

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

Но иногда они все же нужны. Так что теперь оставалось только стараться избегать RRA-чисел как можно чаще!

Например, в (1 × π) + (3 × π) нам повезло, что у нас есть символические представления вещественных частей. π в обоих случаях.

Поскольку вещественные части одинаковы, мы можем выполнить суммирование путем сложения рациональных частей. Если бы это было (1 × π) + (3 × √2), они бы просто использовали RRA для этого.

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

«Система компьютерной алгебры» достигла бы аналогичной цели, но была бы гораздо медленнее и гораздо сложнее. Система компьютерной алгебры настолько сложна, что поддерживать ее в рабочем состоянии способны очень немногие.

Но то, что придумали Боэм и co, на 100% верно, и позволяет достичь 99% пути к идеальному UX всего за 1% от сложности реализации.

Вот это инженерия! Вы должны прочитать его статью «На пути к API для реальных чисел».

Надеюсь, в следующий раз вы будете больше ценить свой калькулятор для Android!

Источник