Про деление пополам, или не используйте вещественные числа

13.01.2019

Всем ученикам на алгопроге я всегда говорю: никогда не используйте вещественные числа, если без этого можно обойтись — из-за погрешностей, которые при этом всегда возникают. Подобные решения я сразу «игнорирую» (не засчитываю и требую от учеников их переделать).

В качестве примера — в одной задаче надо проверять, правда ли, что некоторая целочисленная величина a составляет не менее 7% от другой целочисленной величины b (да, это задача про выборы, а как вы догадались?). Там часто пишут типа a >= 0.07 * b, а я требую переписать это на 100 * a >= 7 * b, или что-нибудь подобное.

С другой стороны, иногда операции с вещественными числами настолько простые, что подобное придирание казалось мне неправильным. Но вот сегодня подходит ко мне школьник: мол, у него не работает решение по задаче ВТО. Да, я конечно помню эту задачу. Там действительно есть где ошибиться: надо, во-первых, хорошо понимать применения НОДа, чтобы понять, как тут применить НОД, плюс, как сказали бы ЧГКшники, в этой задаче нетривиальный пуант — можно все посчитать правильно, но на последних строчках неправильно вычислить то число, которое собственно надо вывести.

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

Ладно, говорю, покажи код. Смотрю, «пуант» вроде правильный, и вообще код правдопродобен. Ближе к концу мне в глаза бросается следующее (решение на питоне 3):

cs = int((x*y-us)/2)

Ну, говорю, вообще у тебя тут вещественные числа. Ну и что, говорит он, у меня же int. Да, говорю, но вот представь себе, если у тебя от деления 10 на 2 получится не 5, а 4.9999 — ведь тогда int даст 4. Да, действительно, говорит школьник — давайте попробую пересдать, исправив на //.

Эх, думаю я про себя, я ведь обманываю школьника. Я-то знаю, как компьютер хранит вещественные числа, и понимаю, что разделить на 2 — это просто вычесть 1 из экспоненты, и при делении 10 на 2 абсолютно точно получится ровно 5. Будь любая другая операция — еще могли бы быть проблемы, но деление на 2 не создает дополнительных погрешностей…

И тут я вспоминаю, что в этой задаче ограничение на x и y вроде бы до 10^9, а соответственно x*y может быть до 10^18 и, конечно же, не может быть точно представлено в вещественном типе двойной точности (питоновском float, который на самом деле double). И это вполне сходится с тем, что у школьника проходят все тесты, кроме нескольких последних — которые скорее всего близки к максимальным.

Школьник переписал на //, сдал, получил OK.

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


Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru