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

Скрупулезные читатели и редакторы английского текста, вероятно, отметили положение апострофа в терминах "twos complement" (дополнение до двойки) и "ones complement" (дополнение до единиц). В первом случае каждая цифра дополняется до первой степени двойки, а во втором весь код есть дополнение до кода, представленного единицами во всех разрядах. По аналогии с "ones complement" может существовать и формат "twos complement" (дополнение До двоек), который используется в системе счисления по основанию 3 и является дополнением До(2...22)з.

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

Легко видеть, что между записью чисел в системах по основанию Ь и Ь* существует простая связь:

{...a3a2aiao.a-ia-2...)b = (... АзЛгЛхЛо.А-хЛ-г .. .)бА:, (5)

Aj = {akj+k-i • • • o,kj+iakj)b

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

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

(. . . 03020100.0-10-2 . . . )-10

= + аз(-10) + О2(-10)2 + Oi(-lO) +ао + ---

=----ЮООоз + 100о2 - lOoi -Юо - io-i + т5оа-2----

Здесь, как и в традиционной десятичной системе, цифры удовлетворяют неравенствам О < Ofc < 9. Число 12345 67890 запишется в такой "негадесятичной" системе в виде

(1 93755 73910) 1о, (6)

так как оно равно как раз 10305070900 - 9070503010. Интересно отметить, что обращение этого числа, -12345 67890, запишется в виде

(28466 48290) 1о. (7)

И действительно, любое вещественное число, положительное или отрицательное, может быть представлено без знака в системе по основанию -10.

Системы по отрицательному основанию впервые описаны Витторио Грюнваль-дом (Vittorio Grunwald) в Giornale di Matematiche di Battaglini 23 (1885), 203-221, 367. В этой работе изложены правила выполнения в таких системах четырех арифметических действий, а также рассмотрены правила извлечения корня, проверка делимости и перевод из одной системы счисления в другую. Однако, похоже, работа Грюнвальда осталась незамеченной, так как она была опубликована в довольно заштатном журнале и вскоре забыта. Следующее исследование по системам счисления по отрицательному основанию опубликовал О. Дж. Кемпнер (А. J. Kempner) в АММ 43 (1936), 610-617. В этой работе он рассмотрел свойства систем счисления с нецелыми основаниями и отметил в примечаниях, что системы счисления с отрицательными основаниями также будут иметь право на существование. Двадцать лет спустя эта идея снова была предложена; на этот раз - 3. Павляком (Z. Pawlak) и А. Вакуличем (А. Wakulicz) [Bulletin de VAcademie Polonaise des Sciences, Classe III, 5 (1957), 233-236; Serie des sciences techniques 7 (1959), 713-721], a также Л. Уэйделом (L. Wadel) [IRE Transactions EC-6 (1957), 123]. Экспериментальные вычислительные машины SKRZAT 1 и BINEG, в которых -2 использовалось в качестве основания системы, были сделаны в Польше в конце 50-х годов (см. N. М. Blachman, САСМ 4 (1961), 257; R. W. Marczynski, Ann. Hist. Computing 2 (1980), 37-48). Дополнительные ссылки на литературу приводятся в журналах IEEE Transactions ЕС-12 (1963), 274-276; Computer Design 6 (May, 1967), 52-63. Можно полагать, что идея отрицательного основания возникла независимо сразу у целого ряда авторов. Например, Д. Э. Кнут в небольшом машинописном тексте, предназначенном для конкурса "Поиск научных талантов" среди учеников старших классов, в 1955 году обсуждал системы счисления с отрицательными основаниями. Там же обсуждалось и дальнейшее распространение этой идеи на основания, являющиеся комплексными числами.

Выбор основания 2г приводит к интересной системе счисления, которую естественно назвать "мнимочетверичной" (по аналогии с "четверичной"). Такая система обладает необычным свойством, заключающимся в том, что в ней любое комплексное число может быть представлено без знака при помощи цифр 0,1,2 и 3. (См. D. Е. Knuth, САСМ 3 (1960), 245-247.) Например,

(11210.31)2t = 1 • 16 -fl (-8г) + 2 (-4) + 1 (2г) + 3 • {-i) + = 7 - 7г.

Здесь число (оап • • • aiOo-O-i • • • а-2л)2г равно

(а2„ .. .0200-0-2 • • •о 2л)-4 + 2г(а2п-1 • • .0301.0-1 . ..a-2k+i)-4,

так что перевод числа в мнимочетверичную форму и обратно сводится к переводу в "негачетверичную" форму и обратно действительной и мнимой частей числа. Интересное свойство этой системы заключается в том, что она позволяет единообразно

выполнять умножение и деление комплексных чисел без разделения действительной и мИимой частей. Например, в этой системе можно перемножить два числа так же, как при любом другом основании, но при этом нужно использовать несколько иное "правило переноса": в случае, если цифра становится больше 3, вычесть 4 - и -1 "перенесется" на два разряда влево; когда же цифра отрицательна, к ней прибавляется 4 и +1 "переносится" на два разряда влево. Проиллюстрируем это своеобразное правило переноса следующим примером.

1 2 2 3 1 [9 - Юг]

1 2 2 3 1 [9 - Юг]

1 2 2 3 1

1 0 3 2 0 2 1 3

1 3 0 2 2 1 3 0 2 2

1 2 2 3 1

0 2 1 3 3 3 1 2 1 [-19 - 180г]

Аналогичную систему, в которой используются лишь цифры О и 1, можно построить и по основанию \/2г. Однако в ней для представления мнимой единицы г требуется бесконечное непериодическое разложение. Витторио Грюнвальд (Vittorio Grunwald) предложил разрешить эту проблему, используя цифры О и 1/\/2 в нечетных позициях, однако это фактически испортило всю систему. (См. Commentari deWAteneo di Brescia (1886), 43-54.)

Используя основание г - 1, можно также получить "бинарную" комплексную систему счисления, предложенную У. Пенни (W. Penney) [JACM 12 (1965), 247-248]:

(.. .a4a3a2aiao-a-i • ••)<-!

=----4а4 + {2 + 21)аз - 2ia2 + (i-l)ai -Юо - (i41)a i + •• •.

В ней задействованы только цифры О и 1. Продемонстрировать, что любое комплексное* число допускает такое представление, можно, рассмотрев интересное множество S, приведенное на рис. 1. Это множество по определению состоит из всех точек, которые могут быть записаны в виде Х>1а(г - 1)"* для бесконечной последовательности Qi, «2, о.з, • • нулей и единиц. Она известна также как "двуглавый дракон" (см. М. F. Barnsley, Fractals Everywhere, second edition (Academic Press, 1993), 306, 310). Ha рис. 1 показано, что множество 5 можно разбить на 256 частей, конгруэнтных jS. Заметим, что если множество 5 повернуть по часовой стрелке на 135°, то оно распадется на два примыкающих одно к другому множества, конгруэнтных (1/\/2) S, поскольку (г - 1)S = S U {S + I). Детально доказательство того, что множество 5 содержит все комплексные числа, достаточно малые по модулю, рассмотрено в упр.18.

Быть может, самой изящной из всех систем счисления является уравновешенная троичная система счисления (по основанию 3), в которой вместо цифр О, 1 и 2 используются "триты" (троичные цифры) -1, О и +1. Заменив -1 символом 1, получим следующие примеры уравновешенных троичных чисел.