в более общих ситуациях приходится прибегать ко всяким хитростям, потому что переполнение при округлении может происходить даже во время выполнения команды FLOT.

Аналогично предположим, что MIX имеет команду FADD, но не имеет FIX. Чтобы округлить число и, записанное в формате с плавающей точкой, до ближайшего целого числа с фиксированной точкой (причем известно, что число неотрицательно и займет не более трех байтов), в программе можно записать

FADD FUDGE, где в ячейке FUDGE содержится константа

результат в гА будет иметь вид

(13)

D. История и библиография. Истоки арифметики чисел с плавающей точкой прослеживаются вплоть до вавилонян (около 1800 г. до н. э. или ранее), которые применяли арифметические операции над числами с плавающей точкой по основанию 60, но не имели обозначения для порядка. Нужный порядок всегда некоторым образом "подразумевался" тем, кто производил вычисления. По крайней мере в одном случае обнаружено, что у вавилонян получился ошибочный ответ, потому что сложение осуществлялось при неверно выполненном выравнивании операндов, однако это случалось весьма редко (см. О. Neugebauer, The Exact Sciences in Antiquity (Princeton, N. J.: Princeton University Press, 1952), 26-27). Другой пример раннего обращения к формату с плавающей точкой связан с именем греческого математика Аполлония (3 в. до н. э.), который, по-видимому, был первым, кто объяснил, как можно упростить умножение, по крьйней мере в простых случаях, собирая степени 10 отдельно от их коэффициентов. Метод Аполлония обсуждается в труде Паппа Александрийского "Математическое собрание" (4 в. н. э.). После гибели вавилонской цивилизации представление с плавающей точкой существенным образом, использовалось для формирования произведений и частных лишь много веков спустя, когда были открыты логарифмы (1600 г.) и вскоре после этого Отред (Oughtred) изобрел логарифмическую линейку (1630 г.). Примерно в тот же период бьшо введено современное обозначение " i" " для порядков; отдельные символы для квадрата х, куба i и т. д. использовались и раньше.

Арифметика с плавающей точкой была включена в конструкцию некоторых из самых ранних вычислительных машин. Это было независимо предложено Леонардо Торресом-и-Овьедо (Leonardo Torres у Quevedo) в Мадриде (1914 г.), Конрадом Цузе (Konrad Zuse) в Берлине (1936 г.) и Джорджем Стибицем (George Stibitz) в Нью-Джерси (1939 г.). В машине Цузе использовалось двоичное представление с плавающей точкой, которое он назвал полулогарифмической нотацией; он также реализовал соглашение относительно операций с некоторыми особыми величинами, подобными "оо" и "не определено". Первой американской вычислительной машиной, в которой появились средства для выполнения операций в формате с плавающей точкой, была Модель V (Bell Laboratories), за которой последовала гарвардская машина Марк П. Обе эти машины, спроектированные в 1944 году.

были релейными вычислительными устройствами. [См. В. Randell, The Origins of Digital Computers (Berlin: Springer, 1973), 100, 155, 163-164, 259-260; Proc. Symp. Large-Scale Digital Calculating Machinery (Harvard, 1947), 41-68, 69-79; Datamation 13 (April, 1967), 35-44 (May, 1967), 45-49; Zeit. fur angew. Math, und Physik 1 (1950), 345-346.]

Использование двоичных чисел с плавающей точкой серьезно обсуждалось в 1944-1946 годах группой исследователей из Школы Мура (Moore School) в связи с планами создания первой электронной вычислительной машины, но оказалось, что на лампах электронную схему, реализующую арифметику с плавающей точкой, выполнить гораздо труднее, чем на реле. Конструкторы первых электронных машин поняли, что масштабирование - это целая проблема в программировании, но они чувствовали, что это всего лишь небольшая часть общей работы по программированию в те годы. Конечно, масштабирование в явном виде чисел с фиксированной запятой казалось вполне окупающим затраченные время и усилия, поскольку программист при этом вынужден был все время держать вычисления в поле зрения и заботиться об их точности. Далее конструкторы возражали, что при представлении чисел с плавающей точкой занимается ценное место в памяти, так как нужно хранить порядки. Кроме того, схемотехнические решения арифметики с плавающей точкой трудно приспособить к вычислениям с многократной точностью. [См. von Neumanns Collected Works 5 (New York: Macmillan, 1963), 43, 73-74.] Конечно же, в это время они создавали машину, которая была первой машиной с хранимой в памяти программой и второй электронной машиной, и им предстояло выбрать формат либо с фиксированной, либо с плавающей точкой, но не оба сразу. Они предвосхитили составление программ двоичной арифметики с плавающей точкой, и команды "сдвиг влево" и "сдвиг вправо" фактически были введены в эти машины, главным образом, с целью повышения их эффективности. Первой машиной, которая имела средства для выполнения арифметических операций с обоими форматами, была, по-видимому, ЭВМ, разработанная фирмой "Дженерал Электрик" [см. Proc. 2nd Symp. Large-Scale Digital Calculating Machinery (Cambridge, Mass.: Harvard University Press, 1951), 65-69].

Подпрограммы для работы в формате с плавающей точкой, интерпретирующие системы для ранних ЭВМ, были составлены Д. Дж. Уилером (D. J. Wheeler) и другими и впервые опубликованы в книге Wilkes, Wheeler, Gill, The Preparation of Programs for an Electronic Digital Computer (Reading, Mass.: Addison-Wesley, 1951) (cm. подпрограммы Al-AU). Интересно отметить, что в ней описаны программы для десятичного представления с плавающей точкой, хотя использовалась двоичная ЭВМ; другими словами, числа представлялись в виде 10/, а не 2/, и поэтому для операций сдвига требовались умножения или деления на 10. На этой машине десятичное масштабирование выполнялось почти так же просто, как сдвиг, а десятичное представление значительно упрощало ввод-вывод.

Авторы большинства публикаций при описании деталей реализации подпрограмм арифметики ссылаются на технические отчеты многочисленных производителей компьютеров, но иногда встр>ечаются ссылки на открытые источники. Помимо упомянутых выше работ, определенный исторический интерес представляют следующие: R. Н. Stark and D. В. MacMillan, Math. Сотр. 5 (1951), 86-92, в которой описана программа, "прошитая" на специальной сменной панели; D. МсСгаскеп,

Digital Computer Programming (New York: Wiley, 1957), 121-131; J. W. Carr III, CACM-2,5 (May, 1959), 10-15; W. G. Wadey, JACM 7 (1960), 129-139; D. E. Knuth, JACM 8 (1961), 119-128; 0. Kesner, CACM 5 (1962), 269-271; F. P. Brooks and K. E. Iverson, Automatic Data Processing (New York: Wiley, 1963), 184-199. Дискуссия относительно арифметики с плавающей точкой с точки зрения разработчиков компьютеров представлена в работах S. G. Campbell, "Floating point operation" в Planning a Computer System, edited by W. Buchholz (New York: McGraw-Hill, 1962), 92-121, A. Padegs, IBM Systems J. 7 (1968), 22-29. Дополнительный список источников, в основном, имеющих отношение к анализу точности вычислений в формате с плавающей точкой, представлен в разделе 4.2.2.

Поистине революционные изменения в аппаратной реализации арифметики с плавающей точкой произошли, когда большинство изготовителей компьютеров приняли к исполнению стандарт ANSI/IEEE Standard 754 в конце 80-х годов. (См. ШЕЕ Micro 4 (1984), 86-100; W. J. Cody, Сотр. Sci. и Statistics: Symp. on the Interface 15 (1983), 133-139; W. M. Kahan, Mini/Micro West-83 Conf Record (1983), Paper 16/1; D. Goldberg, Computing Surveys 23 (1991), 5-48, 413; W. J. Cody and J. T. Coonen, ACM Trans. Math. Software 19 (1993), 443-451.)

Компьютер MMIX, который заменит MIX в следующем издании данной книги, будет полностью соответствовать этому стандарту.

УПРАЖНЕНИЯ

1. [10] Как будут выглядеть число Авогадро и постоянная Планка (3), если их представить в виде четырехразрядных чисел с плавающей точкой по основанию 100 с избытком 50? (Именно таким было бы представление в машине MIX, как в (4), если бы размер байта равнялся 100.)

2. [12] Предположим, порядок е находится в интервале О < е < R Каковы наибольшее и наименьшее положительные значения, которые могут быть записаны как р-разрядные числа с плавающей точкой по основанию b с избытком д? Каковы наибольшее и наименьшее положительные значения, которые могут быть представлены в виде таких нормализованных чисел?

3. [11] (К. Цузе (К. Zuse), 1936.) Покажите, что, работая с нормализованными двоичными числами с плавающей точкой, можно немного увеличить точность без увеличения объема используемой памяти: р-разрядную дробную часть можно представлять при помощи всего лишь р - 1 разрядов машинного слова, если чуть-чуть уменьшить интервал значений порядка.

► 4. [16] Пусть 6 = 10, р = 8. Какой результат даст алгоритм А для операции (50,4-.98765432) ф (49, -f-.ЗЗЗЗЗЗЗЗ), для операции (53, -.99987654) ф (54, -f-.lOOOOOOO) и для операции (45, -.50000001) ф (54, -f-.lOOOOOOO)?

► 5. [24] Будем говорить, что ж ~ у (по отношению к данному основанию Ь), если хну - действительные числа, удовлетворяющие следующим условиям:

[х/Ь\ = [y/bj; X mod 6 = 0 у mod 6 = 0;

0<xmod6<i6 0<j/mod6<i6;

xmod6=i6 j/mod 6 =56;

\Ъ<хтод.Ъ<Ъ \Ь <ymoAh <Ь.