Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 64
Текст из файла (страница 64)
О, и оно не является результатом обращения знака никакого р — разрядного положительного числа. Таким образом, возможно, изменение знака, т. е. замена х на — к, приведет к переполнению. (См. упр. 7 и 31, в которых обсуждается формат дополнения до основания системы счисления, который имеет бесконечную точность.) Вше одна система обозначений, принятая с самых первых дней эры быстродействующих вычислительных машин, — это представление в виде дополнения до всех дев В этоы случае число — 12345 67890 зэлисывается в виде (4) 87654 32109.
Каждая цифра отрицательного числа (-х) равна разности между 9 и соответствующей цифрой числа х. Нетрудно видеть. что для отрицательного числа дополнение до девяти всегда на единицу меньше соответствующего дополнения до десяти. Сложение и вычитание производятся по ьсодулю 10'о — 1„а это означает, что перенос из крайней слева позиции добавляетгя к крайней справа (см. описание арифметики по модулю ю — 1 в разделе 3.2.1.1).
Опять возникаег проблема с 'минус нулем'", так как записи 99999 99999 и 00000 00000 обозначают одно и то же значение. Только что изложенные идеи для арифметики по основанию 10 в полной мере применимы и к арифметике по основанию 2; здесь мы имеем абсолюпзную величину со знаком, дополнение до доул и дополнение до одного**. Арифметика в дополнительном коде — это арифметика по модулю 2", а арифметика в обратном коде — по модулю 2" — 1, Машина ИХХ имеет дело только с прямым кодом, что и используется в примерах этой главы. Тем не менее в сопроводитель- ' В общепринятой русскоизычной терминологии етому ионятию соответствует термнк обрягннмй иое.
— Прим. нерее. '* В обгдеоринятой русскоязычной терминологии этим понятиям соответствуют термины ирлмой, обратный н донолннтельнмй код, которыми мы будем пользоваться в дельнейюем. — Прион. иерее, ном тексте рассматриваются, если в этом есть необходимость, и альтернативные варианты процедур для дополнительного и обратного кодов, Скрупулезные читатели и редакторы английского текста, вероятно, отметили положение апострофа в терминах "сзго'з сошр)ешепг" (дополнение до двойки) н "опез' согар!ешепь" (дополнение до единиц). В первом случае каждая цифра дополняется до первой степени двойки, а во втором весь код есть дополнение до кода, представленного единицами во всех разрядах.
По аналогии с "опез' сошр!ешепг" может существовать и формат "змоз' сошр!ешепг" (дополнение до двоек), который используется в системе счисления по основанию 3 и является дополнением до (2...22)з. В руководствах по машинному языку программирования часто указывается, что схемотехника компьютера позволяет настраивать конкретное положение разделяющей точки в каждом машинном слове. На это сообщение не стоит обращать внимание.
Целесообразнее изучить правила размещения разделяющей точки в результате выполнения каждой конкретной команды, если предположить, что до ее выполнения точки в операндах бььли расположены в каком-то определенном месте. Например, в случае машины И1Х можно было бы рассматривать наши операнды либо как целые числа с разделяющей точкой в крайнем справа положении, либо как правильные дроби с разделяющей точкой в крайнем слева положении, либо как некоторые промежуточные варианты.
Правила установки разделяющей точки после осуществления операций сложения, вычитания, перемножения и деления определяются очевидным образом и следуют из алгоритмов выполнения этих операций. Легко видеть, что между записью чисел в системах по основанию Ь и 5ь существует простая связь: (...азагаьао.а ьа г...)ь = ( ° ° АзАгАьАо.А-зА-г ° ° )ь (5) Аг = (аьв+ь ь ...аь1+ьаьу)ь (см. упр. 8). Таким образом, получается простой способ перехода "чисто визуэль- ного" от, скажем, двоичной системы к шестнадцатеричной.
Помимо стандартных систем по основанию 5, обсуждавшихся выше, существует множество других интересных вариантов позиционных систем счисления. Например, можно было бы рассматривать числа по основанию (-10), так что ( - азазагао а-ьа-г ° ° )-ьо + аз(-10) + аг(-10) + аз(-10)' + ао з-.. — 1000аз + 100аг — 10аг + ао — го а ь + ~~а г — ' ' Здесь, как и в традиционной десятичной системе, цифры удовлетворяют неравенствам 0 < аь < 9. Число 12345 67890 запишется в такой "негадесятичной" системе в виде (1 93755 73910)-го, (6) так как оно равно как раз 10305070900 — 9070503010. Интересно отметить, что обращение этого числа, -12345 67890, запишется в виде (7) (28466 48290)-)о.
И действительно, любое вещественное число, положительное или отрицательное, может быть представлено без знака в системе по основанию -10. Системы по отрицательному основанню впервые описаны Витторио Грюнвальдом (У!!Гог!о Огппэга)4) в Сюгпа!е й Магетаг!сйе г(! Ваггай!!и! 23 (1885), 203- 221, 367. В этой работе изложены правила выполнения в таких системах четырех арифметических действий, а также рассмотрены правила извлечения корня, проверка делимости и перевод нз одной системы счисления в другую. Однако, похоже, работа Грюнвальда осталась незамеченной, так как она была опубликована в довольно заштатном журнале и вскоре забыта. Следующее исследование по системам счисления по отрицательному основанию опубликовал О, Дж.
Кемпнер (А. Л. Кешрпег) в АММ 43 (1936), 610-617. В этой работе он рассмотрел свойства систем счисления с нецелымн основанкямн и отметил в примечаниях, что системы счисления с отрицательными основаниями также будут иметь право на существование. Двадцать лет спустя эта идея снова была предложена; на этот раз — 3. Павляком (2. Ран!а)г) н А. Вакуличем (А.
ЪЧакп1!сх) (Вийейп Не !'Аслот!е Ро!опа!эе йм Яс!епсеэ, С!аээе 1П, 6 (1957), 233-236; 84Пе деэ эс!епсеэ гесйп!с!пеэ 7 (1959), 713-72Ц, а также Л. Уэйделом (! . %5м)е1) (ЖЕ ТгапэасПопз ЕС-6 (1957) „123). Экспериментальные вычислительные машины ЯК112АТ 1 п В1!ЧЕС, в которых — 2 использовалось в качестве основания системы, были сделаны в Польше в конце 50-х годов (см. Н.
М. В!аспшап, САСМ 4 (1961), 257; В.. %'. ЫагсхуйэЫ, Апп. Ниа Сошри!!пя 2 (1980), 37 — 48). Дополнительные ссылки на литературу приводятся в журналах 1ЕЕЕ ТгэлэасНопи ЕС-12 (1963), 274-276; Сотрпгег Вез!8п 6 (Ыау, 1967), 52-63. Можно полагать, что идея отрицательного основания возникла независимо сразу у целого ряда авторов. Например, Д. Э, Кнут в небольпюм машинопнсном тексте, предназначенном для конкурса "Поиск научных талантов" среди учеников старших классов, в 1955 году обсуждал системы счисления с отрицательными основаниями.
Там же обсуждалось и дальнейшее распространение этой идеи на основания, являющиеся комплексными числами. Выбор основания 2! приводит к интересной системе счисления, которую естественно назвать "мнимочетвернчной" (по аналогии с "четверичной"). Такая система обладает необычным свойством, заключающимся в том, что в ней любое комплексное число может быть представлено без знака при помощи цифр О, 1, 2 н 3. (См. П. Е.
Кппгй, САСМ 3 (1960), 245-247,) Например, (11210.31)м = 1 16 + 1 . ( — 8!) + 2 (-4) + 1 (2!) + 3 ( — -'!) + 1(--') = 7э — 7-'!. Здесь число (аэ„...а~но.а ~...а гь)ьч равно (пээ .сэпо.о з...о ть) э+2!(пэ -~ азама ь ...а эьь~)-~ так что перевод числа в мнимочетверичную форму и обратно сводится к переводу в "негачетверичную" форму и обратно действнтельной н мнимой частей числа. Интересное свойство этой системы заключается в том, что она позволяет единообразно выполнять умножение и деление комплексных чисел без разделения действитечьной и мнимой частей. Например, в этой системе можно перемножить два числа так же, как при любом другом основании, но при этом нужно использовать несколько иное "правило переноса": в случае, если цифра становится больше 3, вычесть 4— и -1 "перенесется" на два разряда влево; когда же цифра отрицательна, к ней прябавляется 4 и +1 "переносится" на два разряда влево, Проиллюстрируем это своеобразное правило переноса следующим примером.
[9 — 10![ [9 — 104[ 12231 12231 12231 10320213 13022 13022 12231 021333121 [-19 — 180() Аналогичную систему, в которой используются лишь цифры О и 1, можно построить и по основанию Я1. Юднако в ней для представления мнимой единицы ! требуется бесконечное непериодическое разложение. Витторио Грюнвальд (У!ссог)о Сгпптга!6) предложил разрешвть зту проблему, используя цифры 0 н 1/~/2 в нечетных позициях, однако это фактически испортило всю систему. (См.
Соттепгаг! де!!'А!впво с9 Вгезс!а (1886), 43-54.) Используя основание ! — 1, можно также получить "бинарную" комплексную систему счисления, предложенную У, Пенни (%'. Реппеу) [,7АСМ 12 (1965), 247-248]: ( оАпзозНпэ о-! ° ° ° )а-1 — 4оа + (2+2!)пз — 2!аз + (1-1)аг + ао — $(!+1)а з + ° ° Выть может, самой изящной из всех систем счисления является уравивеешеииал щропчнпл система счисления (по основанию 3), в которой вместо цифр О, 1 и 2 используются "триты" (троичные цифры) -1, О и +1. Заменив -1 символом 1, получим следующие примеры уравновешенных трончных чисел.
В ней задействованы только цифры 0 и 1. Продемонстрировать, что любое комплексное'число допускает такое представление, можно, рассмотрев интересное множество 8, приведенное на рис. 1. Это множество по определению состоит из всех точек, которые могут быть записаны в виде 2 ь>~аь(! — 1) "' для бесконечной последовательности аы ат, аз, ... нулей и единиц.
Юна известна также как "двуглавый дракон" (см. М. Р. Вахпз1еу, Яасга!з Егегувфеге, зесоп6 есЫоп (Асайещ!с Ргезз, 1993), 306, 310). На рнс. 1 показано, что множество 5 можно разбить на 256 частей, конгруэнтных — '„Я. Заметим, что если множество 5 повернуть по часовой стрелке на 135', то оно распадется на два примыкающих одно к другому множества, конгруэитных (1/~Г2) Я., поскольку (! — 1)8 = 5 0 (8 + 1).
Деильно доказательство того, что множество Я содержит все комплексные числа, достаточно малые по модулю, рассмотрено в упр. 18. Рис. 1. Фрактальное множестве Я, называемое "двутлавый дракон". Один нз способов поиска числа в уравновешенной троичной системе состоит в сле- дующем. Сначала запншем число в троичной системе счислення, к примеру 208.3 = 121201 022002200220 )з. (Очень простой способ перевода в троичную систему, пригодный для вычнсления вручную с карандашом и бумагой, описан в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
