СЕРИЯ XIX

1967

МАТЕМАТИКА КИБЕРНЕТИКА

2

Г. О. ЕФРЕМОВ

Язык математических машин

Г. О. ЕФРЕМОВ

ЯЗЫК МАТЕМАТИЧЕСКИХ МАШИН

Системы счисления

ИЗДАТЕЛЬСТВО «ЗНАНИЕ»

Москва 1967

513

Е91

Введение

Представим себе, что мы читаем биографию ученого-математика, записанную в несколько необычной форме:

«Еще в младших классах средней школы он проявлял себя весьма смышленым мальчиком. С задачами, которые сверстники решали полчаса, он справлялся за какие-нибудь 101—110 минут. Одаренный недюжинным умом и неиссякаемой энергией, этот счастливец окончил вуз на год раньше срока — за 11 лет, и в возрасте 10100 лет, будучи совсем молодым человеком, возглавил важную научно-исследовательскую лабораторию».

Вы всматриваетесь в лежащий перед вами странный текст, снова и снова перечитываете его, стараясь понять содержание отрывка. Нет, это не бред сумасшедшего. Текст принадлежит перу человека, обладающего здравым рассудком и острым умом, но дело в том, что числа в нем выражены в иной, непривычной нам системе счисления. Что же это за странная форма записи? В самом деле, как это «за какие-нибудь 101—110 минут»? Разве это мало, если сверстники решают задачу за полчаса? Кроме того, как же можно окончить вуз раньше положенного срока за 11 лет? Наконец, назвать молодым человеком того, кто имеет возраст 10100 лет?

Однако не будем спешить с выводами. Но чтобы разобраться в содержании упомянутого отрывка, нам необходимо знать некоторые сведения из теории счета, нужно ознакомиться с тем, что такое система счисления, и особенно с двоичной системой, являющейся наиболее распространенным языком математических машин.

Одной из характерных черт развития науки и техники последнего времени является внедрение математических методов в разные сферы человеческой деятельности. Математика представляет собой незаменимый аппарат автоматизации производства, ее используют при проектировании технических сооружений, городов, поселков с их разносторонним хозяйством. Успехи советской науки и техники за последние годы —

широкое применение атомной энергии в мирных целях, запуск искусственных спутников Земли и космических кораблей, осуществление полетов человека в космическое пространство и т. д. — опираются в значительной степени на успехи развивающейся математической науки. Наконец, мы являемся свидетелями того, как математика проникает в сферы, далеко не родственные ей. Возникает целый ряд новых наук: математическая биофизика, математическая экономика, математическая лингвистика, происходит «математизация» медицины, гуманитарных наук. Мы не говорим уже о роли математики в механике, физике, астрономии, геодезии, химии, где математические методы давно стали обиходными. Претворяются в жизнь предсказания выдающегося ученого и художника Леонардо да Винчи о том, что никакое человеческое исследование не может быть названо истиной, если оно не проходит через математические доказательства.

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

Чтобы математическая машина могла решать все эти задачи, их нужно представить на «понятном» для машины языке. Таким языком является язык цифр. Машина «понимает» вводимую информацию лишь при цифровой записи ее. Решение любой задачи — научно-технической, логической — сводится в машине к совокупности арифметических операций, которые выполняются в арифметическом устройстве машины,

причем эти арифметические операции производятся над двоичными (реже над троичными) числами.

В данной брошюре будет рассмотрен «язык» математических машин — системы счисления, которые в них применяются.

Что известно из истории цифр

Под системой счисления подразумевается совокупность приемов наименования и записи чисел. Так как обозначать числа можно разными приемами, то и системы счисления бывают различные.

Самым простым способом записи является изображение каждого предмета отдельным знаком: в этом изображении было бы столько знаков, сколько имеется предметов. Из исторических источников известно, что во время похода персидского царя Дария на скифов отряду греков, которому поручалась охрана моста через Дунай, он передал веревку с завязанными на ней узлами и оставил следующий наказ: развязывать по одному узлу в день и плыть домой, когда все узлы будут развязаны. Таким образом, отряд пользовался самой простой системой счисления, которую можно было бы назвать единичной: каждому дню соответствовал свой узел. Ни на какие разряды здесь число не делится, никаких переходов в высшие разряды не производится.

В глубокой древности запись производилась еще примитивнее. В то время людям были известны только два числительных: один и два. Про большее число предметов тогда говорили просто «много». Используя пальцы одной и обеих рук, люди постепенно научились считать до пяти и десяти, а затем и дальше. Числа тогда записывали не при помощи цифр, а изображали особыми значками — иероглифами. Одним из примеров такой записи является египетская нумерация, которая возникла за 2500—3000 лет до нашей эры. При записи чисел при помощи иероглифов египтяне пользовались единственным принципом — принципом сложения: числа, изображенные рядом стоящими иероглифами, складываются. Подобные системы счисления называются аддитивными (термин происходит от латинского слова additio — сложение).

Интересная система счисления, являющаяся, по существу, тоже аддитивной, сложилась около 2000 лет назад в Древнем Риме. В римской системе счисления для записи натуральных чисел применяются знаки I, V, X, L, С, D, M и т. д., которые соответственно обозначают один, пять, десять, пятьдесят, сто, пятьсот, тысячу и т. д. Они называются цифрами. При записи чисел пользуются следующими правилами:

— написанные друг за другом одинаковые цифры означают их сумму;

= если большая цифра стоит впереди меньшей, то они складываются;

— если меньшая цифра находится впереди большей, то меньшая вычитается из большей.

Так, запись III означает три, XX — двадцать, VIII — восемь, XII — двенадцать, XL — сорок, ХС — девяносто. Число тысяча девятьсот шестьдесят семь в римской системе счисления записывается так: MCMLXVII. Выполнение арифметических действий над числами, записанными в римской системе, представляет значительную трудность. Неудобны в этой системе также запись и чтение чисел. Поэтому римская система счисления в данное время почти не применяется. Римскими цифрами пользуются лишь для обозначения веков, номеров месяцев и порядковых числительных.

Более совершенными являются алфавитные системы счисления, в которых для обозначения чисел используются буквы алфавита. Так, в славянской нумерации, употреблявшейся в Древней Руси, для записи чисел применялись двадцать семь букв. Эта нумерация позволяла записывать весьма большие числа и более просто выполнять арифметические действия над ними.

Интересный способ записи чисел появился в Древнем Вавилоне (около 2000 лет до нашей эры). Вавилоняне числа изображали при помощи лишь двух знаков: один знак соответствовал единице, другой — десяти. Числа до 59 записывались как комбинации этих знаков по принципу сложения их значений, а число 60 снова изображалось знаком для единицы, но этот знак уже изображал единицу старшего (второго) разряда. Числа до 3599 записывались также по принципу сложения, а число 3600 снова обозначалось знаком для единицы, однако он представлял собой уже единицу очередного старшего (третьего) разряда. Такой же принцип применялся и для записи еще больших чисел.

Цифры в вавилонской нумерации обозначались знаками, напоминающими клинья. Поэтому письменность вавилонян называют клинописью.

Вавилонская нумерация, как и некоторые алфавитные системы, относится к позиционным системам счисления. Остатки этой нумерации сохранились и поныне: круг делится на 360 угловых градусов, градус — на 60 минут, минута на 60 секунд.

В позиционной системе счисления цифра имеет различное значение в зависимости от того, на каком месте в числе она находится. Иначе говоря, значение цифры в числе зависит от позиции, которую она занимает. Поэтому система и называется позиционной. Так, в вавилонской системе одна и та же цифра обозначала 1; 60; 3600 и т. д., находясь соответственно в нервом, втором, третьем и так далее разрядах. Количество

единиц низшего разряда, составляющее единицу соседнего высшего разряда, называется основанием системы. В вавилонской системе основанием являлось 60.

В истории развития человеческой культуры встречаются позиционные системы и с другими основаниями. Так, французское числительное quatre-vingts, означающее число 80, в буквальном переводе представляется в виде четыре-двадцать, что свидетельствует, что когда-то существовала двадцатиричная система. В Древнем Китае применялась пятеричная нумерация. Сохранившаяся до наших дней единица измерения дюжина, составляющая 12 единиц, является остатком двенадцатиричной системы.

Особый интерес своей необычностью представляет пози-

Примеры записи чисел у древних вавилонян.

ционная система счисления, которой пользовались древние центральноамериканские индейские племена майя, обитавшие на полуострове Юкатан. Применение математических машин и математических методов позволило советским ученым расшифровать древние рукописи этих племен, никем ранее не прочитанные. Система счисления майя имеет два основания: пять и двадцать. Поэтому ее можно называть пятерично-двадцатиричной системой. Единица в этой системе обозначалась точкой (точнее — маленьким кружочком); числа два, три, четыре — соответственно двумя, тремя, четырьмя точками, поставленными в строку. Для числа пять существовал уже другой знак — горизонтальная черточка. Для изображения чисел шесть, семь, восемь и девять над черточкой ставились соответственно одна, две, три и четыре точки. Число десять записывалось двумя черточками, одиннадцать — двумя черточками и одной точкой и т. д., а число девятнадцать записывалось тремя черточками и четырьмя точками. Особый знак существовал для изображения нуля. Числа записывались в вертикальную колонку: сверху вниз в порядке возрастания разрядов.

Примеры записи чисел в системе счисления майя

Десятичная система счисления, которой мы обычно пользуемся, также представляет собой позиционную систему. Рассматривая числа 243 и 342, нетрудно заметить, что одна и та же цифра 3 в первом числе обозначает три единицы, во втором — три сотни. Цифра 2, наоборот, в первом числе обозначает две сотни, во втором — две единицы. Значение цифр определяется местом этих цифр в записанном числе. Так как цифра 4 занимает в обоих числах одинаковое положение, то не изменяется и значение ее. В десятичной системе счисления для записи чисел используется десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

В этой системе основанием является десять, и каждые десять единиц данного разряда числа составляют единицу соседнего старшего разряда. Так, прибавляя к девяти единицам еще одну единицу, получаем десять единиц. Результат записывается двузначным числом 10: десять единиц первого разряда составляют одну единицу второго разряда. Аналогично десять единиц второго разряда (10 десятков) составляют одну единицу третьего разряда (1 сотня) и т. д. Любое число в этой системе можно представить как сумму целых степеней десяти:

где a1 может принимать любое из значений: 0, 1,2, 9. Например,

Десятичная система счисления возникла около V века нашей эры в Индии и стала распространяться на Запад и Восток. В Европу эта система вошла с переводами с арабского и в связи с этим получила название арабской системы счисления. Лишь в XVII веке она появляется в России, вытесняя алфавитную систему записи чисел. Распространение этой системы на всех континентах мира объясняется привычностью счета десятками, так как человек всегда пользовался для подсчета количества предметов десятью пальцами своих рук.

В этой системе можно записывать любые числа — целые и дробные. Числа в ней представляются компактно, и над ними удобно производить арифметические действия.

В принципе можно представить систему счисления с произвольным основанием. Пусть основанием системы является

некоторое число р. Тогда число в этой системе представляется как сумма степеней р:

где а, может принимать значения 0, 1, 2, р.

Если основание рассматриваемой системы записывать цифрами той же системы, то в любой системе это основание будет записано единицей с нулем: р=10 и

Двоичная система счисления — язык математической машины

Двоичная система счисления по сравнению с другими представляет собой наиболее простую систему. Основанием ее служит два, и для записи чисел достаточно иметь всего два знака: 0 и 1. В этой системе каждые две единицы данного разряда составляют единицу следующего разряда. Приведем для сравнения запись первых пятнадцати натуральных чисел в десятичной и двоичной системах.

В десятичной системе

1

2

3

4

5

6

7

8

9

В двоичной системе

1

10

11

100

101

110

111

1000

1001

В десятичной системе

10

11

12

13

14

15

В двоичной системе

1010

1011

1100

1101

1110

1111

Число, записанное в десятичной системе, можно представить в двоичной системе, последовательно выделяя из него максимальные целые степени числа два. Пусть, например, следует представить в двоичной системе 23. Выделим целую степень 2, содержащуюся в данном числе: 24= 16. Из остатка 23—16=7 выделяется следующая максимальная степень:

22=4; из следующего остатка 7—4 = 3 выделяется максимальная степень 21 = 2 и остается 1. Этот остаток может быть представлен как 20. Таким образом число 23 в виде суммы степеней числа два можем выразить так:

Это же число, записанное в двоичной системе, будет иметь вид: 10111.

Перевод чисел из десятичной системы в двоичную можно легко произвести и путем последовательного деления на два: достаточно остатки, получаемые при каждом делении, написать друг за другом в обратном порядке. В качестве примера покажем перевод в двоичную систему записи числа 345, записанного в десятичной системе:

При первом делении в частном получилось 172, в остатке 1: при делении первого остатка — в частном 86, в остатке 0 и т. д. Переписав остатки в обратном порядке, запишем в двоичной системе это число как 101011001.

В случае использования разных систем счисления, чтобы различать, в какой системе представлено число, внизу справа от него ставится в виде индекса основание системы. Например, запись 11012 означает, что число 1101 представлено в двоичной системе. Если число представлено в десятичной системе, то такой индекс обычно не ставится. Не ставится он обычно и в том случае, когда речь все время идет о какой-либо одной системе счисления.

Перевод из двоичной системы в десятичную производится в обратном порядке. Так, двоичное число 110101 при переводе в десятичную систему будет равно:

Арифметические операции в двоичной системе чрезвычай-

но упрощаются. Таблицы сложения и умножения получаются элементарно простыми:

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

— одна цифра 0, другая 1; тогда в разряде суммы будет 1;

— в данном разряде обоих чисел стоит 1; тогда в разряде суммы будет 0, а 1 остается «в уме», т. е. переносится в следующий разряд;

— данный разряд обоих чисел, как и в предыдущем случае, представлен единицей, но помимо этого имеется единица «в уме»; в этом случае в данном разряде суммы появится 1, кроме того единица остается «в уме» для переноса в следующий разряд.

Эти операции легко проследить на следующем примере:

В десятичной системе действие сложения выглядело бы так;

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

Пусть необходимо выполнить действие:

Для вычитаемого числа числом, дополняющим его до следующей высшей разрядной единицы, т. е. до 1000, является 675. Прибавим это число к уменьшаемому. Чтобы можно было сразу отбрасывать в итоге лишнюю цифру слева, левее высших разрядов складываемых чисел заранее проводится верти-

кальная линия. Результат вычисления читаем под горизонтальной чертой справа от вертикальной линии:

Результат, как видно, получился тот же, что и в первом случае.

Аналогично производится вычитание чисел в двоичной системе. Допустим, что из 10011 нужно вычесть 101. Сначала необходимо уравнять количество разрядов у данных чисел. Для этого достаточно приписать к вычитаемому спереди два нуля и оно запишется как 00101. Дополнением к вычитаемому (до 100000) является число 11011, Прибавим это число к уменьшаемому:

Отбросив единицу слева от вертикальной линии, получим 01110. Действительно, 19—5=14.

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

— заменить цифры числа на родственные, т. е. единицы нулями и нули единицами;

— прибавить 1 к низшему разряду записанного таким образом числа.

Пример. Допустим, что нам необходимо найти дополнение для числа 1101:

Дополнение для 001011011:

Дополнение для 011000:

Умножение в двоичной системе также сводится к сложению. Умножим по обычному правилу умножения 11011 на 1101:

Как мы видим, умножение по обычному правилу сводится к переписыванию множимого (с соответствующими сдвигами) и сложению.

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

Деление 1101 на 101

Вычитание делителя

Остаток Сдвиг влево

Сдвиг влево Вычитание делителя

Деление 10010 на 111

Вычитание делителя

Остаток Сдвиг влево

Ответ:

В данном случае число, образованное первыми тремя цифрами делимого, т. е. число 100, меньше делителя 111. Поэтому для первого деления пришлось взять в делимом четыре цифры (1001). В связи с этим в целях уравнивания количества разрядов впереди делителя на место четвертого разряда поставлен нуль.

В вычислительных машинах с помощью тех же двух цифр обозначаются и знаки двоичных чисел: знак «+» выражается цифрой 0, знак «—» — цифрой 1. Для изображения знака впереди каждого числа вводится специальный разряд, называемый знаковым разрядом. Например, числа +11010 и — 01011 в шестиразрядной сетке соответственно изображаются как 011010 и 101011,

Двоичная и троичная системы

Какая система счисления лучше? Для машинной математики это вовсе не праздный вопрос. Система счисления должна быть экономичной в отношении объема физических элементов, с помощью которых осуществляется запоминание чисел в машинах.

Ответ многих людей в пользу десятичной системы является неверным и объясняется лишь силой привычки. Десятичная система — не наилучшая. Самой экономичной с этой точки зрения оказывается... троичная система счисления. Но даже двоичная система, несмотря на некоторую громоздкость записи чисел, является лучше десятичной. Попытаемся дать теоретическое обоснование этого вывода.

Для оценки системы счисления удобно пользоваться понятием цифроразрядов, которое представляет собой произведение количества цифр, используемых в данной системе счисления, на число разрядов, необходимых для изображения чисел. Чем меньше количество цифроразрядов, тем система лучше, т. е. это произведение определяет объем оборудования, необходимого для воспроизведения чисел в машинах.

Предположим, что для записи чисел в десятичной системе используется n разрядов. Максимальным числом, которое можно записать в этих n разрядах, является:

Если основанием системы счисления является а, то аналогично для записи этого максимального числа потребуется другое количество разрядов. Обозначив это количество разрядов через г, можно записать:

откуда

Таким образом, обозначив количество цифроразрядов (az) через с, получим:

Найдя первую производную функцию с по а и приравняв

ее нулю, получим уравнение для нахождения минимального значения а:

откуда

следовательно, а = е.

Итак, количество числоразрядов имеет наименьшее значение при системе счисления с основанием, равным основанию натуральных логарифмов. Но использовать е в качестве основания системы затруднительно, так как это число трансцендентное. Целым же числом, наиболее близким к е=2,718..., является 3, а следующим по степени приближения — 2.

Таким образом, мы установили, что наиболее выгодной системой счисления для машин была бы троичная система, а за ней — двоичная. Троичная система записи чисел в машине на 59% экономичнее десятичной и на 5,4% двоичной.

Троичная система счисления применяется в математической машине «Сетунь», построенной в Вычислительном центре Московского государственного университета имени М. В. Ломоносова. Машина «Сетунь» является первой в мире машиной, работающей в этой системе.

Поскольку основанием системы служит 3, то три единицы данного разряда числа составляют единицу соседнего старшего разряда. Однако в машине «Сетунь» цифрами являются 1; 0 и — 1. Цифру — 1 будем обозначать символом 1. Ниже приводится сравнительная запись нескольких чисел в десятичной и троичной системах счисления с цифрами 0, 1, —1.

В десятичной системе

1

2

3

4

5

6

7

8

9

10

В троичной системе

1

11

10

11

111

110

111

101

100

101

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

Вот несколько примеров такой записи:

В связи с наличием в такой системе положительной и отрицательной цифр имеется возможность представлять в машине непосредственно как положительные, так и отрицательные числа без специального знакового разряда. Как видно из приведенных выше примеров, знак числа определяется знаком старшей значащей цифры.

Таблицы сложения и умножения в троичной системе счисления с цифрами 1,0, — 1 имеют следующий вид:

Таблица сложения

Таблица умножения

Арифметические действия над числами производятся по обычным правилам с использованием приведенных таблиц сложения и умножения.

Примеры сложения и вычитания

Вычитание удобно заменять сложением — вместо того, чтобы вычитывать вычитаемое, достаточно к уменьшаемому прибавить число, полученное из вычитаемого заменой цифр 1 на 1 и 1 на 1.

Умножение

Деление Вычитание делителя Остаток

Ответ:

В самом деле

Почему же все-таки двоичная?

Основной системой счисления, применяемой в математических машинах, является все же двоичная. Она представляет собой язык математических машин таких систем, как БЭСМ, «Урал», «Стрела», М-3, «Киев», СЦМ, М-20 (СССР), ИБМ, «Ураган», ДИСЕАК, УНИВАК, ДИДЖИТАК (США), «Пегас», «Меркурий», ЭДСАК (Англия), САПО (Чехословакия), КАБ-2022 (Франция), БЭСК (Швеция), ПЭРМ (ФРГ) и т. д. Машины же, где двоичная система не применяется, составляют исключение. И это не случайно. Двоичная система счисления по сравнению с другими системами обладает рядом решающих преимуществ.

Уже было выяснено, что в отношении экономии в оборудовании двоичная система, за исключением троичной, самая выгодная из всех других систем. При все возрастающих масштабах применения математических машин в народном хозяйстве этот фактор имеет немаловажное значение.

Арифметические операции в двоичной системе счисления выполняются наиболее просто. Двоичная система позволяет наиболее эффективно осуществлять запоминание чисел в машинах. Физические элементы, из которых составляются запоминающие устройства, должны обладать в этом случае лишь двумя ярко выраженными состояниями. Одно из таких состояний может соответствовать цифре 1, другое — цифре 0. Такими элементами могут быть, например, конденсаторы (заряды положительный и отрицательный), ферромагнитные сердечники (северный и южный магнитные полюса), электронные лампы (открытая и закрытая лампы) и др. Кроме того, числа в этой системе очень удобно представлять в виде совокупности

электрических импульсов (наличие импульса в данный момент времени и отсутствие его). При системе счисления с основанием четыре от физических элементов требовалось бы наличие четырех различных состояний, при пятеричной системе — пять состояний и т. д. Но создать физические приборы, обладающие таким большим количеством устойчивых состоянии, резко отличных друг от друга, гораздо труднее.

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

Восьмеричная система счисления

При программировании задач для ряда математических машин применяется восьмеричная система счисления, основанием которой является число восемь. В этой системе восемь единиц данного разряда составляют единицу соседнего старшего разряда и для записи чисел используются восемь цифр: 0, 1,2, 3, 4, 5, 6, 7. Любое число, записанное в этой системе, может быть представлено как сумма степеней числа восемь:

где a1 может принимать значения 0, 1, 2, 3, 4, 5, 6, 7. Например

Таблицы сложения и умножения восьмеричной системы напоминают соответствующие таблицы десятичной системы. Таблица 1 представляет собой таблицу сложения. Слагаемые записаны в верхней строке и в левом столбце. Сумму следует находить в месте пересечения соответствующей строки и столбца. Например, чтобы найти сумму 6 + 5, находим столбец, отмеченный цифрой 6, и строку, первой цифрой которой является 5 (или наоборот), и в месте пересечения их читаем 13. Это и будет искомая сумма. В самом деле 138=1«81 + 3—80=11.

Таблица 1

Таблица сложения в восьмеричной системе счисления

+

0

1

2

3

4

5

6

7

10

0

0

1

2

3

4

5

6

7

10

1

1

2

3

4

5

6

7

10

11

2

2

3

4

5

6

7

10

11

12

3

3

4

5

6

7

10

11

12

13

4

4

5

6

7

10

11

12

13

14

5

5

6

7

10

11

12

13

14

15

6

6

7

10

11

12

13

14

15

16

7

7

10

11

12

13

14

15

16

17

10

10

11

12

13

14

15

16

17

20

Аналогично следует пользоваться и таблицей умножения (табл. 2).

Таблица 2

Таблица умножения в восьмеричной системе счисления

X

0

1

2

3

4

5

6

7

10

0

0

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

7

10

2

0

2

4

6

10

12

14

16

20

3

0

3

6

11

14

17

22

25

30

4

0

4

10

14

20

24

30

34

40

5

0

5

12

17

24

31

36

43

50

6

0

6

14

22

30

36

44

52

60

7

0

7

16

25

34

43

52

61

70

10

0

10

20

30

40

50

60

70

100

Действия над числами в восьмеричной системе аналогичны действиям в десятичной системе и основываются на приведенных выше таблицах сложения и умножения.

Примеры:

В первом примере, при сложении цифр 2 и 3 низших разрядов в низшем разряде суммы получаем 5; далее складываем цифры второго разряда: 6+4=12; цифру 2 записываем в данном разряде суммы (1 остается «в уме» и прибавляется к сумме цифр следующего разряда: 0 + 4 + 1=5) и т. д.

В примере на вычитание цифра низшего разряда уменьшаемого меньше цифры вычитаемого. Поэтому в уменьшаемом «занимаем» единицу соседнего разряда и производим вычитание: 16—7 = 7 и т. д.

Чтобы разобраться в примере на умножение, нужно также воспользоваться таблицами сложения и умножения. Сначала умножаем множимое на 4. По таблице умножения находим: 7×4 = 34; цифру 4 записываем в данном разряде, а 3 сохраняем «в уме», чтобы прибавить к результату умножения на 4 цифры следующего разряда множимого и т. д.

Перевод чисел из одной позиционной системы счисления в другую

Для перевода чисел из любой позиционной системы в произвольную другую может быть использован способ, подобный рассмотренному нами способу перевода числа из десятичной системы в двоичную: нужно произвести последовательное деление числа, записанного в исходной системе, на основание другой системы, в которую переводится число. При этом основание произвольной системы должно быть записано в форме, соответствующей первоначальной системе (в системе, в которой представлено преобразуемое число).

Если, например, число 673, представленное в десятичной системе, нужно перевести в троичную систему счисления, то число 673 следует разделить на 8, первое частное — снова на 3 и т. д. и из полученных остатков составить число в троичной системе счисления, записывая их друг за другом в обратном порядке (в целях сокращения записи условимся записывать только частные и остатки):

Из остатков составляется число 220221. Это и есть троичная запись числа 673. Действительно,

В этом примере процесс деления для читателя является привычным, так как числа, которыми приходилось оперировать, записаны в десятичной системе счисления.

Рассмотрим случай, когда данное число представлено не в десятичной системе и его нужно перевести в систему, основание которой тоже отлично от десяти.

Переведем число 24135 в троичную систему счисления.

При этом, как мы видим, число 24135 записано в пятеричной системе: каждая единица данного разряда, начиная со второго, составляет пять единиц соседнего низшего разряда. Процесс деления произведем более подробно.

Остатки от действий деления составляют: 1, 2, 0, 1, 1, 1. Следовательно, число в троичной системе можно представить как 111021. Итак, 24135= 1110213.

Чтобы убедиться в правильности преобразования, выразим 24135 и 1110213 в десятичной системе счисления:

В обоих случаях получилось одно и то же десятичное число. Обоснование этого способа перевода чисел из одной позиционной системы в другую заключается в следующем.

Пусть целое число N представлено в р-ичной системе счисления и его необходимо перевести в систему с основанием q. Предположим, что основание второй системы записано в первой, т. е. в /7-ичной системе.

Допустим, что изображение числа N в q-ичной системе нам известно и оно имеет следующий вид:

Пусть цифры аn, аn-1, а1, а0 в p-ичной системе выражаются как bn, bn-1 b1, b0. Тогда число N может быть записано так:

N = bnqn+bn-1qn-1 + ... + b2q2+b1q1 + b0.

Разделим обе части равенства на q:

Число N1 = bnqn-1+bn-1qn=2 + .-.+b2q + b1 представляет собой частное, b0 — остаток. Частное N1 снова делим на q:

Получили частное N2 = bnqn-2 + bn-1qn-3 + ... + b2 и остаток b1.

Деление на q будем продолжать до тех пор, пока очередное частное не станет меньше q. При этом у нас появятся числа b0, b1, bn-1 bn, которые нужны для записи числа N в q-ичной системе:

Таким образом, перевод числа из р-ичной системы в q-ичную сводится к нахождению цифр для записи числа в q-ичной системе путем деления числа, данного в р-ичной системе, на q. При этом q должно быть выражено также в р-ичной системе.

При q<p число может быть записано в q-ичной системе из полученных остатков деления непосредственно. Если же q>p, то те из остатков b0, b1, b2, ... bn, которые больше р, нужно предварительно перевести в q-ичную систему.

Так, при переводе числа 121023 в пятеричную систему имеем следующее:

Остатками являются числа 1, 11, 0, 1, которые записаны в троичной системе. В пятеричной системе это будут цифры 1, 4, 0, 1. Следовательно, число в пятеричной системе запишется так: 1041.

Проверка:

Рассмотрим далее вопрос о переводе правильной дроби из одной системы в другую.

Пусть дробь D записана в р-ичной системе счисления и ее нужно представить в системе с основанием q. Полагаем, что это основание q записано в р-ичной системе.

Допустим, что изображение дроби D в q-ичной системе счисления нам известно и оно имеет следующий вид:

Представим, что цифры а-1 а-2, а-3,... в р-ичной системе выражаются числами b-1, b-2, b-3 ... Основание системы (10) обозначим через q.

Тогда дробь D выразится следующим образом:

Умножим дробь на q:

Произведение состоит из целого числа b-1 и дробной части

Умножив дробную часть снова на q, получим:

Продолжая этот процесс дальше, получаем числа b-3, b-и т. д.

Таким образом, путем умножения дроби, представленной в p-ичной системе счисления, на основание новой системы q, выраженное в p-ичной системе, мы получили числа b-1, b-2, b-3, которые нужны для записи данной дроби в q-ичной системе счисления. Эти числа пока выражены в р-ичной системе. После перевода их в q-ичную систему мы получаем цифры a-1, а-2, а-3, ... для окончательной записи дроби в q-ичной системе.

Пример:

Пусть требуется перевести дробь 0,1112 в десятичную систему счисления.

Основание новой системы счисления в старой системе выразится числом 1010.

Для записи дроби в десятичной системе получили числа 1000; 111 и 101. Представим их в десятичной записи: 10002 = 8, 1112 = 7, 1012 = 5. Итак, 0,1112 = 0,875. Проверка:

В данном случае дробь в новой системе счисления имеет вид конечной дроби. В большинстве же случаев получается

бесконечная дробь и результат выражается с определенной точностью.

Пример:

Пусть дробь 0,4235 необходимо представить в троичной системе счисления.

Таким образом,

Если же число содержит целую и дробную часть, то их нужно переводить в новую систему счисления раздельно и полученные результаты соединить.

Пример:

Смешанное число 315,1256 необходимо перевести в троичную систему счисления.

Перевод чисел из восьмеричной системы счисления в двоичную и обратно

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

Пусть число представлено в восьмеричной системе счисления:

Предположим, что нам известна также двоичная запись этого числа:

Основания систем и показатели степеней нами изображены для удобства в десятичной системе счисления.

Очевидно, что при делении двух одинаковых чисел на одно и то же число получаются одинаковые частные и одинаковые остатки.

Разделим числа N и M на одно и то же число 8=23. От деления N на 8 получаем частное

и остаток а0.

Деля M на 23, соответственно находим

Имеем:

Аналогично находим:

Таким образом, если в изображении восьмеричного числа цифры представить в двоичной системе счисления, то получилась бы следующая запись:

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

Примеры:

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

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

Примеры:

Представление чисел в двоично-десятичной записи

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

Двоично-десятичная запись заключается в том, что цифры десятичного числа представляют в двоичной системе. Причем, ввиду того что самая большая цифра десятичной системы в двоичной системе изображается четырехразрядным числом, то в записи любой цифры должно быть четыре знака: 9= 10012, 8=10002, 7 = 01112, 6 = 01102, 0,4 = 0,01002 и т. д. Эти группы из четырех цифр называются тетрадами. Число 397,52 в двоично-десятичной записи представляется, например, так: 0011 1001 0111,0101 0010.

Для обратного перевода двоично-десятичного числа в десятичную систему записи необходимо разбить его на тетрады в обе стороны от запятой и каждую тетраду отдельно заменить десятичной цифрой.

Так, например, двоично-десятичное число 1100010111,0110100101 представляет собой десятичное число 317,694.

Формы представления чисел в математических машинах

В математических машинах применяются две формы представления чисел: естественная и полулогарифмическая.

В машинах с естественной формой представления чисел последние изображаются в виде последовательности опреде-

ленного количества цифр с постоянным положением запятой, которая отделяет целую часть чисел от дробной. Например, числа +3105,81; +0067,19; —2591,00; —0000,74; +000,05 представлены в естественной форме. В них запятая поставлена после четвертого знака, считая слева направо. Эта форма представления чисел называется иначе формой с фиксированной запятой.

Диапазон чисел, представляемых в естественной форме, недостаточно велик. Например, при шести разрядах и с запятой после четвертого знака, как это было в приведенных выше примерах, можно представить положительные числа, начиная от 0000,01 и кончая 9999,99.

В полулогарифмической форме число изображается с помощью двух групп цифр. Первая группа, называемая мантиссой, представляет собой последовательность цифр числа. Вторая же группа служит для определения положения запятой и называется порядком. Данная форма представления чисел называется еще нормальной или формой с «плавающей» запятой.

Пусть N есть число, записанное в естественной форме. Оно может быть представлено как N ⋅ 100, где 10 — основание системы счисления. Преобразуем Это число так, чтобы абсолютная величина первого сомножителя была меньше единицы. Для этого при |N| > 1 запятую следует перенести на необходимое число разрядов влево, одновременно увеличив показатель степени основания на то же число единиц. Если |N|<1, то число в таком преобразовании не нуждается.

Итак, имеем: N ⋅ 100 = m ⋅ 10p, где m является мантиссой числа, p-порядком.

Например, число + 3105,81, записанное в естественной форме, в полулогарифмической форме может быть представлено так: + 0,310581.10+4. Группа цифр +310581 представляет собой мантиссу, +4 — порядок. В машине число было бы представлено в следующем виде: +310581 +04.

Число может быть представлено в полулогарифмической форме в разном виде. Например, приведенное выше число можно изобразить так: +0,0310581.10+5; + 0,00310581.10+6 и т. д. В первом случае мантиссой является +0310581, порядком — +5; во втором случае ими являются соответственно числа +00310581 и +6.

Мантисса числа представляет собой всегда правильную дробь, а порядок — целое число.

Нормальное число, т. е. число, выраженное в нормальной форме, называется нормализованным, если первая цифра мантиссы отлична от нуля. Если число N=m <10р нормализованное, то

Так, в нашем примере число с мантиссой +310581 и порядком + 4 является нормализованным.

В двоичной системе счисления первая слева цифра мантиссы нормализованного числа представляет собой всегда 1.

Применение полулогарифмической или нормальной формы представления чисел с «плавающей» запятой позволяет значительно расширить диапазон чисел, которыми оперирует машина.

При сложении и вычитании чисел, заданных в полулогарифмической форме, их порядки сначала должны быть выравнены. Так, если нужно сложить числа + 0,24315.10+2 и 0,341018.10+3, то мантиссу первого числа сначала следует сдвинуть на один разряд вправо, соответственно увеличив порядок его на единицу, т. е. произвести следующее преобразование: + 0,24315.10+2 =+0,024315.10+3. Далее, остается произвести сложение мантисс. Порядком суммы будет общий порядок слагаемых. В результате сложения получится число: + 0,365333.10+3.

Аналогично производится и вычитание.

При умножении и делении соответствующие действия производятся также над мантиссами, а порядок результата находится следующим образом: при умножении порядки сомножителей складываются, при делении из порядка делимого вычитается порядок делителя.

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

Заключение

Разные народы мира разговаривают, пишут и читают на различных языках. Одну и ту же мысль можно передавать по-русски и по-украински, по-немецки и по-английски, по-французски и по-испански и т. д. Любая речь состоит из слов, которые пишутся при помощи букв соответствующего алфавита. Однако алфавитом может быть не только набор подобных букв, но и система других знаков. В качестве алфавита, например, можно представить совокупность цифр 0, 1, 2, 9. Числа, написанные этими цифрами, можно рассматривать как слова в данном алфавите. Алфавит могут составить знаки 0 и 1. Этот алфавит также позволяет составлять слова. Сущность работы математической машины заключается в переработке информации, выраженной словами при помощи алфавита подобного типа. Слова эти представляют собой не что иное,

как двоичные числа. Такими знаками можно изображать не только то или иное число, но и всевозможные слова, всякую мысль, любое правило. Например, если букву а записать двоичным числом 00001, е — числом 00010, и — 00011, к — 00100, м — 00101, т — 00110, то слово «математика» выразится двоичным числом:

00101000010011000010001010000100110000110010000001.

В введении нами был приведен отрывок из биографии ученого. Но ничего странного в тексте, по существу, нет. Лишь числа в нем даны в непривычной двоичной системе счисления. Если представить их десятичными числами, то текст будет выглядеть так:

«Еще в младших классах средней школы он проявлял себя весьма смышленым мальчиком. С задачами, которые сверстники решали полчаса, он справлялся за какие-нибудь 5—6 минут. Одаренный недюжинным умом и неиссякаемой энергией, этот счастливец окончил вуз на год раньше срока — за 3 года, и в возрасте 20 лет, будучи совсем молодым человеком, возглавил важную научно-исследовательскую лабораторию».

Все стало на место, когда мы перевели цифры в десятичную систему счисления.

В математических машинах двоичная система счисления, как мы отмечали, является основной системой. Но нам известно, что это не единственно возможная машинная система, что например, в математической машине «Сетунь» применяются троичные числа. И хотя кроме двоичной и троичной систем, в машинах производятся операции и над числами записанными в других системах, — десятичной, восьмеричной, хотя в машинах применяется также десятично-двоичная запись чисел, — все они имеют вспомогательное значение. Языком математических машин является прежде всего язык двоичных чисел.

Литература

Р. С. Гутер, Б. В. Овчинский, П. Т. Резниковский. Программирование и вычислительная математика. М., «Наука», 1965.

Я. П. Борохович и А. В. Алексеев. Математические машины и программирование. М., Сельхозгиз, 1963.

Н. П. Брусенцов, С. П. Маслов, В. П. Розин, А. М. Тишулина. Малая цифровая вычислительная машина «Сетунь». М., изд-во МГУ, 1965.

Г. Н. Берман. Счет и число. М., Изд-во Технико-теоретической литературы, 1952.

СОДЕРЖАНИЕ

Стр.

Введение ............. 3

Что известно из истории цифр....... 5

Двоичная система счисления — язык математической машины............ 10

Двоичная и троичная системы....... 15

Почему же все-таки двоичная?....... 18

Восьмеричная система счисления...... 19

Перевод чисел из одной позиционной системы счисления в другую............ 21

Перевод чисел из восьмеричной системы счисления в двоичную и обратно........ 25

Представление чисел в двоично-десятичной записи . 27

Формы представления чисел в математических машинах 27

Заключение............ 29

Литература............ 31

Георгий Осипович ЕФРЕМОВ

ЯЗЫК МАТЕМАТИЧЕСКИХ МАШИН

Редактор В. Ю. Иваницкий Худож. редактор Е. Е. Соколов Техн. редактор Т. В. Филипенкова Корректор И. И. Поршнева Обложка Н. Н. Лутохина

А 17321. Сдано в набор 6/Х 1966 г. Подписано к печати 9/XII 1966 г. Формат бумаги 60x901/16. Бумага типографская №9 3. Бум. л. I 0. Печ. л. 2.0. Уч.-изд. л. 1.60. Тираж 36 000 экз. Б. 3 . 72/7-1966 г. Издательство «Знание». «Москва, Центр. Новая пл., л. 3/4. Зак. 3128. Типография изд-ва «Знание». Москва. Центр. Новая пл., л. 3/4.

Цена 6 коп.

6 коп.

Индекс 70096

К ЧИТАТЕЛЯМ СЕРИИ «РАДИОЭЛЕКТРОНИКА И СВЯЗЬ»

В январе исполнился год, как выходят в свет брошюры серии «Радиоэлектроника и связь». За это время, судя по отзывам читателей и возросшему тиражу, серия приобрела известную популярность, вызвала к себе несомненный интерес. Есть письма, свидетельствующие о том, что некоторые читатели узнают о той или иной брошюре слишком поздно, когда она уже разошлась: издательство в этом случае не может удовлетворить их спрос.

ДОРОГИЕ ТОВАРИЩИ!

Напоминаем, что в 1967 году издательство выпустит в серия «Радиоэлектроника и связь» 12 работ. Среди них:

Сифоров В. И., чл.-корр. АН СССР. Радиоэлектроника сегодня и завтра (о достижениях и основных тенденциях развития радиоэлектроники в нашей стране и за рубежом).

Лукьяиович В. М., доктор хим. наук. Электронная микроскопия.

Федоров Б. Ф., канд. техн. наук. Оптический гироскоп (о гироскопе, основанном на лазере).

Кромский Г. И., Солуян С. И., канд. техн. наук. Лазерная локация и связь (о новых направлениях лазерной техники).

Кононов В. Г., канд. техн. наук. Вероятностные методы в радиотехнике и связи (о теории вероятностей и математической статистике на службе надежности работы линий связи и радиоэлектронной аппаратуры).

Курбаков К. И., канд. техн. наук. Электроника в стандартизации.

Чтобы получать брошюры регулярно, а к концу года собрать полную библнотечку, лучше всего подписаться на серию «Радиоэлектроника и связь», как подписываются на газеты и журналы. Ее индекс 70077. Подписная плата с 1 апреля до конца года — 81 коп.

Заказы на отдельные работы принимаются в книжных магазинах по тематическому плану издательства «Знание» на 1967 год. В тематическом плане названия брошюр серии «Радиоэлектроника и связь» помещены на страницах 70—73.

ИЗДАТЕЛЬСТВО «ЗНАНИЕ»