Вещественные числа

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

Как компьютер хранит вещественные числа?

(Если вы не поймете, что написано в этом разделе, это не очень страшно, но попробуйте понять.)

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

Поэтому компьютер хранит числа в записи с плавающей точкой: он хранит только несколько первых ненулевых цифр числа, а также то, что называется «экспонента», т.е. целое число, показывающее, на сколько надо сдвинуть десятичную запятую в числе. Например, число 137.03599907444 компьютер может хранить следующим образом: он будет хранить несколько первых ненулевых цифр: 13703599 (ну или округленное значение: 13703600), и еще «экспоненту»: 2 — т.е. что в числе 1.3703599 (отделяется запятой только первая цифра) запятую надо сдвинуть на две цифры направо. (И это соответствует записи $137.03599907444\approx 1.3703599e2$.) Аналогично, для числа 0.007297352569824 храниться будет 72973525 и -3.

Еще более точно — компьютер хранит числа в двоичной системе счисления; все примеры выше сделаны в десятичной системе только для простоты.

Типы данных

Все современные компьютеры умеют работать со следующими тремя типами данных:

• single — хранит 7-8 значащих цифр, экспоненту до примерно 40, занимает в памяти 4 байта, работает сравнительно быстро;
• double — хранит 15-16 цифр, экспонента до ~300, занимает 8 байт, работает несколько медленнее;
• extended, он же long double — хранит 19-20 цифр, экспонента до ~5000, занимает в памяти 10 байт, работает намного медленнее;

Эти типы поддерживаются процессором (т.е. процессор умеет выполнять команду «сложить два числа типа single» или «вычесть два числа типа extended» и т.п.). Поэтому эти типы присутствуют (возможно, с другими названиями) во всех существующих языках программирования.

Кроме того, в паскале есть еще один тип данных, real. Это тип данных, существующий лишь для обратной совместимости. Дело в том, что когда язык паскаль только создавался, не было общепринятых стандартов хранения вещественных чисел в компьютере. Поэтому в первых версиях паскаля существовал особенный тип real. С тех пор появились стандарты хранения вещественных чисел, поэтому тип real теперь не нужен. Теперь во Free Pascal real — это или single, или double, в зависимости от настроек паскаля. Поэтому не используйте real, а явно пишите тот тип, который хотите.

В питоне нет простой возможности выбрать один из этих трех типов, по умолчанию доступен только тип double, причем в питоне он называется float (!).

С этими типами доступны все привычные уже вам операции: +-*/, abs, sqrt, ввод-вывод через read и writeln (в паскале) или через float(input()), map(float, ...) и print (в питоне). В питоне также работает деление с остатком (// и %).

При этом в ваших программах, а также при вводе вы можете задавать числа как в записи с фиксированной точкой, так и с плавающей, т.е. вы можете писать, например, a:=1.23+2.34e-1;, и при считывании чисел можете вводить значения тоже как в формате 1.23, так и в формате 2.34e-1.

Вообще, на паскале в наших задачах стоит использовать в первую очередь тип extended, поскольку он обеспечивает наилучшую точность, а время работы во многих задачах на вещественные числа не очень важно. Если же время работы важно, или если в вашем языке программирования нет extended, то можно использовать double. Тип single, как правило, не обеспечивает достаточной точности в олимпиадных задачах, поэтому его использовать на олимпиадах практически никогда не надо. Тип real, как уже было сказано, использовать не надо вообще никогда, ни в олимпиадных задачах, ни в реальной жизни.

Про вывод подробнее

Часто в наших задачах вы можете встретить фразу "выведите ответ с точностью до 5 знаков после запятой", или "с пятью верными знаками" и т.п. Такие фразы почти всегда обозначают, что ваш ответ должен содержать 5 верных цифр после запятой, но они не запрещают вам выводить больше цифр. Вы можете вывести хоть 20 цифр — если первые пять из них верные, то ответ будет зачтен. И наоборот, вы можете вывести меньше цифр — если невыведенные цифры — нули, то ответ тоже будет зачтен. Вообще, строго говоря, такая фраза в условии просто обозначает, что ваш ответ должен отличаться от верного не более чем на 1e-5.

Пример: если правильный ответ на задачу — 0.123456789, то вы можете вывести 0.12345, или 0.123459876, или даже 1.2345e-1 (т.к. это то же самое, что и 0.12345). А если правильный ответ — 0.10000023, то вы можете вывести 0.10000, 0.10000987 или даже просто 0.1 или 1e-001 (т.к. это то же самое, что и 0.10000).

В частности, это обозначает, что вы можете пользоваться стандартными функциями вывода (writeln и print) без каких-либо особых ухищрений; не надо округлять число, не надо форматировать вывод и т.д.

Вот если в задаче строго сказано "вывести ровно с 5 знаками после запятой", то это другое дело. Но на приличных олимпиадах такое бывает очень редко.

Полезные функции

Что в паскале, что в питоне есть несколько функций, которые вам будут полезны при работе с вещественными числами. Для ряда из этих функций надо: в паскале — в самом начале программы, до var, написать uses math;; в питоне — в самом начале программы написать from math import *. Кроме того, имейте в виду, что с этими функциями также могут возникать проблему погрешностей (см. ниже).

• floor ("пол") — округляет число вниз, т.е. определяет ближайшее целое число, которое меньше или равно данного вещественного. Например, floor(2.4)=2, floor(2)=2, floor(-2.4)=-3, и floor(2.8)=2.
• ceil ("потолок") — округляет число вверх, т.е. определяет ближайшее целое число, которое больше или равно данного вещественного. Например, ceil(2.4)=3, ceil(2)=2, ceil(-2.4)=-2, и ceil(2.8)=3.
• trunc — округляет число в сторону нуля. Например, trunc(2.4)=2, trunc(2)=2, trunc(-2.4)=-2, и trunc(2.8)=2.
• round — округляет число к ближайшему целому числу ("по школьным правилам", за исключением ситуации, когда дробная часть числа строго равна 0.5 — тогда в зависимоти от числа может быть округление то в одну, то в другую сторону). Например, round(2.4)=2, round(2)=2, round(-2.4)=-2, и round(2.8)=3.
• frac — (только в паскале; в питоне похожим образом работает взятие остатка по модулю 1: x % 1) возвращает дробную часть числа. Более точно, frac(x)=x-trunc(x). Например, frac(2.4)=0.4, frac(2)=0, frac(-2.4)=-0.4, и frac(2.8)=0.8.

Пример программы, используйющей эти функции:

uses math;
begin
writeln(floor(-2.4)); // выводит -3
writeln(ceil(2.4)); // выводит 3
writeln(trunc(2.8)+frac(2.4+0.4)); // выводит 2.8
writeln(round(3.9)); // выводит 4
end.

from math import *
print(floor(-2.4))  # выводит -3
print(ceil(2.4))  # выводит 3
print(trunc(2.8)+(2.4+0.4)%1)  # выводит 2.8
print(round(3.9))  # выводит 4

Погрешности

Два правила работы с вещественными числами

Сначала напишу два главных правила работы с вещественными числами:

Ниже я разъясняю оба этих правила.

Необходимость использования eps

Как уже говорилось выше, компьютер не может хранить все цифры числа, он хранит только несколько первых значащих цифр. Поэтому, если, например, разделить 1 на 3, то получится не 0.33333... (бесконечно много цифр), а, например, 0.33333333 (только несколько первых цифр). Если потом умножить результат обратно на 3, то получится не ровно 1, а 0.99999999. (Аналогичный эффект есть на простых калькуляторах; на продвинутых калькуляторах он тоже есть, но проявляется сложнее.)

Поэтому если вы напишите, например, следующий код:

var a:extended; // или любой другой вещественный тип
begin
a:=1/3;
a:=a*3;
if a=1 then writeln('Ok')
else writeln('Fail');
end;

то на экран будет выведено Fail.

На самом деле все еще хуже: компьютер работает в двоичной системе счисления, поэтому даже числа, в которых в десятичной системе счисления конечное число цифр, в компьютере могут представляться неточно. Поэтому, например, сравнение if 0.3+0.6=0.9 тоже не сработает: если сложить 0.3 и 0.6, то получится не ровно 0.9, а слегка отличающее число (0.899999 или 0.900001 и т.п.)

(Вдумчивый читатель-паскалист может написать программу writeln(0.3+0.6); и обнаружить, что она выводит на экран 9.0000000000000000E-0001, т.е. вроде точно 0.9, и никакими ухищрениями не получается заставить ее вывести что-то, отличающееся от 0.9. Причина опять в том, что компьютер работает в двоичной системе счисления: реально получается не совсем 0.9, но при переводе результата в десятичную систему для вывода на экран эта очень маленькая ошибка отбрасывается. Тем не менее, ее можно увидеть, если написать writeln(0.3+0.6-0.9); — получится вовсе не ноль, а 5.4210108624275222E-0020, т.е. видно, что сумма 0.3+0.6 действительно не равна 0.9. Почему получился именно такой результат, и почему на самом деле цифрам этого результата нельзя верить — это тема отдельного разговора. Отмечу еще, что все это у меня получилось на Kubuntu Linux, на других системах или при других настройках результат может быть другим; может даже оказаться, что 0.3+0.6 точно равно 0.9, но ошибки будут на других парах чисел.)

(На питоне все тут проявляется еще ярче: print(0.3+0.6) выводит у меня 0.8999999999999999.)

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

Стандартный подход для борьбы с этим — выбрать маленькое число eps (от названия греческой буквы ε — «эпсилон», «epsilon»), и два числа считать равными, если они отличаются не более чем на eps.

Про то, как выбирать это eps, обсудим ниже, пока будем считать, что мы взяли eps=1e-6. Тогда в начале программы (обычно принято до var) пишем

// pascal
const eps=1e-6;

# python
eps = 1e-6

То есть мы предполагаем, что если два числа на самом деле должны быть равны, но отличаются из-за погрешности, то они отличаться будут менее чем на eps; а если они на самом деле должны различаться, то различаться они будут более чем на eps. Таким образом, eps разделяет ситуации «два числа равны» и «два числа не равны». (Естественно, это будет работать не при любом eps, т.е. eps надо аккуратно выбирать — про это см. ниже.)

Аналогично, если нам надо проверить if x>=y, то надо писать if x>=y-eps или if x>y-eps. (Обратите внимание, что тут не важно, писать строгое или нестрогое равенство — вероятность того, что окажется точно x=y-eps очень мала из-за тех же погрешностей: скорее всего окажется или больше, или меньше. Более того, если оказалось, что точно x=y-eps, это обозначает, что мы неправильно выбрали eps, т.к мы не смогли отделить ситуацию «числа $x$ и $y$ равны» и ситуацию «числа не равны». См. еще ниже в разделе про выбор eps.)

Если нам надо написать условие if x>y, то его тоже надо переписать, ведь нам важно (подробнее см. ниже), чтобы при $x=y$ условие не выполнилось! Поэтому переписать его надо так: if x>y+eps. Аналогичные соображения действуют для любых других сравнений вещественных чисел.

Итак, именно поэтому

(Первое правило будет дальше :) )

^* за исключением случаев, когда вам не важно, что произойдет в случае точного равенства, см. ниже.

Выбор eps

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

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

В некоторых задачах такое eps можно вычислить строго. Например, пусть задача: даны три числа $a$, $b$ и $c$, каждое не больше 1000, и каждое имеет не более 3 цифр после десятичной запятой. Надо проверить, правда ли, что $a+b=c$. Из изложенного выше понятно, что тупое решение if a+b=c не сработает: может оказаться, что должно быть $a+b=c$, но из-за погрешностей получится, что $a+b<> c$. Поэтому надо проверять if abs(a+b-c)<eps, но какое брать eps?

Подумаем: пусть действительно $a+b=c$. Какой может быть разница $a+b-c$ с учетом погрешностей? Мы знаем, что $a$, $b$ и $c$ не превосходят 1000. Это значит, что если мы, например, используем тип данных double, в котором хранятся 15-16 верных цифр, то погрешности будут примерно в 15-16-й значащей цифре. Для максимальных возможных значений чисел (т.е. для 1000) погрешности будут порядка 1e-12 или меньше, т.е. можно рассчитывать, что если $a+b=c$, то в программе $|a+b-c|$ будет порядка 1e-12 или меньше.

С другой стороны, пусть $a+b<> c$. Какой тогда может быть разница $|a+b-c|$? По условию, все числа имеют не более трех цифр после запятой, поэтом понятно, что эта разница будет равна 0.001 или больше.

Поэтому можно, например, взять eps=1e-5. С одной стороны, если на самом деле $a+b=c$, то в программе $|a+b-c|$ точно получится намного меньше eps, а с другой стороны, если на самом деле $a+b<> c$, то $|a+b-c|$ будет точно намного больше eps. Итак, в этом примере мы смогли точно вычислить подходящее eps (на самом деле, конечно, вариантов много — подошло бы любое число, которое существенно меньше 1e-3 и существенно больше 1e-12).

Но бывают задачи, где так просто вычислить подходящее eps не получается. На самом деле таких задач большинство — как только вычисления у вас становятся сложнее чем сложить два числа, за погрешностями уже становится сложно уследить. Можно, конечно, применять какие-нибудь сложные техники, но обычно принято просто брать какое-нибудь eps порядка 1e-6..1e-10.

Но в итоге вы не можете быть уверены, что вы выбрали правильное eps. Если ваша программа не работает — это может быть потому, что у вас ошибка в программе, а может быть просто потому, что вы выбрали неверный eps. Бывает так, что достаточно поменять eps — и программа пройдет все тесты. Конечно, это не очень хорошо, но ничего не поделаешь.

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

Собственно, из этого и следует

Пример: пусть у вас в программе есть четыре целых (integer) положительных числа $a$, $b$, $c$ и $d$, и вам надо сравнить две дроби: $a/b$ и $c/d$. Вы могли бы написать if a/b>c/d, но это плохо: в результате деления получаются вещественные числа, и вы сравниваете два вещественных числа со всеми вытекающими последствиями. (Конкретно в этом случае, возможно, ничего плохого не случится, но в чуть более сложных случаях уже может случиться, да и в этом случае возможно и случится, я не проверял.) А именно, может оказаться, например, что $a/b=c/d$ на самом деле, но из-за погрешностей в программе получится $a/b>c/d$ и if выполнится. Вы можете написать eps, думать, каким его выбрать... но можно проще. Можно просто понять, что при положительных (по условию) числах это сравнение эквивалентно условию if a*d>c*b. Здесь все вычисления идут только в целых числах, поэтому это условие работает всегда (ну, если нет переполнения, конечно), и не требует никаких eps (да еще и работает быстрее, чем предыдущий вариант). Его написать не сложнее, чем вариант с делением, поэтому всегда следует так и писать. Всегда, когда в решении вы переходите от целых к вещественным числам, задумайтесь на секунду: а нельзя ли обойтись без вещественных чисел? Если да, то постарайтесь так и поступить — и никаких проблем с точностью у вас не возникнет.

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

Дополнительный материал. «Грубые» задачи: когда eps не нужно

Рассмотрим следующие код (x, y, max -- вещественные числа):

if x>y then max:=x 
else max:=y;

if x > y:
    max = x
else: 
    max = y

Здесь мы сравниваем два вещественных числа, чтобы найти максимум из них. Казалось бы, в соответствии со сказанным выше, в сравнении нужен eps... но нет! Ведь если два числа на самом деле равны, то нам все равно, в какую из веток if мы попадем — обе ветки будут верными! Поэтому eps тут не нужен.

Так иногда бывает — когда вам все равно, в какую ветку if'а вы попадете, если два сравниваемых числа на самом деле равны между собой. В таком случае eps использовать не надо. Но каждый раз тщательно думайте: а правда ли все равно? Всегда лучше перестраховаться и написать eps (выше с eps тоже все работало бы), за исключением совсем уж простых случаев типа приведенного выше вычисления максимума.

Еще пример: считаем сумму положительных элементов массива

var x:array[...] of extended;

... пусть значения массива x вычисляются в программе
s:=0;
for i:=1 to n do
    if x[i]>0 then s:=s+x[i];

# x -- массив вещественых чисел
s = 0
for i in range(len(x)):
    if x[i] > 0:
        s += x[i]

Здесь, опять-таки, если должно быть $x_i=0$, то не важно, добавим мы его в сумму или нет: сумма от добавления нуля не изменится. Поэтому eps писать не надо (но ничего страшного не будет, если и написать).

Еще пример, где уже eps необходим: определим, какое из двух чисел больше:

var x,y:extended;
    ans:integer;
...
if x>y+eps then ans:=1
else if x<y-eps then ans:=2
else ans:=0;

...
if x > y + eps:
    ans = 1
elif x < y-eps:
    ans = 2
else:
     ans:=0

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

Тогда в задаче (фрагменте кода) eps нужен, если задача является негрубой: тогда существуют такие входные данные, которые вам важно отличить от очень близких им. Например, если надо определить, какое из двух чисел больше, то при входных данных «0.3 0.3» надо ответить «они равны», но при очень небольшом изменении входных данных, например, на «0.300001 0.3» ответ резко меняется: надо отвечать «первое больше».

Если же задача (или фрагмент кода) является грубым, то, скорее всего, в нем можно обойтись без eps: если вы чуть-чуть ошибетесь при вычислениях, ответ тоже изменится не очень сильно. Например, если вы вычисляете максимум из двух чисел, то на входных данных «0.3 0.3» ответ 0.3, а на входных данных «0.300001 0.3» ответ 0.300001, т.е. изменился не очень сильно.

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