AOP_Tom2 (1021737), страница 63
Текст из файла (страница 63)
В первых быстродействующих вычислительных машинах, созданных в США в начале 40-х годов, использовалась десятичная арифметика. Но в 1946 году в сыгравшем важную роль отчете А. В. Беркса (А. Ж. Вцг1се), Г. Г. Голдстайна (Н. Н. ОоЫ- вНпе) и Дж. фон Неймана (Я. топ зеншапп) о проекте первой вычислительной машины с хранимой в памяти программой были подробно изложены причины, которые побудили их порвать с традицией и перейти к системе счисления по основанию 2 (см. ЯоЬгз иоп чешпапп, Со!!есгес( Игог!сэ 6, 41.-65). С тех пор двоичные вычислительные устройства получили всеобщее распространение.
После первой дюжины лет работы с двоичными машинами в статье В. Буххольца (1т". ВнсЬЬо1з) иГ1пкегв ог Е!втв7" (САСМ 2 (Ресегпбег, 1959), 3-1Ц был выполнен анализ сравнительных достоинств и недостатков двоичной системы счисления. Структура компьютера И1Х, используемого в этой книге, такова, что машина может быть как двоичной, так и десятичной. Интересно отметить, что почти все программы для этого компьютера можно написать, не зная, какая именно система используется (двоичнаи или десятичная), даже при выполнении вычислений с многократной точностью. Итак, мы видим, что на методику программирования для компьютера выбор основания системы счисления не оказывает значительного влияния.
(Заслуживает упоминания исключение из этого правила — операции "булевой" алгебры, рассматриваемые в разделе 7.1; см. также алгоритм 4.5.2.) Ошрицашельные числа могут быть представлены в компьютере несколькими спосабамн, Выбор того или иного способа зачастую оказывает влияние на метод реализации арифметических операций. Поясним сказанное. Сначала будем считать машину И1Х десятичной: тогда каждое слово состоит из десяти пифр и знака, например (2) -12345 67890. Этот способ представления называется пбсалютпным значением са знаком*. Такое представление соответствует общепринятым обозначениям, и поэтому его предпочитают многие программисты. Возможное неудобство заключается в том„что допускается существование как "минус нуль", так и "плюс нуль", в то время как зти разные коды должны обозначать одно и та же число.
На практике такая возможность требует принятия определенных мер предосторожности. В балыпинстве механических счетных машин, выполняющих действия десятичной арифметики, используется другая система записи — дополнение да деслгпивв. Если вычесть 1 из 00000 00000, в этой системе записи получим 99999 99999; другими * В общенрннятой русскоязычной терминологии этому понятию соответствует термнн прямой кад.— Прим.
перев. *в В общепринятой русскоязычной терминологии этому понятию соответствует термин дополни- тельный кад.— Прим. перев. словами, числу явно не приписывается знак, а вычисления выполняются по моду- лю 10го. Число — 12345 67890 в форме дополнения до десяти будет выглядеть так: (3) 87654 32110.
В этой системе обозначений принято считать отрицательным любое число, головная инфра которого — 5, 6, ?, 8 или 9, хотя с точки зрения сложения и умножения не будет большим грехом рассматривать (3), если это удобно, как число +87654 32110. Попутно отметим, что в такой системе не возникает проблема "минус нуль". На практике основное различие между двумя описанными формами представления заключается в том, что сдвиг вправо дополнения до десяти не эквивалентен делению на 10; к примеру, число — 11 =... 99989 после сдвига вправо на одну позицию превращается в... 99998 = — 2 (в предположении, что сдвиг вправо отрицательного числа порождает в головном разряде Я9н).
В общем случае результатом сдвига числа х, записанного в формате дополнения до десяти, на одну позицию вправо будет число (х/10), независимо от того, положительно или отрицательно число х. Одним из возможных неудобств записи в формате дополнения до десяти является несимметричность относительно нуля.
Наибольшее отрицательное число, представимое р цифрами, есть 500...О, и оно не является результатом обращения знака никакого р — разрядного положительного числа. Таким образом, возможно, изменение знака, т. е. замена х на — х, приведет к переполнению. (См. упр, 7 н 31, в которых обсуждается формат дополнения до основания системы счисления, который имеет бесконечную точность.) Еще одна система обозначений, принятая с самых первых дней эры быстродействующих вычислительных машин, — зто представление в виде дополнения до всех девяп1ок В этом случае число — 12345 67890 записывается в виде (4) 87654 32109.
Каждая цифра отрицательного числа ( — х) равна разности между 9 и соответствую1пей цифрой числа х. Нетрудно видеть, что для отрицательного числа дополнение до девяти всегда на единицу меньше соответствующего дополнения до десяти. Сложение и вычитание производятся по модулю 10'а — 1, а это означает, что перенос из крайней слева позиции добавляется к крайней справа (см. описание арифметики по модулю ео — 1 в разделе 3.2.1.1). Опять возникает проблема с "минус нулем", так как записи 99999 99999 и 00000 00000 обозначают одно и то же значение. Только что изложенные идеи для арифметики по основанию 10 в полной мере применимы и к арифметике по основанию 2; здесь мы имеем абсолютную величину со ливком, дополнение до двух и дополнение до одного*э.
Арифметика в дополнительном коде — это арифметика по модулю 2", а арифметика в обратном коде — по модулю 2" — 1. Машина И1Х имеет дело только с прямым кодом, что н используется в примерах этой главы. Тем не менее в сопроводитель- * В обшепринятай русскоязычной терминологии этому понятию соответствует термин оброшнмй код. — Лрнм. нерее.
*э В общепринятой русскоязычной терминологии этим понятиям соответствуют термины прямой, обрешнмо и дополнншельнмй код, которыми мы будем пальзаввться в дальнейшем. — Прим. нерее. ном тексте рассматриваются, если в этом есть необходимость, и альтернативные варианты процедур для дополнительного и обратного кодов. Скрупулезные читатели и редакторы английского текста, вероятно, отметили положение апострофа в терминах "ьжо'з сошр!ешепсо (дополнение до двойки) и "опез' сошр!ешепьь (дополнение до единиц). В первом случае каждая цифра дополняется до первой степени двойки, а во втором весь код есть дополнение до кода, представленного единицами во всех разрядах. По аналогии с "опез' сошр1е- щепФ" может существовать и формат "своз' сошр!етепс" (дополнение до двоек), который используется в системе счисления по основанию 3 и является дополнением до (2...
22) з. В руководствах по машинному языку программирования часто указывается, что схемотехника компьютера позволяет настраивать конкретное положение разделяющей точки в каждом машинном слове. На это сообщение не стоит обращать внимание. Пелесообразнее изучить правила размещения разделяющей точки в результате выполнения каждой конкретной команды, если предположить, что до ее выполнения точки в операндах были расположены в каком-то определенном месте. Например, в случае машины М1Х можно было бы рассматривать наши операнды либо как целые числа с разделяющей точкой в крайнем справа положении, либо как правильные дроби с разделяющей точкой в крайнем слева положении, либо как некоторые промежуточные варианты.
Правила установки разделяющей точки после осуществления операций сложения, вычитания, перемножения и деления определяются очевидным образом и следуют из алгоритмов выполнения этих операций. Легко видеть, что между записью чисел в системах по основанию Ь и Ь сущеь ствует простая связь: (...азагазаоа за г .
)ь=( .АзАгАзАоА-зА-г. )ь (5) где Ау = (аьз+ь-з аьз+заьз)ь (см. тпр, 3). Таким образом, получается простой способ перехода "чисто визуаль- ного" от, скажем, двоичной системы к шестнадцатеричной. Помимо стандартных систем по основанию Ь, обсуждавшихся выше, существует множество других интересных вариантов позиционных систем счисления. Например, можно было бы рассматривать числа по основанию ( — 10), так что (..
азагазпо.а-за — г... )-10 + аз (-10) + аг( — 10) + аз ( — 10) ' + ао + . — 1000аз + 100аг — 10аз + ао — з' а з + зова г— Здесь, как и в традиционной десятичной системе, цифры удовлетворяют неравенствам 0 ( аь ( 9. Число 12345 67890 запишется в такой "иегадесятичиой" системе в виде (1 93755 73910) ге, (6) так как она равна как раз 10305070900 — 9070503010. Интересно отметить, что обращение этого числа, — 12345 67890, запишется в виде (7) (28466 48290)- И действительно, любое вещественное число, положительное или отрицательное, мажет быть представлено без знака в системе по основанию — 10.
Системы по отрицательному основанию впервые описаны Витторио Грюнвальдом (Ч!!сог!о СгипгваЫ) в Сюгпа!е с(! МасетабсЬе с!г Вассай!!и! 23 (1885), 203- 221, 367. В этой работе изложены правила выполнения в таких системах четырех арифметических действий, а также рассмотрены правила, извлечения корня, проверка делимости и перевод из одной системы счисления в другую. Однако, похоже, работа Грюнвальда осталась незамеченной, так как она была опубликована в довольна заштатном журнале и вскоре забыта. Следующее исследование по системам счисления по отрицательному основанию опубликовал О.
Дж, Кемпнер (А. Л. Кетрпег) в АММ 43 (1936), 610 — 617. В этой работе он рассмотрел свойства систем счисления с нецелыми основаниями и отметил в примечаниях, что системы счисления с отрицательными основаниями также будут иметь право на существование. Двадцать лет спустя эта идея снова была предложена; на этот раз — 3. Павлякам (Е. Рагс!а!с) и А.
Вакуличем (А. Ч'а!си!!сг) !Ви!!ебп с!е 1'Аеас!ет!е Ро!опа!ве с(ев Яс!епсев, С!авве П1, 5 (1957), 233 — 236; ЯеНе с!ев всгепсев СесЬпнйиев 7 (1959), 713 — 721], а также Л, Уэйделом (Ь. %ас!е!) (1ВЕ Тгапвассюпв ЕС-6 (1957), 123). Экспериментальные вычислительные машины 8ККЕАТ ! и В!!ЧЕС, в которых — 2 использовалось в качестве основания системы, были сделаны в Польше в конце 50-х годов (см. М, М. В!асЬспап, САСМ 4 (1961), 257; Н. %'. Магсгуйв1с1, Апп. Гйва Сотрибпй 2 (1980), 37 — 48).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
