точность вычислений коварна…

Posted: 2017-08-11 in Приколы
Метки:

Это третий пост с тегом «математика». А навеян он прочтением вот этой занятной статейки.

a/(b+c)+b/(a+c)+c/(a+b)=4

Нестрашное на первый (поверхностный) взгляд уравнение:

a/(b+c) + b/(a+c) + c/(a+b) = 4

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

Если вам интересно, какое же у него решение, и в чем подвох — просим углубиться.

На практике это уравнение эллиптической кривой, на которой поиск нужных точек — матан весьма лютый сам по себе. И да — брутфорс тут не поможет, даже на ASIC. Подробности есть в статье, я же просто приведу корни этого прекрасного уравнения:

a = 154476802108746166441951315019919837485664325669565431700026634898253202035277999

b = 36875131794129999827197811565225474825492979968971970996283137471637224634055579

c = 4373612677928697257861252602371390152816537558161613618621437993378423467772036

Правда, они классные ?

Я решил тут же это проверить, причём встроенными средствами операционки — консольным калькулятором bc, поскольку никакой другой калькулятор такое не перенесёт, а ставить спец-софт ради одной мелкой проверки мне, как обычно, влом.

Запускаем:
[Amin@h1 ~]$ bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.

bc умеет переменные, создадим:

a=1544…999
b=3687…579
c=4373…036

Для проверки просто вводим имя переменной, жмём ентер, смотрим, что там записано.

Вычисляем итоговое значение:

a/(b+c)+b/(a+c)+c/(a+b)
3

И видим три в ответе вместо четырёх. Как же так ? Проблема в том, что разрядность регистров ограничена, а компьютер при выполнении операций над числами с плавающей запятой неизбежно оставляет только какое-то фиксированное число знаков после запятой (сколько там в регистры/прочие структуры в памяти влезет). Хотя это и считается азбучной истиной, до сих пор встречаются биллинги (sic!), где можно обнаружить балансы вида 48.0299999999999999999 руб, при том что такая запись по-своему абсурдна. Это так называемые ошибки округления, которые могут накапливаться в чудовищно большие значения, полностью превращая данные в мусор. Надо быть очень внимательным к таким вещам.

Тут же ситуация дополнительно осложнена тем, что bc по умолчанию приводит результаты вычислений к целым, причём не округляя, а отбрасывая лишние разряды. Проверим и попробуем исправить это, задав переменной scale, с какой точностью после запятой вести вычисления:

scale=3
a/(b+c)+b/(a+c)+c/(a+b)
3.999

scale=300
a/(b+c)+b/(a+c)+c/(a+b)
3.999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999

Неимоверно близко к четырём, но не четыре. Проблема в том, что какое бы значение scale мы не поставили, бесконечность знаков мы принять на компе всё равно не сможем в силу конечности объёма памяти.

Попробуем немного преобразовать уравнение, приведя все три части к общему знаменателю и сделав ровно одно целочисленное (это очень важно!) деление в самом конце. Сперва вычислим промежуточные суммы, просто чтобы меньше писать текста :

ab=a+b
bc=b+c
ac=a+c

и посмотрим их:

ab
191351933902876166269149126585145312311157305638537402696309772369890426669333578

bc
41248744472058697085059064167596864978309517527133584614904575465015648101827615

ac
158850414786674863699812567622291227638480863227727045318648072891631625503050035

Смотрим:

scale=0
(a*ac*ab+b*ab*bc+c*bc*ac)/(ab*ac*bc)
4

scale=3
(a*ac*ab+b*ab*bc+c*bc*ac)/(ab*ac*bc)
4.000

scale=30
(a*ac*ab+b*ab*bc+c*bc*ac)/(ab*ac*bc)
4.000000000000000000000000000000

Как только мы пришли к целочисленному делению, и точность вычислений перестала теряться в далёких разрядах — мы сразу же получили точный ответ, несмотря на использование таких гигантских чисел.

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

Именно отсюда идёт правило, что все операции в платёжных системах (нормальных, во всяком случае) проводятся только в целых числах, а суммы внутри всегда хранятся как целое число копеек/центов/сатошей.

Будьте внимательны, грабли ждут невнимательных =) .

Реклама

Обсуждение закрыто.