Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 12
Текст из файла (страница 12)
Пример 1.6. Предстзвнхь полпчественный зввнвзленх (83.16]ез в восьыеой системе а = 8 с злфзвнтом днфр 10, 1, 2, ..., 7) с течносгыо до 8 з. Используя вышеприведенные алгоритмы, получаем ~Дз Д 2П3 Е2 Дз [123]а -з 1 8 +2 8 +3 8 =[83]ае; 0.16Х8=1,28 0.28Х8=2,24 ДЕ~ ЕД ~1 Д2 [0.12] = 1 . 8 ~ + 2 8 з ш 0.16. Часто для повышения ннфорызлнонной бевопвсностн фнрыы заменяют взв влфзвнг пнфр, хзв н основание зрнфыетнвн.
Рзссыотрны перевод число 8ь16 вз десятнеюй зрнфыепавн в восьмеричную с злфзвнтом пнфр (6, 5, 4, 3, 2, 1, О, Ц, где полнчественный аввнззлент пнфр тозов: [6] = -Б, [5] = -5,, [4] = -4, (3] ю -3, [2] ш-2, [1]=-1, [0] юо, [1] =1. Для попоной ззпнсн представим волнчественный зпвнвзлент цифр есхе- ственного злфзвнхз (О, 1, 2, ..., 7), нсполъзуя волнчественные зпвнвзленты пнфр издонного злфзвнтз: (0]е [0]е~ [1]е — [1]ез [2]е [2]е ° Для овределення правой честя последнего вырзнення заметим, чхо 2 = 8 — 6 = ш 8+ (-6) -+ [16]„следовательно, [2], = (16],. Анзлштачно получаем (3], = = [16]е~ [4]е = [14]е~ [5]е = [13]е, [6]е = [12]е~ [7]е = [11]е. Подставляя нзйденные соотношения в запись [123.12]„получзеы 123.12 -+ 100.00 16О.ОО + 015.00 000.10 6 255.26 -+ 1600 00 + 0066.06 оооо Д~ [1654.66], Колнчестзенный аввнввлепт 83.16 в восьмеричной системе счисления с зл- фзвнтоы пнфр [6, 5, 4, ..., О, Ц будет представим в виде 1664.66.
Действительно, [1664.66]а-+1.8 — 6 8 — 5 8 4 8а — 6 8 — 6 8 аш ш 84 — 0.84 = 83.16. В 1.8. Комиьютериые арифметики Гл. 1. Осиаоы миовосортиых миовкесте 60 Одределнм вввнсь величественного эввнввлевтв 83.16 в системе счисления с осюювинем 0.125 н елаввитам вирр (6, $, 4, ..., О, 1). Звмечвя, что 0.12$ = 8 ~, волучвем, что величественные эввнввленты рьврядов в снстемвд счисления с основеннем 8 н 8 ~ симметричны относительно Вт В' Ве В-' В-т <В >т В т<В ~>~ В <В э>е <В э> аэ<В ~> ~ Вт Рнс. 1.22 пулевого рверядв (рнс.
1.22). Отсюдь волучвем искомую вввэюь 83.16 в виде [684381]еаээ. Определим оптимальное в смысле сложности реализации основание Я-позиционной арифметики. Под слохсносн>ью реалиэо«ии Сбудем понимать произведение разрядов Ь на количество значений каждого разряда Я. Количество чисел Ж, кодируемое Я-ичным Ь-разрядным вектором, равно 11< = Яь. (1.8) Найдем значение Я, при котором сложность реализации С минимальна: ппп Ь Я. э Логарифмируя (1.8), получаем 1и Ж = Ь ° 1п Я, Х = 1п Ф/1и Я. Отсюда сложность реализации имеет вид С = Я ° 1пМ/1пЯ. Найдем условие экстремума С: <1С 1пФ 1пЯ вЂ” Я (1/Я) 1пЖ е[Я 2 Я отсюда 1пЯ вЂ” 1=0, Определим, является ли Я = е условием минимума или максимума: 1пФ (1/Я) ° 1птЯ вЂ” 1пФ 1пЯ 2 1пЯ (1/Я)+21пФ 1пЯ ,1пеЯ <У'С ~ 1п Ф(- 1п Я ° (1/Я) + 2 1п Я) ~ НЯ [Эм, 1пе Я Эже Получили условие минимума. Следовательно, оптимальным основанием позиционной арифметики является число 3, являющееся ближайшим большим от основания натурального логарифма е.
Каждой арифметике с основанием Я можносопостапнть Е дальный граф, каждая доля которого содержит Я вершин, определяющих количественные эквива- 1 ленты О, 1, 2, ..., Я вЂ” 1; число при эхом представляется ломаной, соединяющей соответствующие цифры. На рис. 1.23 представлено число 1021 з арифметике с основанием Я = 3. Рнс. 1.23 $ 1.8. Компьютерные арифметики В естестпенных системах счисления, получивших наибольшее распространение, можно записывать числа (при натуральном ос- новании) только одного знака. Для изображения чисел противопо- ложного знака в хаких системах используют знак + илн —.
Более целесообразно кодировать знак числа с помощью цифр, исполь- зуемых при записи числа. Для этого в записи числа выделяют адин специальный разряд, называемый энаковым. Цифра, стоя- щая в нем, не кодирует количественного эквиналента и не участ- вует в вычислении эквивалента с помощью функции Г. Будем кодировать знак + нулем, знак — цифрой Я-1 в нулевом разряде при задании чисел х, [х[ < 1. Для этого определим прямой код числа х, [х[ < 1 следующим образом: О.х<хх...х„, х > О, [х]„ = Я вЂ” 1.х<хх...х„, х < О.
Учитывая, что [х[ < 1, это соотношение можно переписать з виде х, х>0, (х]„ = Я - 1+ [х[, х < О. < В настоящее время широко используют полулогарифмнческую форму представления чисел, или представление с плавающей точкой. Любое число х в системе счисления с нахуральным основа- нием Я можно предсхавить (неоднозначно) как Яв< 1 нэ(х), где Гл. 1. Основы многосоршныл мнолсесто ]ш(и)] < 1. Будем называть ш(х) манпьиссоб числа х, р(х)— яорлдком числа х в системе с основанием Я. Если при фиксированном Я задать р(х) и пь(х), то число х определяется однозначно. Пара р(х) и хя(х) хранится в памяти ЭВМ.
Для однозначного представления чисел в полулогарифмическай форме обычно требуется, чтобы мантисса удовлетворяла неравенству Я 1 < пь(х) < 1. Такая мантисса называется иормалиэованиоб. В машинном представлении числа в самом левом разряде кодируется знак порядка, затем в п1 разрядах записывается величина порядка, далее имеется разряд для записи знака мантиссы и яг разрядов для записи величины мантиссы. Рассмотрим реализацию операций сложения, вычитания, умножения и деления в позиционных арифметиках с естественным множеством цифр.
При любом основании Я операции сложения и умножения определяются таблицами выполнения этих операций в одном разряде и правилами образования переносов в старшие разряды. При этом необходимо, чтобы в операции участвовали соответствуюшие разряды слагаемых. Поэтому при сложении необходимо еше выравнять порядки слагаемых (сдвинуть мантиссы так, чтобы суммировать разряды с одинаковыми номерами). При сложении выравнивание порядков происходит в результате увеличения меньшего порядка до большего.
Для того чтобы количественный эквивалент числа при этом не изменялся, необходимо каждое увеличение порядка на единицу компенсировать сдвигом мантиссы вправо на один разряд. Полученному результату приписывается выровненный порядок. При нормализации мантиссы результата необходимо сдвигать ее вправо (на один разряд) или влево до тех пор, пока не будут выполняться условия нормализации. Для сохранения количественного эквивалента числа при этом необходимо увеличить (при сдвиге мантиссы вправо) или уменьшить (при сдвиге мантиссы влево) порядок результата на число единиц, совпадающее с числом сдвигов. Пример 1.7. Вычислим сумму двух количественных зкзнввлентоз 24.17 н 32.98 з арифметике 8 и 5; алфавит дифр — (О, 1, 2, 3, 4).
Для задания атил чисел з лолулохармрмяческей форме з памяти комдьюхера озределим ил порядки и мантяссы з заданной арифметике с точностью зредстазлення мантисс до 5 ~; 24.17 ~ [44.04]сс целая часть— дробная чвсть— 24 ]5 0 17 х 5 = © 8$ го «[$ Озбнб=®гб Е 0 0 е Следозвтелыю, р(44.04) = 2, т(44.04) = 0.4404, [44.04]ь -+ бт х 0.4404, $1.8. Компьюшерные орифмгтпики 38.92 -+ [112.4«]а: целая часть— дробная часть— 0.98 н $ = ®.90 0,90 х $ = ®.$0 32 [5 <р оо Ф 63 Следозвтелыю, р(112.44) = 3, тл(112.44) = 0.1124 (зятый разряд восле точки ие нищем, так как аадвниая точность 5 ~), Таблица 1.16 [112.44]ь -+ $ х 0.1124.
+ 0 1 2 3 4 Слоиенне ввэр з затирнчной арнфме- 0 00 01 02 03 04 тиве озределяехся табл. 1.16. 1 01 02 03 04 10 В клетке [~', у] табл. 1.16 левая цифра г 02 03 04 указывает аивчеине зереноса в старший рааряд, правая — значение сухаая з соответствующем разряде. 4 04 10 11 12 13 Выравниваем зарядки до большего: [44.04]ь -+ $ х 0.4404 ~ 5 х 00441 (елиницв з младшем разряде золучилась восле озрутления), [112.44]ь -+ 5е к 0.1124. Пронвводим слоиение мантисс сохлвмо хабл. 1.16: 0.0441 + 1~ 1122 О. 2120 Следовательно, [44.04+ 112.44]ь -ь ба х 0.2120.
Колнчесхзешияй аквизажкт найденной суммы равен 5 х0.2120-+5 х(2 $ +1 5 +2 ° $ а+0.$ )= =2 ° бе+1 ° $ +2 ° бе=57.0. Порялок р суммы равен 3, мантисса суммы — 0.2120. При вычитании двух чисел возникают трудкости, связанные с заемом единиц в старших разрядах. Эта операция плохо реализуется в современных ЭВМ для систем счисления с естественным множеством цифр и натуральным основанием. Для систем с отрицательным основанием или систем с натуральным основанием и симметрической (симметрической) совокупностью цифр эта операция осушествляется простш вычитаемое инвертируется (т. е, вместо записи числа -а берется запись числа -а в этой системе), и полученные коды суммируются.' Для систем с натуральным основанием и естественным множеством цифр операция алгебраического сложения осушествляется с помошью дополнительного или обратного кодов этих чисел.
ГЛ.1. Основы лмогосоро»ныл лиолсесюа Заменим операцию вычитания у — х операцией сложения у и Я вЂ” х с последующим уменьшением результата иа величину, ранную Я: у — х = у+ (Я вЂ” х) — Я. Введем понятие дояолиияггльного кода числа ж (х, х>0, (*)д=]Я'+х, х<0'. Операцию вычитания можно заменить операцией сложения и на основании следующего соотношения: у — х = у + (Я вЂ” Я " — х) — Я+ Я ". Отсюда получаем определение обратного и даполнительнога кодов числа х: ]х, х>0, (х]д = (х]о+ Я ", х < О. Дополнительный код отрицательного числа х ь4 хгхт...х„, [х] < 1, имеет следующий вид: (х]л — (Я вЂ” 1). (Я вЂ” 1 — хг) (Я вЂ” 1 — хт)...
(Я вЂ” х„). Обратный код этого числа имеет вид (х1о = (Я вЂ” 1).(Я вЂ” 1 — х1)(Я вЂ” 1 — хт) ° ° .(Я вЂ” 1 — ха). Такимобразом, имеемследующие правила образования обратного и дополнительного кодов для отрицательных чисел. 1. Для получения обратного кода отрицательного числа необходимо в каждом разряде Я-ичной записи числа заменить цифру этого разряда на цифру, дополняющую ее до Я вЂ” 1. В знаковом разряде следует записать цифру Я вЂ” 1. 2.
Для получения дополнительного кода отрицательного числа необходимо прибавить единицу к младшему разряду его обратного кода. Отсюда имеем соответственно следующие правила алгебраического сложения. 1. Для алгебраического сложения чисел х и у произвольного знака в системе счисления с натуральным основанием и естественным множеством цифр достаточно перевести запись этих чисел в дополнительный код, просуммировать полученные коды по правилам сложения чисел в системе с основанием Я и отбросить единицу переноса из знакового разряда, если таковая возникает. Полученный результат представляет собой дополнительный код алгебраической суммы чисел х и у, 5 1.8. Комяьюлгериые арифа»еогихи 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
