Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 97
Текст из файла (страница 97)
располо>кеннай справа. позтому можно уб>рать все автоматы, компонента "о которых всегда нулевая для любых и-битовых чисел.) ь 12. (М4!) (А. Шднхаге(А. Яс)>оп)>абе),) Назначение данногоупражнения — доказать. что простая форма машины с указателем (разделяющей точкой) может выполнить умножение и-битовых чисел за 0(п) шагов. В машине отсутствуют встроенные возможности реализации арифметики; все, что она делает, — работает с указателями в узлами, Каждый узел имеет одно и то же конечное число полей связи, и имеется конечное множество связующих регистров. Операции, которые зта машина может выполнять, перечислены ниже; >) считывание олного входного бита; если зтот бит равен О, то выполнение перехода: й) вывод О или 1; 'ш) загрузка в регистр содержимого другого регистра или содержимого поля связи узла, на который указывает регистр; ьт) сохранение содержимого регистра в полях связи узла, на которъой указывает регистр; т) переход в случае равенства двух регистров, >4) создание нового узла и формирование в регистре указателя на него; тй) остановка процесса.
Эффективно реализуйте метод преобразования Фурье на такой машине. (Указание. Пока- жите сначала, что для любого положительного Х можно создать АГ узлов, представляющих целые числа (О, 1,..., А>-1), причем узлы, которые представлвют числа р, имеют указатели на узлы, представляющие числа р+ 1, (р/2) и 2р. Такие узла> могут быть созданы за О(>>>) шагов. Покажите, что в атом глучае арифметика по основанию Х моделируется легко. Например, чтобы найти узел для (р+4) п>об Х и определить, являются ли р+ 4 > Х указателями на р и о, такой арифметике потребуется 0()об Х) шагов. Кроме того, операция умножения может быть смоделкрована за О(1об Х)з шагов. Рассмотрим теперь алгоритм.
приведенный в тексте раздела, при й = 1, т = бй и Х = 2>м>'з>, так что все величины для арифметики в формате с фиксированной точкой представляются 13-разрядными целы- ми числами по основанию Х, Таким образом, покажите, что каждый проход быстрого преобразования Фурье может быть реализован за 0(К + (А>1об А") ) = 0(К) шагов с использованием следующей идеи.
Кан>дая из К требуемых операций присвоения может быть "скомпнлирована" для имитируемого компьютера наподобие 612 в виде ограничен- ного списка команд. Прн атом размер слова машины равен >>>, а команды для К машин, выполняющих операции параллельно, можно промоделировать за 0(К+(АГ )об.>>') ) шагов при условии, что команды рассортированы таким образом, что все идентичные команды выполняются вместе. (Две команды идентичны, если у нпх одинаковый код, цпикаковое содержимое регистров и операцлы расположены в одинаковых ячейках памяти.) Обратите внимание на то, что А>з = 0(п>з~>з), а потому (А"!об Х)т = 0(К).] 13.
(Мйб] (А. Шбнхаге.) Основываясь иа результатах зтого раздела для гл = и, получите хорошую верхнюю оценку для времени, необходимого, чтобы умножить я>-битовое число на и-битовое числа в случае, если оба числа очень большие, но число и значительно больше числа ш, 14. (М42) Напишите программу реализации алгоритма Т с учетом сделанных в упр.
4 усовершенствований. Сравните ее с программой, разработанной для алгоритма 4.3.1!>4, и с программой, основанной на использовании (2), чтобы увидеть, насколько большим должно быть число и, чтобы проявилось усовершенствование алгоритма Т. 1б. ]МЗУ] (Ш. А.
Кук (Б. А. СооЦ.) Алгоритм умножения называется алгоритмом реааьното времени, если ввод (А+ Ц-го бита операнда выполняется юльке после вычисления Й-го выходного бита. Какие самые быстрые алгоритмы умножении в реальном времени можно реализовать на различных автоматах? ° 16. ]ЗЗ] Докажите, что для дискретного преобразования Фурье цо (Зо) требуется всего О(К)оЗК) арифметических операций, даже если К ие равно степени 2. ]Указание. Перепишите выражение (ЗЬ) в виде ,зд ~~ <,.~-Пзут ~з!з о<с<к и выразите этот результат в виде свертки.) 17, (МЯ6] Схема умножения (2) Карацубы при получении и-разрядного произведения выполняет К„1-разрядных операций умножения, где Аг = 1, Кэ, = ЗКп и Кзп+~ = 2К +~ + К«при и > 1.
"Решите" зто рекуррентное уравнение путем поиска точной формулы для К„„когда п 2'~ + 2'з+" + 2', е~ > ез > " > е~ > О. ° 18. ]МЯО] Разработайте схему выделения памяти для промежуточных результатов при выполнении операций умножения по рекурсивному алгоритму, основанному яа уравнении (2). Зеданм два М-разрядных целых числа в и о, каждое из которых занимает М разрядов памяти. Покажите, как ограничить вычисления, чтобы произведение вв оказалось в последних значащих 2Х разрядах (ЗМ + О(!об Х))-разрядной области рабочего пространства.
ь 19. [МЗЗ] Покажите, как вычислить ию шоб гл при ограниченном количестве операций, оговоренных в правилах упр. З.2.1.1-11, если имеется возможность проверить, будет ли олин операнд меньше другого. Оба чиста и и и переменные, но пт постоянно.
Указание. Рассмотрите вопрос декомпозиции в (2). 4.4. ПРЕОБРАЗОВАНИЕ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ Если пы паши прядки, изобретая арифметику, вели счет при помощи двух рук или восьми пальцев, а не десяти "цифр", у нас никогда бы не было хлопот с разработкой програмль двоично-десятичного преобразования чисел, (И, возможно, мы бы никогда столько не узнали о системах счисления.) В этом разделе будут рассмотрены вопросы, связанные с преобразованием чисел из позиционной системы счисления по одному основанию в позиционную систему счисления по другому основанию. Конечно, этот процесс наиболее важен для двоичных компьютеров при преобразовании входных данных, представленных в десятичном формате, в двоичный формат и преобразовании результатов из двоичного формата обратно в десятичный. А.
Четыре основных метода. Преобразование чисел из двоичной системы счисления в десятичную и обратно — одна из наиболее машинно-зависимых операций, поскольку разработчикам компьютеров приходится постоянно изобретать различные способы аппаратной реализации этой операции. Б связи с этим далее будут рассматриваться только основные принципы решения данной задачи, на основании которых программисты могут выбирать процедуры, наиболее подходящие для реализации на компьютере конкретной конфигурации. Будем предполагать, что операции преобразований выполняются только с неотрицательными числами, так как манипулирование знакамн легко учесть. Предположим, что выполняется преобразование из системы счисления по основанию Ь в систему счисления по основанию В.
(Обобщение для систем счисления со смешанным основанием рассматривается в упр. 1 и 2.) Большинство процедур преобразования нз одного основания в другое основано на операциях умножения и деления, использующих один из четырех методов, которые описываются ниже. Два первых метода применяются для преобразования целых чисел (разделяющая точка расположена справа), а два других — для дробных частей чисел (разделяющая точка расположена слева).
Чаще всего нельзя точно выразить конечную дробную часть по основанию Ь (О.и ьи з...и )ь в виде конечной дробной части по основанию В (ОХ' ь(1 з...б' м)я, Например, десятичная дробь ~р в двоичном формателредставляется бесконечной дробью (0.0001100110011... )э. Б связи с этим приходится иногда округлять результат до М разрядов. Метод 1, а (Деление на В с использованием представления чисел в формате по основанию 6). Для заданного целого числа и можно получить представление в формате по основанию В вида (... озПьЦ>)в, выполняя бо = и пкк1 В, (1ь = (и~В) пюд В, Пэ = Ц и~В) ~В) пю4 В, до тех пор, пока не окажется (... ((и/В) /В) ...
/В) = О. Метод 1, Ь (Умножение на В с использованием представления чисел в формате по основанию 6). Если представление числа и по основанию Ь имеет вид (им - °, иьио)ь, то можно, воспользовавшись арифметическими операциями с числами, которые представлены в форльате по основанию В, получить полипом имЬ + +иьЬ+ио = и в виде ((... (им Ь+ и ь) Ь+ . ) Ь+ иь) Ь+ ио. Метод 2, а (Умножение на Ь с использованием представления чисел в формате по основанию В). Для данного дробного числа и можно вычислить значения разрядов (.11 г 11 э... )я его представления по основанию В следующим образом: Г г = '1иВ). 11 э = ((иВ)В).
(/ э = Ц(иВ)В)В), где (х) означает хшо«(1 = х — (х). Чтобы округлить результат до И1 разрядов, вычисления можно прервать после получения 1«' м, причем если (... ((иВ)В)... В) больше 1, то значение 11 м спедует увеличить на единицу. (Заметим, однако, что эта операция может привести к необходимости выполнения переносов, которые должны быть при помощи арифметических операций по основанию В включены в результат. Было бы проще перед началом вычислений прибавить к исходному числу и константу -'В зг, но это может привести к неправильному результату, если в компьютере число -'В м не может быть точна представлено в формате по основанию Ь, Заметим также, чта возможно округление результата до (1.00...0)в„ если 6™ > 2Взг.) В упр.
3 рассматривается обобщение этого метода на случай перез«енного 61, достаточно большого для представления исходного числа с заданной точностью. В такой ситуации проблема перекосов не возникает. Метод 2, Ь (Деление на Ь с использованием представления чисел в формате па аснованяюВ), Если числои представлено пооснаваниюЬввиде(0.и ги э...и „)м то можно, используя арифметические операции по основанию В, вычислить и «Ь '+ и зЬ з+ +и,„Ь '"ввиде ((...
(и „,/Ь+ иг )/Ь+ ° + и»)/Ь+ и г)/Ь. Необходимо внимательно следить за погрешностями, возннкаюгцимн при усеченнях илп округлениях во время выполнения операции деления на Ь; они, как правило, незначительны, но это бывает не всегда. Подведем итоги. Методы 1, а; 1, Ь: 2, а и 2, Ь предоставляют по два возможных способа преобразования целых и дробных чисел. И, конечно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
