Хабрахабр

Aрифметика произвольной точности в Erlang


@rawpixel

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

Однако, хотелось бы иметь не только bigint, но и возможность оперирования рациональными, комплексными и числами с плавающей точкой с необходимой точностью. Если говорить про Erlang, то он, как и многие другие языки, реализует IEEE754 стандарт для float, в то время как стандартный тип Integer в Erlang реализован с использованием арифметики произвольной точности.

Решение, обеспечивающее необходимую точность операций через переход в представление с фиксированной точкой, оформлено в виде библиотеки EAPA (Erlang Arbitrary Precision Arithmetic), призванной удовлетворить потребности финансовых приложений, разрабатываемых на Erlang / Elixir. В статье представлен минимальный обзор теории кодирования чисел с плавающей точкой и наиболее яркие примеры возникающих эффектов.

Стандарты, стандарты, стандарты...

Он определяет четыре формата представления: На сегодняшний день основным стандартом двоичной арифметики с плавающей точкой является широко применяемый в технике и программировании IEEE754.

  • с одинарной точностью (single-precision) 32 бита
  • с двойной точностью (double-precision) 64 бита
  • с одинарной расширенной точностью (single-extended precision) >=43 бит (редко используемый)
  • с двойной расширенной точностью (double-extended precision) >= 79 бит (обычно используют 80 бит)
    и четыре режима округления:
  • Округление, стремящееся к ближайшему целому.
  • Округление, стремящееся к нулю.
  • Округление, стремящееся к +∞
  • Округление, стремящееся к -∞

Форматы представления ограничивают предельный размер числа, а режимы округления влияют на точность. Большинство современных микропроцессоров изготовляются с аппаратной реализацией представления вещественных переменных в формате IEEE754. Например, официальная реализация Erlang хранит float в 3 словах на 64 разрядной машине и в 4 словах на 32 разрядной. Программисты зачастую не могут изменить поведение аппаратуры и реализации языков программирования.

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

Так, для float она составляет 11,920928955078125e-6 %, а для double — 2,2204460492503130808472633361816e-14 %. Основная масса чисел при отображении на конечное множество имеет стабильную и небольшую относительную погрешность. В жизни программистов большинство решаемых повседневных задач позволяют пренебречь этой погрешностью, хотя следует учесть, что и в простых задачах можно наступить на грабли, так как величина абсолютной ошибки может достигать 1031 и 10292 для float и double соответственно, вызывая затруднения в вычислениях.

Иллюстрация эффектов

Давайте попробуем воспроизвести возникающие эффекты в Erlang. От общей информации к делу.

Все примеры, приведенные ниже, оформлены в виде ct-тестов.

Округление и потеря точности

Начнем с классики – сложения двух чисел: 0,1+0,2 = ?:

t30000000000000004(_)-> ["0.30000000000000004"] = io_lib:format("~w", [0.1 + 0.2]).

Попробуем добиться верного результата. Результат сложения слегка отличается от интуитивно ожидаемого, и тест проходит успешно. Перепишем тест с использованием EAPA:

t30000000000000004_eapa(_)-> %% prec = 1 symbols after coma X = eapa_int:with_val(1, <<"0.1">>), Y = eapa_int:with_val(1, <<"0.2">>), <<"0.3">> = eapa_int:to_float(1, eapa_int:add(X, Y)).

0 совсем небольшую величину: Данный тест тоже успешно выполняется, показывая, что проблема устранена.
Продолжим эксперименты, добавим к 1.

tiny(_)-> X = 1.0, Y = 0.0000000000000000000000001, 1.0 = X + Y.

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

tiny_eapa(_)-> X1 = eapa_int:with_val(1, <<"1.0">>), X2 = eapa_int:with_val(25, <<"0.0000000000000000000000001">>), <<"1.0000000000000000000000001">> = eapa_int:to_float(eapa_int:add(X1, X2)).

Переполнение разрядной сетки

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

float_overflow(_) -> 1.0 = 9007199254740991.0 - 9007199254740990.0, 1.0 = 9007199254740992.0 - 9007199254740991.0, 0.0 = 9007199254740993.0 - 9007199254740992.0, 2.0 = 9007199254740994.0 - 9007199254740993.0.

0, что очевидно является проблемой. Как видно из теста, в какой-то момент разница перестает быть равна 1. EAPA позволяет решить и эту проблему:

float_overflow_eapa(_)-> X11 = eapa_int:with_val(1, <<"9007199254740992.0">>), X21 = eapa_int:with_val(1, <<"9007199254740991.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X11, X21)), X12 = eapa_int:with_val(1, <<"9007199254740993.0">>), X22 = eapa_int:with_val(1, <<"9007199254740992.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X12, X22)), X13 = eapa_int:with_val(1, <<"9007199254740994.0">>), X23 = eapa_int:with_val(1, <<"9007199254740993.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X13, X23)).

Опасная редукция

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

Покажем, что в Erlang эта проблема присутствует:

reduction(_)-> X = float(87654321098765432), Y = float(87654321098765431), 16.0 = X-Y. %% has to be 1.0

0 вместо ожидаемого 1. Получилось 16. Попробуем исправить данную ситуацию: 0.

reduction_eapa(_)-> X = eapa_int:with_val(1, <<"87654321098765432">>), Y = eapa_int:with_val(1, <<"87654321098765431">>), <<"1.0">> = eapa_int:to_float(eapa_int:sub(X, Y)).

Другие особенности арифметики с плавающей точкой в Erlang

Начнем, пожалуй, с игнорирования отрицательного нуля.

eq(_)-> true = list_to_float("0.0") =:= list_to_float("-0.0").

Сразу хочется сказать, что EAPA сохраняет данное поведение:

eq_eapa(_)-> X = eapa_int:with_val(1, <<"0.0">>), Y = eapa_int:with_val(1, <<"-0.0">>), true = eapa_int:eq(X, Y).

В Erlang нет внятного синтаксиса и обработки NaN и бесконечностей, что порождает целый ряд особенностей, например, вот таких: так как оно допустимо.

1> math:sqrt(list_to_float("-0.0")).
0.0

Попробуем воспроизвести для маленьких: Следующим моментом является особенность обработки больших и маленьких чисел.

2> list_to_float("0."++lists:duplicate(322, $0)++"1").
1.0e-323
3> list_to_float("0."++lists:duplicate(323, $0)++"1").
0.0

и для больших чисел:

4> list_to_float("1"++lists:duplicate(308, $0)++".0").
1.0e308
5> list_to_float("1"++lists:duplicate(309, $0)++".0").
** exception error: bad argument

Приведем еще пару примеров для маленьких чисел:

6> list_to_float("0."++lists:duplicate(322, $0)++"123456789").
1.0e-323
7> list_to_float("0."++lists:duplicate(300, $0)++"123456789").
1.23456789e-301

8> 0.123456789e-100 * 0.123456789e-100.
1.524157875019052e-202
9> 0.123456789e-200 * 0.123456789e-200.
0.0

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

EAPA (Erlang Arbitrary-Precision Arithmetic)

На данный момент в репозитории EAPA представлен максимально простой и удобный интерфейс eapa_int для работы с числами с фиксированной точкой. EAPA – NIF расширение, написанное на Rust. К числу особенностей eapa_int можно отнести следующие:

  1. Отсутствие эффектов IEEE754 кодирования
  2. Поддержка больших чисел
  3. Настраиваемая точность до 126 знаков после запятой. (в текущей реализации)
  4. Автоскейлинг
  5. Поддержка всех основных операций над числами
  6. Более или менее полное тестирование, в том числе property based.

Интерфейс eapa_int:

  • with_val/2 – перевод числа с плавающей точкой в фиксированное представление, которое можно в том числе безопасно использовать в json, xml.
  • to_float/2 – перевод числа с фиксированной точкой в число с плавающей точкой с заданной точностью.
  • to_float/1 – перевод числа с фиксированной точкой в число с плавающей точкой.
  • add/2 – сумма двух чисел
  • sub/2 – разность
  • mul/2 – умножение
  • divp/2 – деление
  • min/2 – минимальное из чисел
  • max/2 – максимальное из чисел
  • eq/2 – проверка равенства чисел
  • lt/2 – проверка, что число меньше
  • lte/2 – проверка меньше равно
  • gt/2 – проверка, что число больше
  • gte/2 – проверка больше равно

Код EAPA можно найти в репозитории https://github.com/Vonmo/eapa

Например, если ваше приложение работает с деньгами или вам нужно удобно и точно производить вычислительные операции над числами вида 92233720368547758079223372036854775807. Когда следует использовать eapa_int? 92233720368547758079223372036854775807, можно смело использовать EAPA.

Мы получаем необходимую точность, жертвуя памятью и скоростью вычислений, Тесты производительности и статистика, собранная на реальных системах, показывают, что большинство операций выполняются в диапазоне 3-30 мкс. Как и любое решение, EAPA это компромисс. Данный момент тоже необходимо учитывать при выборе интерфейса с фиксированной точкой EAPA.

Заключение

Конечно, далеко не всегда приходится решать подобные задачи на Erlang или Elixir, но когда возникает проблема и не находится подходящий инструмент, приходится изобретать решение.
Данная статья – это попытка поделиться с сообществом инструментом и опытом, в надежде, что для кого-то эта библиотека окажется полезной и поможет сохранить время.
А как вы считаете деньги в Erlang?

S. P. Не переключайтесь! Работа с рациональными и комплексными числами, а также нативный доступ к Integer, Float, Complex, Rational типам произвольной точности будут освещены в следующих публикациях.

Материалы по теме:

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть