Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§1.8. Компьютерные арифметики

InN ■ (1/S ) • In2 S — IniV • InS • 2 • InS • (1/5) + 21niV • In S

In4 5

d2C

dS2

In N (- In2 5 • (1 /5 )+ 2 In 5)

> 0.

S=e

S=e I" S

Получили условие минимума. Следовательно, оптимальным осно

ванием позиционной арифметики является число 3, являющееся

ближайшим большим от основания натурального логарифма е.

Каждой арифметике с основанием 5 Q Q ^ Q

можно сопоставить L-дольный граф, ка

ждая доля которого содержит 5 вершин,

определяющих количественные эквива

ленты 0, 1, 2, ..., 5 — 1; число при этом

представляется ломаной, соединяющей

соответствующие цифры. На рис. 1.23

представлено число 1021 в арифметике

с основанием 5 — 3. Рис. 1.23

§ 1.8. Еомпьютерные арифметики

В естественных системах счисления, получивших наибольшее

распространение, можно записывать числа (при натуральном ос

новании) только одного знака. Для изображения чисел противопо

ложного знака в таких системах используют знак 4- или —. Более

целесообразно кодировать знак числа с помощью цифр, исполь

зуемых при записи числа. Для этого в записи числа выделяют

один специальный разряд, называемый знаковым. Цифра, стоя

щая в нем, не кодирует количественного эквивалента и не участ

вует в вычислении эквивалента с помощью функции F.

Будем кодировать знак 4- нулем, знак - цифрой 5 —1 в нулевом

разряде при задании чисел ж, |х| < 1. Для этого определим прямой

код числа х, |х| < 1 следующим образом:

_ (0.xix2...xn, х>0,

Х П I 5 - 1.®1®2- • • *п, X < 0.

Учитывая, что |ж| < 1, это соотношение можно переписать в

ВИД® , ^ п

г 1 - I х' ж- 0,

1ж]п_\ S - 1 + 1*1, *<0.

В настоящее время широко используют полулогарифмическую

форму представления чисел, или представление с плавающей

точкой.

Любое число х в системе счисления с натуральным основа

нием S можно представить (неоднозначно) как Sp^ • т(х), где

Гл.1. Основы многосортных множеств

|т(ж )| < 1. Будем называть т (х) мантиссой числа х, р(х) —

порядком числа х в системе с основанием S. Если при фиксиро

ванном S задать р(х) и т(х), то число х определяется однозначно.

Пара р(х) и т(ж) хранится в памяти ЭВМ. Для однозначного пред

ставления чисел в полулогарифмической форме обычно требуется,

чтобы мантисса удовлетворяла неравенству S-1 < т(х) < 1. Та

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

В машинном представлении числа в самом левом разряде коди

руется знак порядка, затем в ni разрядах записывается величина

порядка, далее имеется разряд для записи знака мантиссы и п%

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

Рассмотрим реализацию операций сложения, вычитания, ум

ножения и деления в позиционных арифметиках с естественным

множеством цифр. При любом основании S операции сложения и

умножения определяются таблицами выполнения этих операций

в одном разряде и правилами образования переносов в старшие

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

соответствующие разряды слагаемых. Поэтому при сложении не

обходимо еще выравнять порядки слагаемых (сдвинуть мантиссы

так, чтобы суммировать разряды с одинаковыми номерами).

При сложении выравнивание порядков происходит в результате

увеличения меньшего порядка до большего. Для того чтобы коли

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

каждое увеличение порядка на единицу компенсировать сдвигом

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

писывается выровненный порядок. При нормализации мантиссы

результата необходимо сдвигать ее вправо (на один разряд) или

влево до тех пор, пока не будут выполняться условия нормализа

ции. Для сохранения количественного эквивалента числа при этом

необходимо увеличить (при сдвиге мантиссы вправо) или умень

шить (при сдвиге мантиссы влево) порядок результата на число

единиц, совпадающее с числом сдвигов.

П рим ер 1.7. Вычислим сумму двух количественных эквивалентов 24.17 и

32.98 в арифметике 5 = 5; алфавит цифр — {0, 1, 2, 3, 4}.

Для задании этих чисел в полулогарифмической форме в памяти компью

тера определим их порядки и мантиссы в заданной арифметике с точностью

представления мантисс до 5-4 ;

24.17 -¥ [44.04]5:

целая часть — дробная часть —

_ 24 I 5 0.17 х 5 = @.85

20 4 I 5 0.85 х 5 = @.25

@ О О

Следовательно, р(44.04) = 2, т(44.04) = 0.4404,

[44.04]* -4 5* х 0.4404.

§1.8. Компьютерные арифметики

38.92 -¥ [112.44]*:

целая часть —

_ 32 [_5_

30 _ 6 15

@ _L _ lll_

Ф JL 0

дробная часть —

0.98 х 5 = @.90

0.90 х 5 = @.50

Следовательно, р(112.44) = 3 , т(112.44) =0.1124 (пятый разряд после точки не

пишем, так как заданная точность 5-4 ), Т аб л и ц а 1 16

[112.44]* —► 53 х 0.1124.

Сложение цифр в пятиричной арифме

тике определяется табл. 1.16.

В клетке [«, j] табл. 1.16 левая цифра

указывает значение перекоса в старший

разряд, правая — значение суммы в со

ответствующем разряде.

Выравниваем порядки до большего:

[44.04]* -+ 52 х 0.4404 -¥ 53 х 0.0441

(единица в младшем разряде получилась после округления),

[112.44]* -+ 53 х 0.1124.

Производим сложение мантисс согласно табл. 1.16:

, 0.0441

1 2

00 01 02 03 04

02 03

10 11

4 04

Следовательно, [44.04 + 112.44]*

найденной суммы равен

г 0.1124

0.2120

53 х 0.2120. Количественный эквивалент

5 х 0.2120

5* х (2

5"1 + 1 • 5"а + 2 5-3 + 0.5-4 ) =

= 2 • 5а + 1 • 51 + 2 • 5° = 57.0.

Порядок р суммы равен 3, мантисса суммы — 0.2120.

При вычитании двух чисел возникают трудности, связанные с

Заемом единиц в старших разрядах. Эта операция плохо реали

зуется в современных ЭВМ для систем счисления с естественным

множеством цифр и натуральным основанием. Для систем с отри

цательным основанием или систем с натуральным основанием и

симметрической (симметрической) совокупностью цифр эта опера

ция осуществляется просто: вычитаемое инвертируется (т. е. вме

сто записи числа —а берется запись числа —о в этой системе), и

полученные коды суммируются. Для систем с натуральным осно

ванием и естественным множеством цифр операция алгебраиче

ского сложения осуществляется с помощью дополнительного или

обратного кодов этих чисел.

Гд. 1. Основы многосортных множеств

Заменим операцию вычитания у — х операцией сложения у и

5 — х с последующим уменьшением результата на величину, рав-

Введем понятие дополнительного кода числа г.

Операцию вычитания можно заменить операцией сложения и

на основании следующего соотношения:

Отсюда получаем определение обратного и дополнительного кодов

Дополнительный код отрицательного числа х Х\Х2...ХП,

|*| < 1, имеет следующий вид:

Таким образом, имеем следующие правила образования

обратного и дополнительного кодов для отрица

тельных чисел.

1. Для получения обратного кода отрицательного числа необ

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

этого разряда на цифру, дополняющую ее до 5 - 1. В знаковом

разряде следует записать цифру

5 —1.

2. Для получения дополнительного кода отрицательного числа

необходимо прибавить единицу к младшему разряду его обратного

кода.

Отсюда имеем соответственно следующие правила алгеб

раического сложения.

1. Для алгебраического сложения чисел ж и у произвольного

знака в системе счисления с натуральным основанием и естествен

ным множеством Цифр достаточно перевести запись этих чисел в

дополнительный код, просуммировать полученные коды по прави

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

переноса из знакового разряда, если таковая возникает. Получен

ный результат представляет собой дополнительный код алгебраи

ческой суммы чисел х и у.

y -x = y+ (S -S -n-x )-S + S -n.

числа х:

[ж]д = [ж]о + 5 п, х < 0.

§1.8. Компьютерные арифметики

2. Для алгебраического сложения чисел ж и у произвольного

знака в системе счисления с натуральным основанием S и есте

ственным множеством цифр достаточно перевести запись этих чи

сел в обратный код, просуммировать полученные коды по прави

лам сложения чисел в системе с основанием S и добавить единицу

в младший разряд полученного выражения, если при суммирова

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

результат представляет собой обратный код истинной (алгебраи

ческой) суммы чисел ж и у.

П рим ер 1.8. Вычислим алгебраическую сумму количественных эквива

лентов 19.43 — 28.57 в троичной арифметике S = 3 и естественном алфавите

цифр {0, 1, 2}, используя дополнительный код.

Определим запись числа 19.43 в этой арифметике с точностью до З-3 :

целая часть — дробная часть —

_ 19 I 3 0.43 х 3 = ф .29

18 _6 |3 _ 0.29 х 3 = @.87

Ф J L _ 2 (JL 0.87 х 3 = @.41

‘ JL 0

19.43 -+ [201.102]з -4 З3 х 0.201102.

Аналогично определяем запись чнсла 28.57:

целая часть — дробная часть —

_ 28 I 3 0.57 х 3 = ф.71

27 9 |3 0.71 х 3 = @.13

ф _9_ _3 |3 _ 0.13 х 3 = @.39

_3_ 1 [3_

0 0

28.57 -4 [1001.120]3 -+ З4 х 0.1001120.

Выравниваем порядки до большего:

19.43 -+ 3 4 х 0.0201102,

28.57 З4 х 0.1001120.

Заменяем вычитание сложением в дополнительном коде:

д 0.0201102

2.1221102

[2.1221102] — дополнительный код суммы,

[

2.2122211]о — обратный код суммы,

—0.0100011]з — мантисса суммы.

В результате количественный эквивалент суммы равен —9.14.

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

г—j 0.0201102

0 2.1221102

[2.1221102]а —*■ [—0.0100011], — мантисса суммы.

3 В. А. Горбатов

Гл. 1. Основы многосортных множеств

При умножении необходимо просуммировать порядки сомно

жителей, произвести умножение мантисс по правилам умножения

чисел, нормализовать результат и, если произошел сдвиг ман

тиссы произведения, изменить соответственно порядок произве

дения. Знак произведения определяется отдельно естественным

образом: если сомножители имеют одинаковые знаки, то произве

дение — положительное число, в противном случае — отрицатель

ное.

П рим ер 1.9. Вычислим произведение количественных эквивалентов

12.13 х 17.21 в арифметике с основанием 4 и естественным алфавитом цифр

{О, 1, 2, 3}.

Представим эти количественные эквиваленты в этой арифметике с точностью

до 4

-а.

целая часть —

_ 12 I 4

12 3 | 4

w @ О О

дробная часть —

0.13 х 4 = @.52

0.52 х 4 = @.08

12.31 [30.02]< -+ 4а х 0.3002;

дробиая часть —

0.21 х 4 = @.81

0.84 х 4 = @.36

целая часть —

_ 17 I 4

16 _4 14

Ф JL _1 Li.

_0_ О

17.21 -► [101.03]4 -+ 43 х 0.1011.

Порядок произведения равеи 5: 2 + 3 = 5.

Правила умножения цифр определены в табл. 1.17, где в клетке [•', j] левая

цифра соответствует переносу, правая — значению произведения в этом разряде.

Согласно табл. 1.17 произведем умножение

мантисс:

Т абл и ц а 1.17

0 00 00 00 00

00 01 02 03

2 00 02 10 12

3 00 03

12 21

0.3002

0.1011

3002

0.03101022

После нормализации получим, что произведение равно 44 х 0.3101; это определяет

количественный эквивалент, равный

4* х (3 • 4-1 + 1 • 4-а + 0 • 4-3 + 1 • 4-4 ) = 3 • 43 + 1 • 4а + 0 • 4-1 + 1 • 4° = 209.

При делении из порядка делимого вычитают порядок делителя.

Деление мантисс заменяют вычитанием делителя из делимого до

тех пор, пока в результате очередного вычитания не будет полу

чена отрицательная разность. Затем прибавляют делитель к отри

цательной разности (эта операция называется восстановлением

§ 1.8. Компьютерные арифметики

остатков) и в качестве цифры частного записывают число вы

читаний делителя без учета последнего вычитания. После этого

роль делимого начинает играть остаток, а роль делителя — преж

ний делитель, сдвинутый на один разряд вправо, и т. д. Мантиссу

частного нормализуют и соответственно изменяют порядок част

ного. Знак частного определяют аналогично определению знака

произведения.

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

3.33 в двоичной арифметике S = 2 с алфавитом цифр {0, 1}.

Определим запись чисел 8.17 и 3.33 в двоичной арифметике, вычисляя дроб

ную часть с точностью до 2~*:

целая часть — дробная часть —

0.17 х 2 = @.34

0.34 х 2 = @.68

0.68 х 2 = ф .36

0.36 х 2 = @.72 Ч'

♦ 2 х 0.10000010;

дробная часть —

0.33 х 2 = @.66

0.66 х 2 = ф.32

0.32 х 2 = @.64

0.64 х 2 = ф .28 ф

3.33 -» [H.OlOlJs -+ 2 s x 0.11010100.

Порядок частного равен 2: 4 — 2 = 2.

Вычислим мантиссу частного, используя обратный код; прн этом знак будем

кодировать двумя цифрами для того, чтобы правильно определять нарушение

нормализации мантиссы: + кодируем 00, — кодируем 11.

Первый цикл алгоритма:

00.10000010

00.11010100

Шо

00.10000010

11.00101011

11.10101101

Знак разности отрицательный, следовательно, целая часть частного при делении

мантисс равна 0:

Произведем операцию восстановления:

11.10101101

00.10000001

100.10000001

________

Сумматор обратного кода является циклическим сумматором: перекос из знако

вого разряда суммируется с цифрой младшего разряда. Сумматор дополнитель

ного кода является ациклическим: перенос из знакового разряда не суммируется

с цифрой младшего разряда, перенос “пропадает”.

Гл. 1. Основы многосортных множеств

После восстановления получим уменьшаемое 00.10000010.

Второй цикл алгоритма:

00.10000010 |— | 00.10000101

00.01101010 Ш о 11.10010101

100.00010111

_________

00.00011000

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

ного — 1:

Го-1 1 I 1 1

Третий цикл алгоритма:

00.00011000 |— | 00.00011000

00.00110101 11.11001010

11.11100010

Знак разности отрицательный; следующая цифра мантиссы частного — 0:

1 0

Производим восстановление остатка и переходим к вычислению четвертой

цифры частного.

Четвертый цикл алгоритма:

00.00011000 |— | 00.00011000

00.00011010 11.11100101

11.11111101

Знак разности отрицательный, следовательно, четвертая цифра мантиссы част

ного — 0:

0 0

После восстановления остатка вычисляем пятую цифру мантиссы частного:

00.00011000 |—j 00.00011000

00.00001101 Ш ® 11.11110010

100.00001010

I____________t

00.00001011

Знак разности положительный, следовательно, пятая цифра — 1:

0 0

Для правильного округления аналогично вычисляем шестую цифру; этой

цифрой является 1. Отсюда мантисса частного имеет вид

Искомое частное есть 22 х 0.1010; оно соответствует количественному экви

валенту 2.5:

2а х (1 • 2-1 + 0 • 2-а + 1 • 2_3 + 0 • 2-4 ) = 2 + 2-1 = 2.5.

Как уже отмечалось, система счисления является весомознач

ной, если для каждого разряда с номером j можно указать такое

§1.8. Компьютерные арифметики

число pj, что количественный эквивалент, который сопоставля

ется цифре а,-, записанной в этом разряде, равен pj ■ [о,], где [а,] —

количественный эквивалент, сопоставляемый этой же цифре в ну

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

В вычислительной технике представляет интерес двоично-де

сятичные системы счисления, в которых каждая десятичная ци

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

каждый разряд десятичной записи замещается четырьмя разря

дами. Бели этим четырем разрядам соответствуют некоторые веса,

то имеет место весомозначная система для этих четырех двоич

ных разрядов.

При использовании двоично-десятичных систем в ЭВМ жела

тельно, чтобы кодирование (оно неоднозначно, так как для коди

рования десяти цифр можно использовать любые из 16 тетрад —

четверок из нулей и единиц) удовлетворяло некоторым ограниче

ниям. Приведем пять основных требований, которые сформули

рованы Рутисхаузером.

Единственность. Необходимо однозначное соответствие цифр

и тетрад. Бели это требование не выполнено, то невозможно ко

дирование и декодирование чисел.

Упорядоченность. Большим десятичным цифрам должны

соответствовать большие (по количественному эквиваленту) тет

рады. Выполнение этого требования необходимо при сравнении

кодированных чисел.

Четность. Четным десятичным цифрам должны соответство

вать четные тетрады (тетрады, у которых в крайнем правом раз

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

Дополнительность. Если цифры десятичной системы тако

вы, что сумма их равна девяти, то им должны сопоставляться те

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

Друга заменой единиц на нули, а нулей на единицы. Выполнение

Этого требования необходимо для того, чтобы ввести в двоично

десятичной системе дополнительный или обратный код.

Весомозначность. Должны существовать четыре веса р\, р2,

рз, р\ таких, что если десятичной цифре х сопоставлена тетрада

ai отгадок, то имеет место равенство

* = <*1 • Р\ + »2 • Р2 + «3 • Рз + «4 • Р4, а . = 0, 1.

Кодирование, удовлетворяющее всем пяти требованиям, назы

вается совершенным.

Условимся через Т(х) обозначать тетраду, сопоставимую деся

тичной цифре х. Рассмотрим правила сложения для чисел, запи

как

Гл. 1. Основы многосортных множеств

санных в двоично-десятичной системе. Пусть в десятичной сис

теме взяты цифры ж и у. Тогда либо х + у — некоторая новая

цифра этой системы (если ж + у < 10), либо результатом сумми

рования этих цифр является цифра, соответствующая ж-)-у - 10, и

возникает единица переноса в следующий разряд. Тогда правила

сложения в двоично-десятичной системе имеют вид

Здесь прибавление 16 соответствует переносу единицы в следую

щий разряд (перенос в правый разряд тетрады, стоящей слева от

данной). Как следует из этого соотношения, при суммировании

чисел в такой системе необходимо вносить поправки.

Пусть, например, кодируется каждая десятичная цифра ее за

писью в двоичной системе с использованием четырех двоичных

разрядов. В этом случае цифра 5 будет закодирована тетрадой

0101. Такой способ кодирования называется кодом прямого за

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

замещения Т(х) = ж, можно записать

Таким образом, при суммировании в коде прямого замеще

ния необходимо произвести суммирование в каждой паре тетрад

по правилам двоичного сложения, учитывая перенос между те

традами, если последний возникает. После этого в те разряды,

где сумма кодированных цифр превысила 10, следует добавить по

правку ОНО. Проиллюстрируем это на следующем примере.

Пусть требуется в коде прямого замещения найти сумму чисел

205 и 768. Выполним необходимые операции:

205 — 0010 0000 0101 кодирование

+ 768 — 0111 0110 1000

, 1001 0110 1101 первое суммирование

0000 0000 0110 поправка

973 — 1001 0111 0011 результат

Код прямого замещения удовлетворяет всем требованиям Ру-

тисхаузера, кроме четвертого. Нарушение этого требования не по

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

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

Для выполнения свойства дополнительности будем кодировать де

сятичную цифру ж тетрадой Т (ж), равной ж + 3. Полученный код

называется кодом с избытком 3, или кодом Штибитца. В этом

х + У < Ю,

10) -I-16, х + у > Ю.

ж + у < Ю,

ж + у > 10.