AOP_Tom2 (1021737), страница 98
Текст из файла (страница 98)
+2ц с~ >ее > >е~ >О. ь 18. (МЗО) Разработайте схему выделения памяти для промежуточных результатов при выполнении операций умножения по рекурсивному алгоритму, основанному на уравнении (2), Заданы два Лдразрядных целых числа о и с, каждое из которых занимает Х разрядов памяти. Покажите, как ограничить вычисления, чтобы произведение ио оказалось в последних значащих 2Л' разрядах (ЗХ+ О(1абХ))-разрядной области рабочего пространства. ь 19. (МЯЯ) Покажите, как вычислить ос шабто при ограниченном количестве операций, оговоренных в правилах упр. 3.2.1.1-11, если имеется возможность проверить, будет ли один операнд меньше другого. Оба числа и и и переменные, но т постоянно.
Указание. Рассмотрите вопрос декомпозиции в (2). 4.4. ПРЕОБРАЗОВАНИЕ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ ЕСЛИ ПЫ НАШИ ПРЕДКИ, ИЗОбретая арифметику, вели счет при помощи двух рук нлн восьми пальцев, а не десяти "цифр", у нас никогда бы не было хлопот с разработкой программ двоично-десятичного преобразования чисел. (И, возможно, мы бы никогда столько не узнали о системах счисления.) В этом разделе будут рассмотрены вопросы, связанные с преобразованием чисел из позиционной системы счисления по одному основанию в позиционную систему счисления по другому основанию, Конечно, этот процесс наиболее важен для двоичных компьютеров при преобразовании входных данных, представленных в десятичном формате, в двоичный формат и преобразовании результатов из двоичного формата обратно в десятичный. А. 'Четыре основных метода.
Преобразование чисел из двоичной системы счисления в десятичную и обратно — одна из наиболее машинно-зависимых операций, поскольку разработчикам компьютеров приходится постоянно изобретать различные способы аппаратной реализации этой операции. В связи с этим далее будут рассматриваться только основные принципы решения данной задачи, на основании которых программисты могут выбирать процедуры, наиболее подходящие для реализации на компьютере конкретной конфигурации. Будем предполагать, что операции преобразований выполняются только с неотрицательнь|ми числами, так как манипулирование знаками легко учесть. Предположим, что выполняется преобразование из системы счисления по основанию 6 в систему счисления по основанию В.
(Обобщение лля систем счисления со смешанным основанием рассматривается в упр. 1 и 2.) Большинство процедур преобразования из одного основания в другое основано на операциях умножения и деления, использующих один из четырех методов, которые описываются ниже.
Два первых метода применяются для преобразования целых чисел (разделяющая точка расположена справа), а два других — для дробных частей чисел (разделяющая точка расположена слева). Чаще всего нельзя точно выразить конечную дробную часть по основанию 6 (О.и гц т...и )э в виде конечной дробной части по основанию В (О.Г,П э... П м)я. Например, десятичная дробь —,' в двоичном формате. представляется бесконечной дробью (0.0001100110011... )э.
В связи с этим приходится иногда округлять результат до М разрядов. Метод 1, а (Деление на В с использованием представления чисел в формате по основанию 6). Для заданного целого числа и можно получить представление в формате по основанию В вида (... 1ГтП, Ье) и, выполняя сгэ = и шоб В, сг1 — — (и/В) шоб В, сг» = Ци/В)/В) шоО В, до тех пор, пока не окажется (... Ц и/В1/В1 ... /В) = О. Метод 1, Ь (Умножение на В с использованием представления чисел в формате по основанию 6).
Если представление числа и по основанию 6 имеет вид (и,„... игие)м то можно, воспользовавшись арифметическими операциями с числами, которые представлены в формате по основанию В, получить полипом и,„Ь"'+ .+и16+ие = и в виде ((...(и Ь+ и 1) Ь+ ..)Ь+и1) Ь+по. Метод 2, а (Умножение на Ь с использованием представления чисел в формате по основанию В). Для данного дробного числа и можно вычислить значения разрядов ( сг-гà — г )в его представления по основанию В следующим образом: Г г = (иВ), П г = ((иВ)В), (/ г = (((иВ)В)В), где (х) означает хшоб1 = х — (х). Чтобы округлить результат до АХ разрядов, вычисления можно прервать после получения Т/ и, причем егли (... ЦиВ)В)...
В) больше —,„то значение Г м следует увеличить на единицу, (Заметим, однако, 1 что эта операция может привести к необходимости выполнения переносов, которые должны быть при помощи арифметических операций по основанию В включены в результат. Было бы проще перед началом вычислений прибавить к исходному числу и константу -В, но это может привести к неправильному результату, если в компьютере число -В ' не может быть точно представлено в формате по -лт основанию Ь.
Заметим также, чта возможна округление результата до (1.00 .0)в, если Ьп~ ь 2Вм ) В упр. 3 рассматривается обобщение этого метода на случай переменного А/, достаточно большого для представления исходного числа с заданной точностью. В такой ситуации проблема переносов не возникает.
Метод 2, Ь (Деление на Ь с использованием представления чисел в формате по основанию В). Если чисто и представлена по основанию Ь в виде (О.и ги г... и,„)м то можно, используя арифметические операции по основанию В, вычислить и г Ь ~+ и гЬ г-ь +и „,Ь в виде ((... (и,/Ь+ иг )/Ь+ + и. э)/Ь+ и 1) /Ь. Необходимо внимательно следить за погрешностями, возникающими при усе ~ениях или округлениях во время выполнения операции деления на Ь; опи, как правило, незначительны, но это бывает не всегда. Подведем итоги.
Методы 1, а; 1, Ь; 2, а н 2, Ь предоставляя>т по два возможных способа преобразования целых и дробных чисел. И, конечно, существует вазможность выполнять преобразования целых чисел в дробные и наоборот путем умножения или деления на соответствующую степень Ь или В. Поэтому для выполнения преобразования имеется на выбор по крайней мере четыре метода. В. Преобразование с однократной точностью.
Чтобы проиллюстрировать эти методы, предположим, что И1Х вЂ” двоичный компьютер и нужно преобразонать неотрицательное целое число и, представленное в двоичном формате, в десятичный формат, т. е. получить Ь = 2 и В = 10. Метод 1, а можно запрограммировать следующим образом. ЕИТ1 О Присвоить у < — О. ЕОХ 0 ЕНТА 0 Присвоить гАХ+- и. 1Н 017 =10= (гЛ,гХ) +- ((гЛХ/10),гАХша010). ЯТХ АИЯНЕК,1 С', ~- гХ 1ИС1 1 1 З вЂ” /+1. ЯКАХ б гАХ +- гЛ. 1ХР 1В Повторять да тех пор. пока я результате не получим нуль.
3 Для вычисления А/ разрядов необходимо затратить 18И + 4 циклов. В методе 1, а используется операция деления на 10. В методе 2, а используется умножение на 10., так что программа, реализующая этот метод, может выполняться немного быстрее. Но, применяя метод 2, а, нужно иметь дело с дробями, а это приводит к интересной ситуации, Пусть ш — размер машинного слова, и положим, что и < 10" < ш.
При помощи одного деления можно найти д и г, где ши = 10"9+ г, 0 < г < 10". (2) Если же применить метод 2, а к дроби (д + 1)/ш, то за и шагов получим разряды числа и слева направо, так как ~10" — ~ = ~и+ ~ = и. (Эта идея предложена П. А. Саметом (Р. А. Яашег) и опубликована в жу.риале Яойв аге РгасВсе Хг ЕхреНепсе 1 (1971), 93-96.) Приведем соответствующую М1Х-программу.
ЮОЧ 1ОА 10Х 017 ЛОЧ ЕМТ1 2Н МШ. 0710 О =10" = =10"= ЕМКОЕ и-1 =10= Удостовериться в отсутствии переполнения. гАМ ~- шв+ 10". гА +- д -ь 1, гХ ~ — г. Переход при и > 10". Присвоить з + — в — 1. Представим, что разделяющая точка находится слева, гА = х. Присвоить 1', ь- '110х). х +- 110х).
з 4-1 — 1. Повторить для и > У > О. (4) ЯТА АМЯМЕК,1 ЯЕАХ Я ОЕС1 1 01ММ 2В 1 1 1 — <х< — + —, 10 10 ш' Данная программа немного длиннее предыдущей, н на ее выполнение требуется 16и + 19 циклов, так что при п = М > 8 она выполняется бьштрсе программы (1). Однако при наличии ведущих нулей программа (1) будет выполняться быстрее. Программа (4) в представленном виде при 10 < ш < 10 т~ не может использоваться для преобразования целых чисел и > 10"', так как нужно принять и = т+ 1. В этом случае ведущий разряд числа и можно получить, вычисляя '1и~10""): после этого можно преобразовать число и шог1 10"' по приведенному выше методу при п = тп.
То обстоятельство, что разряды результата могут быть получены слева направо, может оказаться полезным в некоторых приложениях (например, прн последовательном выводе разрядов результата на печать). Итак, метод, применимый для дробей, можно использовать и для преобразований целых чисел, хотя, применив неточное деление при преобразованиях, придется выполнять численный анализ метода. В методе 1, а деление на 10 можно заменить двумя умножениями.
Это может оказаться существенным, поскольку преобразование оснований часто выполняется в компьютерах-"сателлитах', в которых отсутствует встроенная процедура деления. Если предположить, что х — приближение к —, так что 1 го то легко доказать (см. упр. 7), что 1их) = '1и/10) или 1и/10) + 1, пока 0 < и < Вв. Поэтому при вычислении и — 10(их) можно определить значение 1и/10): '1и/10) = 1их) — '(и < 10 1их) ~.
(5) Одновременно можно определить и юое( 10. И1Х-программа, выполняющая преобразование с использованием (5), приведена в упр. 8. На вычисление каждого разряда она затрачивает около 33 циклов. Метод 1, а может быть с успехом применен и в компьютерах, в которых отсутствуют встроенные команды как деления, так и умножения, путем выполнения операций сдвига и сложения, как продемонстрировано в упр. 9. Другой способ преобразования из двоичного представления в десятичное зак.лючается в использовании метода 1, Ь, но при этом необходимо имитировать удвоение в десипзичиай системе счисления.
Этот способ в общем случае наиболее подходит для аппаратной реализации в компьютере; тем не менее процесс удвоения в десятичной системе счисления можно и запрограммировать при помощи операций двоичного сложения, двоичного сдвига и двоичного извлечения или маскирования (побитовое АВВ), как показано в табл. 1, составленной Петером Л. Монтгомери (Ресег 1. МопС- босоегу) .
Таблица 1 УДВОЕНИЕ ДЕСЯТИЧНОГО ЧИСЛА, ЗАКОДИРОВАННОГО В ДВОИЧНОЙ СИСТЕМЕ Пример Общий Вид 001101101001 = 369 и1! и!Ви9иВ и! ивиз и4 азиза! ие 0110 1001 1100 ВП ВШ Вв Вв Вз ВВ ВВ ВВ ВЗ Вз В1 ВВ 0000 1000 1000 вм000в!000вз000 0000 О ПО 0110 0 в!1 впО 0 в! в! 0 0 вз вз 0 0011 1100 1111 Ю11Ю19ЮВЮВ Вв74вви!64вв ВВВШВВВ!вва При помощи этого метода значение каждого разряда д заменяется на 2д при 0 < 4( < 4 и на б + 2д = (2д — 10) + 24 при 5 < Ы < 9 что и требуется для удвоения десятичнь!х чисел, каждый разряд которых закодирован четырьмя битами. Другая идея состоит в том, чтобы хранить таблицу степеней двоек в десятичном формате и складывать соответствующие степени, имитируя операции десятичного сложения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
