вычисления степеней, как будет объяснено в разделе 4.6.3, а также при анализе некоторых игр и головоломок. Джузеппе Пеано (Giuseppe Реапо) использовал двоичную систему как базис "логического" алфавита из 256 символов [Atti della R. Accademia delle Scienze di Torino 34 (1898), 47-55]. Джозеф Боуден (Joseph Bowden) предложил систему обозначений для шестнадцатеричных чисел [Special Topics in Theoretical Arithmetic (Garden City, 1936), 49].

В книге Антона Глэйзера (Anton Glaser) History of Binary and Other Nondec-imal Numeration (Los Angeles: Tomash, 1981) приведена подробная информация и практически исчерпывающий анализ развития двоичной системы, включая перевод на английский язык многих работ, процитированных выше (см. Historia Math. 10 (1983), 236-243).

Большинство современных числовых систем связано с развитием вычислительных машин. Из заметок Чарльза Бэббиджа (Charles Babbage) 1838 года понятно, что он задумывался над использованием в своей аналитической машине недесятичных чисел (см. М. V. Wilkes, Historia Math. 4 (1977), 421). Повышенный интерес к механическим устройствам для выполнения арифметических операций, особенно умножения, побудил в 30-х годах ряд исследователей обратить внимание на двоичную систему. Прекрасный отчет об этих исследованиях вместе с записью дискуссии, состоявшейся после прочитанной им на данную тему лекции приведен в статье Э. Уильяма Филлипса (Е. William Phillips) "Двоичные вычисления" [Journai of the Institute of Actuaries 67 (1936), 187-221]. Филлипс начал статью словами "Конечная цель (этой статьи) состоит в том, чтобы убедить весь цивилизованный мир отказаться от десятичной нумерации и заменить ее восьмеричной".

Современные читатели статьи Филлипса, возможно, будут удивлены, обнаружив, что система счисления по основанию 8 называлась в то время в соответствии со всеми словарями анг.нийского языка "octonary" или "octonal", точно так, как система по основанию 10 называлась "denary" или "decimal". Слово "octal" появилось в английском языке только после 1961 года, причем первоначально, скорее всего, как термин для описания конструкции цоколя определенного класса вакуумных электронных ламп. Слово "hexadecimal", которое вкралось в английский язык еще позже, представляет собой смесь греческого и латинского корней. Более корректными терминами должны были быть либо "senidenary", либо "sedecimal", либо даже "sexadecimal", но последний, пожалуй, для программистов звучал бы слишком рискованно.

Высказывание Ф. X. Уэйлса, приведенное в качестве одного из эпиграфов к этой главе, извлечено из записи дискуссии, опубликованной вместе со статьей Филлипса. Другой слушатель лекции указал на неудобства восьмеричной системы для деловых целей: 5% "превращается в 3.1463 per 64, что звучит довольно ужасно"*.

Филлипса вдохновила возможность реализации его идей в устройствах, работающих на электронных лампах и способных выполнять вычисления в двоичном коде [С. Е. Wynn-Williams, Proc. Roy Soc. London A136 (1932), 312-324].

Bo второй половине 30-х годов Джон В. Атанасофф (John V. Atanasoff) и Джордж Р. Штибитц (George R. Stibitz) в США, Л. Куффигнал (L. Couffignal) и Р. Валта (R. Valtat) во Франции, а также Гельмут Шрейер (Helmut Schreyer) и

* Поскольку слово "процент" на английском языке пишется как "per cent" (от лат. "per centum"), а "cent" (100) заменяется числом 64. - Прим. перев.

Конрад Цузе (Konrad Zuse) в Германии разработали первые электромеханические и электронные машины для выполнения арифметических операций. Все они использовали двоичную систему счисления, хотя позже Штибитц разработал и двоичный код "с избытком 3" для десятичных цифр. Обобщенный обзор этих ранних достижений, включая переводы и копии наиболее значимых современных документов, содержится в книге Brian Randell The Origins of Digital Computers (Berlin: Springer, 1973).

В первых быстродействующих вычислительных машинах, созданных в США в начале 40-х годов, использовалась десятичная арифметика. Но в 1946 году в сыгравшем важную роль отчете А. В. Беркса (А. W. Burks), Г. Г. Голдстайна (Н. Н. Gold-stine) и Дж. фон Неймана (J. von Neumann) о проекте первой вычислительной машины с хранимой в памяти программой были подробно изложены причины, которые побудили их порвать с традицией и перейти к системе счисления по основанию 2 (см. John von Neumann, Collected Works 5, 41-65). С тех пор двоичные вычислительные устройства получили всеобщее распространение. После первой дюжины лет работы с двоичными машинами в статье В. Буххольца (W. Buchholz) "Fingers or Fists?" [CACM 2 (December, 1959), 3-11] был выполнен анализ сравнительных достоинств и недостатков двоичной системы счисления.

Структура компьютера MIX, используемого в этой книге, такова, что машина может быть как двоичной, так и десятичной. Интересно отметить, что почти все программы для этого компьютера можно написать, не зная, какая именно система используется (двоичная или десятичная), даже при выполнении вычислений с многократной точностью. Итак, мы видим, что на методику программирования для компьютера выбор основания системы счисления не оказывает значительного влияния. (Заслуживает упоминания исключение из этого правила - операции "булевой" алгебры, рассматриваемые в разделе 7.1; см. также алгоритм 4.5.2.)

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

-12345 67890. (2)

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

В большинстве механических счетных машин, выполняющих действия десятичной арифметики, используется другая система записи-дополнение до десяти**. Если вычесть 1 из 00000 00000, в этой системе записи получим 99999 99999; другими

* в общепринятой русскоязычной терминологии этому понятию соответствует термин прямой код. - Прим. перев.

** В общепринятой русскоязычной терминологии этому понятию соответствует термин дополнительный ко.- Прим. перев.

словами, числу явно не приписывается знак, а вычисления выполняются по модулю 10°. Число -12345 67890 в форме дополнения до десяти будет выглядеть так:

87654 32110. (3)

В этой системе обозначений принято считать отрицательным любое число, головная цифра которого-5, 6, 7, 8 или 9, хотя с точки зрения сложения и умножения не будет большим грехом рассматривать (3), если это удобно, как число -Ь87654 32110. Попутно отметим, что в такой системе не возникает проблема "минус нуль".

На практике основное различие между двумя описанными формами представления заключается в том, что сдвиг вправо дополнения до десяти не эквивалентен делению на 10; к примеру, число -11 = ... 99989 после сдвига вправо на одну позицию превращается в ... 99998 = - 2 (в предположении, что сдвиг вправо отрицательного числа порождает в головном разряде "9"). В общем случае результатом сдвига числа X, записанного в формате дополнения до десяти, на одну позицию вправо будет число [x/lOJ, независимо от того, положительно или отрицательно число х.

Одним из возможных неудобств записи в формате дополнения до десяти является несимметричность относительно нуля. Наибольшее отрицательное число, представимое р цифрами, есть 500... О, и оно не является результатом обращения знака никакого р - разрядного положительного числа. Таким образом, возможно, изменение знака, т. е. замена х на -х, приведет к переполнению. (См. упр. 7 и 31, в которых обсуждается формат дополнения до основания системы счисления, который имеет бесконечную точность.)

Еще одна система обозначений, принятая с самых первых дней эры быстродействующих вычислительных машин, - это представление в виде дополнения до всех девяток*.

В этом случае число -12345 67890 записывается в виде

87654 32109. (4)

Каждая цифра отрицательного числа (-х) равна разности между 9 и соответствующей цифрой числа X. Нетрудно видеть, что для отрицательного числа дополнение до девяти всегда на единицу меньше соответствующего дополнения до десяти. Сложение и вычитание производятся по модулю 10° - 1, а это означает, что перенос из крайней слева позиции добавляется к крайней справа (см. описание арифметики по модулю W - I в разделе 3.2.1.1). Опять возникает проблема с "минус нулем", так как записи 99999 99999 и 00000 00000 обозначают одно и то же значение.

Только что изложенные идеи для арифметики по основанию 10 в полной мере применимы и к арифметике по основанию 2; здесь .мы имеем абсолютную величину со знаком, дополнение до двух и дополнение до одного**.

Арифметика в дополнительном коде - это арифметика по модулю 2", а арифметика в обратном коде - по модулю 2" - 1. Машина MIX имеет дело только с прямым кодом, что и используется в примерах этой главы. Тем не менее в сопроводитель-

* в общепринятой русскоязычной терминологии этому понятию соответствует термин обратный код. - Прим. перев.

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