Заложники COBOL и математика. Часть 1 +64


Посмотрим правде в глаза: никто не любит дробные числа — даже компьютеры.

Когда речь заходит о языке программирования COBOL — первый вопрос, который всплывает у всех в голове, всегда выглядит так: «Почему человечество всё ещё использует этот язык во множестве жизненно важных областей?». Банки всё ещё пользуются COBOL. Около 7% ВВП США зависит от COBOL в деле обработки платежей от CMS. Налоговая служба США (IRS), как всем хорошо известно, всё ещё использует COBOL. В авиации тоже используется этот язык (отсюда я узнала одну интересную вещь на эту тему: номер бронирования на авиабилетах раньше был обычным указателем). Можно сказать, что множество весьма серьёзных организаций, идёт ли речь о частном или государственном секторе, всё ещё используют COBOL.



> Вторая часть

Автор материала, первую часть перевода которого мы сегодня публикуем, собирается найти ответ на вопрос о том, почему COBOL, язык, который появился в 1959 году, всё ещё настолько распространён.

Почему COBOL всё ещё жив?


Традиционный ответ на этот вопрос глубоко циничен. Организации — это лень, некомпетентность и тупость. Они гонятся за дешевизной и не склонны к тому, чтобы вкладывать деньги в переписывание своих программных систем на чём-то современном. В целом можно предположить, что причина того, что работа столь значительного количества организаций зависит от COBOL, представляет собой комбинацию инерции и недальновидности. И в этом, конечно, есть доля истины. Переписывание больших объёмов запутанного кода — это масштабная задача. Это дорого. Это сложно. И если существующее ПО, по-видимому, работает хорошо, у организации не будет особенно сильной мотивации для инвестирования в проект по обновлению этого ПО.

Всё это так. Но когда я работала на IRS ветераны COBOL рассказывали о том, что они пытались переписать код на Java и оказалось, что Java не может правильно выполнять вычисления.

Для меня это звучало крайне странно. Настолько странно, что у меня сразу же возникла паникёрская мысль: «Господи, значит IRS округляла всем налоговые платежи в течение 50 лет!!!». Я просто не могла поверить в то, что COBOL способен обойти Java в плане математических вычислений, необходимых IRS. В конце концов — людей-то в космос они не запускали.

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

Над какими «i» надо расставить точки?


Я сейчас немного отойду от рассказа о COBOL и расскажу о том, как компьютеры хранили информацию до того, как двоичное представление данных стало стандартом де-факто (а вот материал о том, как пользоваться интерфейсом z/OS; это — нечто особенное). Я так думаю, что в деле рассмотрения нашего вопроса полезно будет уклониться от основной темы в эту сторону. В вышеупомянутом материале я рассказывала о различных способах использования двоичных переключателей для хранения чисел в двоичной, троичной, десятичной системах счисления, для хранения отрицательных чисел — и так далее. Единственное, чему я не уделила достаточно внимания — это то, как хранятся десятичные числа.

Если бы вы проектировали собственный двоичный компьютер — то вы могли бы начать работу с принятия решения о том, что будете пользоваться двоичной системой счисления. Биты слева от точки представляют целые числа — 1, 2, 4, 8. А биты справа — дробные числа — 1/2, 1/4, 1/8…


2.75 в двоичном представлении

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


Я выбрала расстояния между цифрами на глаз — просто чтобы продемонстрировать мою идею

Разницу между числами несложно вычислить самостоятельно. Например, расстояние между 1/16 и 1/32 — это 0.03125, но расстояние между 1/2 и 1/4 — это уже 0.25.

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

Это иллюстрирует классический пример числа 0.1 (одна десятая). Как представить это число в двоичном формате? 2-1 — это 1/2, или 0.5. Это — слишком большое число. 1/16 — это 0.0635. Это — слишком мало. 1/16+1/32 — это уже ближе (0.09375), но 1/16+1/32+1/64 — это уже больше, чем нам нужно (0.109375).

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

Тут вы можете сказать себе: «А почему бы нам просто не сохранить 0.1 точно так же, как мы храним число 1? Число 1 мы можем сохранить без всяких проблем — так давайте просто уберём десятичную точку и будем хранить любые числа так же, как храним целые числа».

Это — отличное решение данной проблемы за исключением того, что оно требует фиксации двоичной/десятичной точки в некоем заранее заданном месте. В противном случае числа 10.00001 и 100000.1 будут выглядеть совершенно одинаково. Но если точка зафиксирована так, что на дробную часть числа выделено, скажем, 2 знака, то мы можем округлить 10.00001 до 10.00, а 100000.1 превратится 100000.10.

Только что мы «изобрели» числа с фиксированной точкой.

С представлением разных значений с помощью чисел с фиксированной точкой мы только что разобрались. Делать это просто. Можно ли, используя числа с фиксированной точкой, облегчить решение ещё каких-нибудь задач? Вспомним тут о наших хороших друзьях — о двоично-десятичных числах (Binary Coded Decimal, BCD). Кстати, чтобы вы знали, именно эти числа используются в большинстве научных и графических калькуляторов. От этих устройств, что совершенно ясно, ждут правильных результатов вычислений.


Калькулятор TI-84 Plus

Рекуррентное соотношение Мюллера и Python


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

COBOL был создан как язык, в котором, по умолчанию, используются числа с фиксированной точкой. Но значит ли это, что COBOL лучше современных языков подходит для выполнения математических вычислений? Если мы зацепимся за проблему наподобие результата вычисления значения 0.1+0.2 — то может показаться, что на предыдущий вопрос надо ответить «да». Но это будет скучно. Поэтому давайте пойдём дальше.

Мы собираемся поэкспериментировать с COBOL, используя так называемое рекуррентное соотношение Мюллера (Muller’s Recurrence). Жан-Мишель Мюллер — это французский учёный, который, возможно, сделал важнейшее научное открытие в сфере информационных технологий. Он нашёл способ нарушить правильность работы компьютеров с использованием математики. Я уверена, что он сказал бы, что изучает проблемы надёжности и точности, но нет и ещё раз нет: он создаёт математические задачи, которые «ломают» компьютеры. Одна из таких задач — это его рекуррентная формула. Выглядит она так:


Этот пример взят отсюда

Формула совсем не кажется страшной. Правда? Эта задача подходит для наших целей по следующим причинам:

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

Вот небольшой скрипт на Python, которые вычисляет результаты рекуррентного соотношения Мюллера, используя числа с плавающей и фиксированной точкой:

from decimal import Decimal
def rec(y, z):
 return 108 - ((815-1500/z)/y)
 
def floatpt(N):
 x = [4, 4.25]
 for i in range(2, N+1):
  x.append(rec(x[i-1], x[i-2]))
 return x
 
def fixedpt(N):
 x = [Decimal(4), Decimal(17)/Decimal(4)]
 for i in range(2, N+1):
  x.append(rec(x[i-1], x[i-2]))
 return x
N = 20 
flt = floatpt(N)
fxd = fixedpt(N)
for i in range(N):
 print str(i) + ' | '+str(flt[i])+' | '+str(fxd[i])

Вот что получается в результате работы этого скрипта:

i  | floating pt    | fixed pt
-- | -------------- | ---------------------------
0  | 4              | 4
1  | 4.25           | 4.25
2  | 4.47058823529  | 4.4705882352941176470588235
3  | 4.64473684211  | 4.6447368421052631578947362
4  | 4.77053824363  | 4.7705382436260623229461618
5  | 4.85570071257  | 4.8557007125890736342039857
6  | 4.91084749866  | 4.9108474990827932004342938
7  | 4.94553739553  | 4.9455374041239167246519529
8  | 4.96696240804  | 4.9669625817627005962571288
9  | 4.98004220429  | 4.9800457013556311118526582
10 | 4.9879092328   | 4.9879794484783912679439415
11 | 4.99136264131  | 4.9927702880620482067468253
12 | 4.96745509555  | 4.9956558915062356478184985
13 | 4.42969049831  | 4.9973912683733697540253088
14 | -7.81723657846 | 4.9984339437852482376781601
15 | 168.939167671  | 4.9990600687785413938424188
16 | 102.039963152  | 4.9994358732880376990501184
17 | 100.099947516  | 4.9996602467866575821700634
18 | 100.004992041  | 4.9997713526716167817979714
19 | 100.000249579  | 4.9993671517118171375788238

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

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

Неприятность заключается в том, что объём оперативной памяти, который имеется у компьютеров, не бесконечен. Поэтому невозможно хранить бесконечное количество десятичных (или двоичных) позиций. Вычисления с фиксированной точкой могут быть точнее вычислений с плавающей точкой в том случае, если есть уверенность в том, что низка вероятность того, что понадобится больше чисел после точки, чем это предусматривает используемый формат. Если число в этот формат не поместится — оно будет округлено. Надо отметить, что ни вычисления с фиксированной точкой, ни вычисления с плавающей точкой не защищены от проблемы, которую демонстрирует рекуррентное соотношение Мюллера. И те и другие в итоге дают неверные результаты. Вопрос заключается в том — когда это происходит. Если увеличить число итераций в Python-скрипте, например, с 20 до 22, то итоговое число, полученное при вычислениях с фиксированной точкой, составит 0.728107. 23 итерации? -501.7081261. 24? 105.8598187.

В разных языках эта проблема проявляется по-разному. Некоторые, вроде COBOL, позволяют работать с числами, параметры которых заданы жёстко. А в Python, например, есть значения по умолчанию, которые могут быть настроены в том случае, если у компьютера есть достаточно памяти. Если мы добавим в нашу программу строчку getcontext().prec = 60, сообщив десятичному модулю Python о том, чтобы он использовал бы 60 позиций после точки, а не 28, как делается по умолчанию, то программа сможет без ошибок выполнить 40 итераций рекуррентного соотношения Мюллера.

Продолжение следует…

Уважаемые читатели! Сталкивались ли вы с серьёзными проблемами, возникшими из-за особенностей вычислений с плавающей точкой?




К сожалению, не доступен сервер mySQL