Октябрь 31

Согласно школьного курса математики, при округлении чисел мы отбрасываем ненужные разряды, причем если первая отбрасываемая цифра больше или равна 5, то последняя сохраняемая цифра увеличивается на единицу. Будем называть этот способ «Арифметическим округлением».

Недоверчивый читатель, наверное, уже заподозрил, что сейчас пойдет речь и о других способах округления, и тянет руку с вопросом: а зачем, собственно? Чем не устраивает этот, столь родной и знакомый?

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

Контора заработала ровно миллион рублей, и поручила бухгалтеру разделить их на тысячу работников пропорционально коэффициенту трудового участия (КТУ). Тот выполнил арифметические действия и получил для каждого работника некоторое число Ni, с некоторым хвостиком дробных копеек. Убедился, что сумма всех Ni дает ровно миллион (мы опускаем проблемы неделимости нацело и бесконечных дробей — пусть хоть сегодня у нас все поделилось). Рассчитал сумму к выдаче — округлил каждое Ni до копеек, и подбил итог. И что же он видит?

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

КТУ в конторе по старой советской традиции ставили с потолка, поэтому он достаточно хорошо подчинялся закону распределения случайных чисел. Соответственно, когда дело доходило до округления, то среди «первых отбрасываемых цифр» было примерно поровну нулей, единичек, двоек и всех остальных цифр. Каждая операция округления вносила свою погрешность (разницу между первоначальным и округленным значением) в зависимости от отброшенного хвостика. При этом погрешности отброшенных единичек (-0.001) компенсировались погрешностями девяток (+0.001), двойки компенсировали восьмерки, и так далее, и лишь погрешности, вносимые при отбрасывании пятерок (+0.005), оставались нескомпенсированными, и накапливались. В среднем на тысяче человек встретилось 100 операций отбрасывания пятерки, каждая из которых дала погрешность пол-копейки. Отсюда и набежали злосчастные 50 копеек.

Вот фрагмент расчетной ведомости, демонстрирующий набегание одной копейки при раздаче суммы в 2000 руб.21 коп.:

КТУ Расчет (Ni) К выдаче Погрешность
1 100001 100.0010 100.00 -0.0010
2 100002 100.0020 100.00 -0.0020
3 100003 100.0030 100.00 -0.0030
4 100004 100.0040 100.00 -0.0040
5 100005 100.0050 100.01 0.0050
6 100006 100.0060 100.01 0.0040
7 100007 100.0070 100.01 0.0030
8 100008 100.0080 100.01 0.0020
9 100009 100.0090 100.01 0.0010
10 100010 100.0100 100.01 0.0000
11 100011 100.0110 100.01 -0.0010
12 100012 100.0120 100.01 -0.0020
13 100013 100.0130 100.01 -0.0030
14 100014 100.0140 100.01 -0.0040
15 100015 100.0150 100.02 0.0050
16 100016 100.0160 100.02 0.0040
17 100017 100.0170 100.02 0.0030
18 100018 100.0180 100.02 0.0020
19 100019 100.0190 100.02 0.0010
20 100020 100.0200 100.02 0.0000
2000.21 2000.22 0.01

Если бы бухгалтер был магом и чародеем, он несомненно решил бы проблему так, чтобы какой-нибудь саблезубый тигр откусил руку, или хотя бы нечетное количество пальцев нашему волосатому пращуру, придумавшему десятичную систему счисления, чтобы в ней не осталось «середины». Но он выкрутился хитрее — половину отбрасываемых пятерок стал округлять вверх, а половину — вниз. Чтобы его не обвинили в личных пристрастиях, критерием стала цифра перед пятеркой — если она четная, то округление вниз, иначе вверх. Это правило и называется правилом «Бухгалтерского» (или «Банковского») округления.

В нашем примере в строке 5 сумма стала округляться до 100.00, вносимая погрешность стала -0.005, скомпенсировав строку 15, и сумма к выдаче совпала с исходной.

Теперь, когда у нас есть больше одного способа округления, возникает извечный вопрос: а какой из них правильный?

Любопытно, что в обсуждении этого вопроса спорщики обычно начисто забывают об области применения алгоритма, и вообще каких-либо критериях правильности, а ищут некую правильность в метафизическом, вселенском смысле. Приходилось встречать мнение, что банковское округление характерно для капиталистических стран, а арифметическое — для СССР. Другие доказывали, что арифметическому учат в школе, а банковскому — в ВУЗах. Когда выяснялось, что в некоторых институтах тоже применяют арифметическое, на полном серьезе составляли «черный список» таких ВУЗов и подвергали их осмеянию. Третьи говорили, что это баг от Microsoft, или глюк всех Pentium-ов (или AMD, в зависимости от личных пристрастий). Поэтому хотелось бы знать, существует ли некий общепринятый документ относительно способов округления. И такой документ действительно существует. Это знаменитый стандарт IEEE 754.

Любопытна история создания этого документа. В 60-е — 70-е годы, когда компьютеры были большими, каждая линейка компьютеров имела свою программную реализацию вычислений с плавающей запятой, свои форматы представления чисел, точность, представимые диапазоны и правила округления. Соответственно, чудеса, вроде описанных в «Неочевидных особенностях вещественных чисел», были у каждого свои. По воспоминаниям старожилов, на некоторых машинах число могло выглядеть отличным от нуля в операциях сравнения и сложения, но быть чистым нулем при умножении и делении. Чтобы без страха поделить на такое число, его следовало умножить на 1.0 и лишь потом сравнить с нулем. А другие машины могли выдать ошибку переполнения при умножении на 1.0 вполне нормального числа. Были такие малюсенькие числа (но не нули), которые давали переполнение при делении на самих себя. В программах были обычными шаманские вставки вроде X = (X + X) — X. Соответственно, одна и та же программа, даже написанная на стандартном FORTRAN’е, могла давать разные результаты на разных машинах.

Для решения этой проблемы в середине 70-х под эгидой IEEE неторопливо начал работу комитет по выработке стандарта 754 — о реализациях вычислений с плавающей запятой. Примерно в это же время Intel начал разработку арифметического сопроцессора i8087 для своих процессоров i8086/88. В качестве консультанта был приглашен профессор Вильям Каган, известный успешным сотрудничеством с Hewlett-Packard.

Проект подходил к завершению. В этот сопроцессор удалось втиснуть все лучшее, что было на тот момент. Профессор Каган решил принять участие в работе комитета IEEE, получил от Intel разрешение открыть некоторые спецификации нового сопроцессора (без раскрытия подробностей его реализации), и представил их как проект стандарта. Учитывая, что у конкурентов сопроцессоры были пока лишь в планах, Intel-овские спецификации выгодно отличались продуманностью и завершенностью. Крыть было нечем. Проект де-факто лег в основу стандарта.

Текст стандарта по идее можно получить в первоисточнике (http://ieee.org), но обычно ссылаются на сборник связанной с ним информации от IBM (http://www2.hursley.ibm.com/decimal/).

Этот стандарт описывает пять способов округления, обязательных для реализации, и два опциональных.

  • round-down — усечение по направлению к нулю
  • round-half-up — арифметическое округление
  • round-half-even — банковское округление
  • round-ceiling — округление к плюс-бесконечности
  • round-floor — округление к минус-бесконечности
  • round-half-down (опционально) — подобно арифметическому, пятерка округляется вниз
  • round-up — (опционально) округление от нуля

А ведь это далеко не все способы, которые можно вообразить. Спросите, зачем нужно больше? Ответим.

Банковское округление — вовсе не панацея для подавления статистической погрешности. Она спасла нашего бухгалтера лишь потому, что округляемые числа были достаточно случайны, то есть появление четных и нечетных цифр перед пятеркой было равновероятно. Но пришли в контору новые времена, и КТУ стали хитро высчитывать на основании затраченного рабочего времени. По нелепому совпадению, для стандартного рабочего месяца это оказалось равно 100005 (как в строке 5). А так как большинство людей работают без прогулов, то значение это стало встречаться очень часто, и итог «К выдаче» вновь оказался больше, чем «Заработано».

Для решения этой проблемы известны следующие алгоритмы:

  1. Random Rounding. Округлять отбрасываемую пятерку вверх либо вниз случайным образом. В принципе, удовлетворительно подавляет статистическую погрешность даже на неслучайных наборах данных. Досадные побочные эффекты — непредсказуемость и неповторяемость результата. Может быть, этот метод и применим в каких-нибудь научно-статистических процедурах обработки информации, но в бухгалтерии он вряд ли приживется.
  2. Alternate Rounding. При каждом очередном вызове для округления пятерки округлять поочередно — один раз вверх, один раз вниз. Понятно, что для этого придется сохранять состояние функции между вызовами. Хотя результат ее работы не удастся объяснить каждому конкретному работяге из операционной ведомости (почему у нас с соседом КТУ одинаковый, а мне к выдаче на копейку меньше), но по крайней мере результат расчетов будет повторяем.
  3. Начисление по цепочке. Суть в том, что после округления первой строки ведомости полученная сумма «к выдаче» вычитается из общей распределяемой суммы (миллиона рублей). Первая строка как бы отбрасывается из рассмотрения, и остаток ведомости пересчитывается исходя из остатка распределяемой суммы на оставшихся 999 человек. После округления следующей строки она вновь отбрасывается, и так далее. Этот алгоритм гарантирует, что итог округленных сумм «к выдаче» обязательно сойдется с исходной (неокругленной) суммой при любом наборе данных. Недостаток его в том, что он работает только «кучей» — пересчитать одного человека будет невозможно, и опять же для одинаковых КТУ округление может произойти по разному.

Думаю, при таком обилии алгоритмов вопрос «какой из них единственно верный» ставить как-то неудобно. Правда, IEEE 754 требует, чтобы промежуточные результаты вычислений округлялись по-банковски. Но стандарт этот касается реализаторов сопроцессоров, и призван лишь обеспечить переносимость программ в смысле одинаковости результатов на разных системах, а про бухгалтерию там ничего нет. Поэтому постановщики и разработчики должны сами проработать этот вопрос, и выбрать подходящий алгоритм. Но чем руководствоваться? Нормативные документы редко опускаются до таких «мелочей». Поэтому на практике обычно спонтанно используют арифметическое либо бухгалтерское округление — какое реализовано в языке, а при расчетах с родным государством — считают доли копейки в его пользу, от греха подальше — иначе дороже выйдет, если проверяющие начнут просчитывать контрольные примеры.

Чтобы отпустить на обед нашего многострадального бухгалтера, обсудим последний на сегодня аспект деления денег. Для программиста он коварен тем, что внешне выглядит как проблема с округлением — несовпадение итога округленных сумм с исходной. Поэтому бухгалтеры нередко берут расчетную ведомость, и, как сказал классик, «ейною мордою начинают мне в харю тыкать». А проблема не касается ни машинной арифметики, ни алгоритма округления. Сформулировать ее можно так: если трое договорились делить доход поровну, а заработали 10 копеек, то как быть с лишней копейкой?

Правильный ответ — решить этот вопрос должна сама бухгалтерия. Вариантов можно предложить три:

  1. Разницу, возникающие в результате ошибок неделимости, следует относить на финансовые результаты. Для выявления суммы разницы сформировать специальный сверочный отчет, (отдельно по расходу и приходу или по видам операций), который показывает точные суммы приходования/списания, и округленные суммы, принятые к учету. На выявленную суммовую разницу следует сделать проводку по бухгалтерской справке.
  2. Оставить эту копейку на этом же бухгалтерском счете как остаток, переходящий на следующий месяц. Если в следующем месяце опять случится та же история, то в остатке останется уже две копейки, а на третий месяц получившиеся двенадцать копеек поделятся без остатка. Этот способ часто использовали во времена инфляции, когда начисление шло с копейками, а в кассе мелочь уже не водилась. Выплачивали до рубля, а копейки оставались на лицевых счетах и переходили на следующий месяц.
  3. Использовать описанный выше способ начисления по цепочке. Помимо вопросов с округлением, он решает и эту проблему. Правда, лишняя копейка будет отдана последнему (а в общем случае — неизвестно кому). Сами решайте, когда это допустимо.

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

Язык Функция арифметического округления Функция бухгалтерского округления
Excel ОКРУГЛ (вызываемая из списка функций для использования в формулах таблицы) Round (функция VBA, используемая в макросах)
FoxPro 2.6 (DOS) ROUND
Perl Math::Round::round Math::Round::round_even
MySQL ROUND — алгоритм зависит от системных библиотек. Может оказаться вовсе не арифметическим и не бухгалтерским.
FLOOR(n * 100 + 0.500001 ) / 100
PostgreSQL ROUND
Delphi SimpleRoundTo (работает с ошибками) RoundTo (работает с ошибками)
RoundTo(n + 0.000001, -2)
StrToFloat(FloatToStr(n, ffFixed, 15, 2))
Trunc(n * 100 + 0.5) / 100 при SetRoundMode(rmUp)
DecimalRoundExt(n, 2, drHalfUp) by John Herbster DecimalRoundExt(n, 2, drHalfEven) by John Herbster

Думаю, наибольшее внимание читателей привлекла строка со встроенными функциями Delphi. Обсудим их.

Прежде всего отметим: на работу функций Delphi сильно влияет установка режима округления процессора командой SetRoundMode. В документации лишь невнятно упомянуто ее влияние на функцию RoundTo, но на самом деле она влияет и на SimpleRoundTo, и вооще практически на все результаты вычислений. В связи с этим категорически не рекомендуется менять режим округления, а при необходимости — делать это лишь кратковременно, и тут же возвращать в значение по умолчанию (rmNearest). Примером нелепого влияния SetRoundMode может служить функция EndOfTheMonth, которая по документации возвращает последний момент текущего месяца, а при SetRoundMode(rmUp) — начинает возвращать первый момент следующего. Приходилось слышать также о проблемах с непонятными ошибками «Invalid floating point operations» внутри ADO, связанные с отличием RoundMode от стандартного.

Итак, согласно документации, SimpleRoundTo реализует арифметическое округление, а RoundTo — банковское. Но на самом деле они вытворяют такие чудеса:

Аргумент Арифм.окр. SimpleRoundTo Банк.окр. RoundTo
0.0150 0.02 0.01 0.02 0.01
0.0250 0.02 0.03
0.0450 0.05 0.04
0.0550 0.06 0.05 0.06 0.05
0.0650 0.06 0.07
0.0750 0.08 0.07 0.08 0.07

Результаты получены на Delphi 7 при режиме округления по умолчанию (rmNearest). Результаты тестирования при других режимах приведены в приложении, но безошибочного поведения согласно какого-либо алгоритма достигнуть так и не удалось.

Вообще, результат RoundTo лишь в 50% случаев округления пятерки совпадает с правилом банковского округления. Статистическая погрешность подавляется отвратительно — набегает 13 руб. 45 коп разницы на миллионе записей. Еще меньше похожа ее подружка SimpleRoundTo на обещанное арифметическое округление — менее 40% совпадений, все ошибки в одну сторону (см. результаты тестов в приложении).

Возникает вопрос: неужели в Borland не знают об этой ошибке? Оказывается, знают еще с августа 2003 года. Соответствущие Public Reports в Quality Central на Borland Developer Network: 5486, 8070, 8143. Кстати, первый же комментарий под заявкой таков: «Кто-нибудь может объяснить, почему они присвоили этой ошибке такой низкий рейтинг?…». Я не могу.

К счастью, нашелся неравнодушный человек по имени John Herbster, который предложил собственную реализацию функций округления, и выложил ее для всеобщего использования. Взять их можно там же, на Borland Developer Network (ссылки под упомянутыми Public Reports, регистрация на BDN бесплатная). В моих тестах они не дали ни одной ошибки, так что всячески рекомендую.

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

Заключение

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

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

Одной из попыток в этом направлении является введение типа Currency, который ведет вычисления с автоматическим округлением промежуточных результатов. Недостатком его является жестко заданная точность (видимо, для вычисления квадратных денег). Есть также смутные сведения о не вполне корректных преобразованиях этого типа в процессе вычислений (приведение к float), что чревато ошибками. Так что этот вопрос ждет своих исследователей.

И еще. Некоторые из функций содержат «волшебные» вставки вроде x + 0.000001. Нередко эти функции показывали безошибочные результаты, и я как честный человек был вынужден об этом сообщить. Но в глубине души я подозреваю, что такие вставки могут привести к ошибкам на других наборах данных. Так что если все же решите их использовать — будьте осторожны. Не нужно забывать, что мы тестировали только положительные числа. На отрицательных, видимо, такие «хвостики» тоже должны быть с минусом. Для меня также непонятен вопрос, не приведут ли такие вставки к систематическому накоплению ошибки при каких-либо условиях. Так что есть о чем задуматься.

Ну и разумеется, хотелось бы выяснить, как обстоят дела с округлением в других продуктах, в частности NET, и других от Microsoft. Если кто-то имеет такие данные — прошу дополнить список.