AOP_Tom2 (1021737), страница 97
Текст из файла (страница 97)
2. Выходная последовательность дается в нижней части состояний машины Мг. О, О, 1, 1, 1, О, О, О, О, 1, О, ..., что представляет собой число (...01000011100)г, прочитанное справа налево. В основу описанной конструкции положена похожая конструкция, предложенная А. Дж. Атрубиным (А. д. АггвЬ1п) и описанная в 1ЕЕЕ 2?апз. ЕС-14 (1965), 394-399. Скорее всего, итеративная конфигурация оптимальна только в том случае,когда входные биты появляются последовательно. Если же они появляются цдиовременно, то следует предпочесть параллельные схемы реализации, которые вычисляют произведение двух и-битовых чисел после О(1оя и) задержек. Эффективные схемы такого рода описаны, например, К.
С. Уоллесом (С. 9, Ъа)!асе) в 1ЕЕЕ Т?апа ЕС-13 (1964), 14 — 17, и Д. Э. Кнутом (П. Е. КппГЬ) в ТЬе Ягап1огс( СгарЬВвзе (Хегг Уог1с: АСМ Ргевз, 1994), 270-279. Ш. Виноград (Б. Жпойгаб) (1АСМ 14 (1967), 793-602) исследовал минимальное время умножения, достижимое в логической цепи, когда и задано и когда входные данные поступают одновременно в произвольно закодированном виде.
Аналогичные вопросы дпя случая, когда операции умножения и сложения должны поддерживаться одновременно, исследованы в работах А. С. Уао, 8ТОС 13 (1981), 308 — 311; Мапзоцг, К!эап апб Т!шаг!, БТОС 22 (1990), 235-243. Умноженье — мое раздраженье, И депенье — совсем не песня: Золотое правило вызывает смятенье, Ну а практика просто бесит! — ИЗ РУКОПИСНОЙ КОЛЛЕКЦИИ ЯЗК. О. ХЭЛЛИУЭЛЛЯ (Л О. НЯЬ !ЬУЕЩ (с. 1570) УПРАЖНЕНИЯ 1.
(32] Идея, выраженная в неравенстве (2), при замене основания 2 основанием 10 может быть обобщена для десятичной системы. Ишюльзуя это обобщение, вычислите произведение чисел 1234 и 2341 (сведите это произведение четырехзначных чисел к трем произведениям двузначных чисел, а каждое нз последних — к произведениям однозначных чисел). 2.
(М22] Докажите, что если на шаге Т1 алгоритма Т присвоить В ь- (Щ, то значение Л останется неизменным или увеличится на единицу. (Поэтому, как была отмечено при описании даннага шага, нет необходимости вычислять квадратный корень.) 3. ]МВВ] Докажите, что последовательности ал и тл, определенные в алгоритме Т, удовлетворяют неравенству 2'л+'(2гь)"л < 2ю-~+ел при й > О. 4. (ЕВ] (К. Бейкер (К. Ваяет).) Покажите, что полинам И'(х) лучше вычислять в тачках х = — г, ..., О, ..., г, чем в неотрицательных точках х = О, 1, ..., 2г, как эта делается в алгоритме Т. Полинам ()(х) можно записать в виде ((( ) () ( 2) + П ( 2) Полиномы У(х) и И'(х) могут быть выражены аналогично.
Покажите, как использовать эту идею для повышения скорости вычислений на шагах Т7 и Тй. б. ]ВВ] Покажите, что если на шаге Т1 алгоритма Т вместо В <- (л(лг] присвоить В ь- (л/2(Ц + 1 при соответствующих начальных значениях величин ао, Ф, ге и ги то оценку (20) можно улучшить до сл < йь.лл2~эээл+' (!Ойьэп). 6. (МВВ] Докажите, что шесть чисел в уравнении (24) попарно просты. 7. (МВВ] Докажите (25). 8.
(Мйй] Истинно ли следующее утверждение. можно игнорировать бит, обратный (вь-ы, .., ва) -л (вв,,вь-~) в (39), так как обратное преобразование Фурье в любом случае снова обратит биты. 9. ]М15] Предположим, чта в методе преобразования Фурье, изложенном в разделе, ва всех случаях параметр и заменяется на ыэ, где й — некоторое фиксированное целое числа, Найдите простую связь между числами (йе, йп...,йк,), вычисленными при помощи обобщенного преобразования Фурье, и числами (йе, йы, йк- ~ ), полученными при а = 1 10. (МВВ] В процессе вычислений па алгоритму умножения Шенхаге-Штрассена значений й, и й, после масштабирования в (43) становится ясно, что все комплексные числа А!'1, вычисленные при выполнении прохода ) подпрограммы преобразования, будут па абсолютной величине меньше 2л л. Покажите, чта при выполнении тпрсгпьега преобразования Фурье (вычисленин й„) все значения Ап! будут па абсолютной величине меньше 1.
ь 11. (М26) Сколько должно быть автоматов в линейной итерационной конфигурации, определяемой (57) и (58) при фиксированном значении и. чтобы можно было вычислить произведение и-битовых чисел? (Заметим, что на автомат М, влияет только компонента ге машины, расположенной справа, поэтому можно убрать все автоматы, компонента ге коэорых всегда нулевая для любых п-битовых чисел.) ь 12. (М4! ) (А.
Шеихаге (А. ЯспопЬабе).) Назначение данного упражнения — доказать, что простая форма машины с указателем (разделяющей точкой) может выполнить умножение и-битовых чисел за О(п) шагов. В машине отсутствуют встроенные возможности реализации арифметики; все, что она делает, -- работает с указателямн и узлами. Каждый узел имеет одно н то же конечное число полей связи, и имеется конечное множество связующих регистров. Операции, которые эта машина может выполнять, перечислены ниже: !) считывание одного входного бита; если этот бит равен О, то выполнение перехода; й) вывод 0 или 1: Й) загрузка в регистр содержимого другого регистра или содержимого поля связи узла, на который указывает регистр; ьт) сохранение содержимого регистра в полях связи узла, на который указывает регистр; т) переход в случае равенства двух регистров; ьб) создание нового узла и формирование в регистре указателя на него, тп) остановка процесса.
Эффективно реализуйте метод преобразования Фурье на такай машине, [Указание. Покажите сначала, что для любого положительного М можно создать Л' узлов. представляющих целые числа (О, 1,..., Л'-1), причем узлы, которые представляют числа р, имеют указатели на узлы, представляющие числа р+ 1, (р/2) и 2р.
Такие узлы могут быть созданы за 0(Л') шагов. Покажите, что в этом глучае арифметика по основанию Л' моделируется легко. Например, чтобы найти узел для (р+о) шоб Л' и определить, являются ли р+о > Х указателями на р и о, такой арифметике гютребуетгя 0()ой Х) шагов. Кроме того, операция умножения может быть смоделнрована за О(!обЛ) шагав. Рассмотрим теперь алгоритм, приведенный в тексте раздела, при !г = 1, гл = бй и Л' = 2! !'з!, так что все величины для арифметики в формате с фиксированной точкой представляются 13-разрядными целыми числами по основанию Л; Таким образам, покажите, что каждый проход быстрого преобразования Фурье может быть реализован за 0(К + (Х!оба) ) = 0(К) шагов с использбванием следующей идеи. Каждая из К требуемых операций присвоения может быть "скампилирована" для имитируемого компьютера наподобие И11 в виде ограниченного списка команд, При этом размер слова машины равен Л", а команды для К машин, выполняющих операции параллельно, можно промоделировать за 0(К+ (Х !ой Х) ) шагов при условии, что команды рассортированы таким образом, что все идентичные команды выполняются вместе.
(Две командм идентичны, если у них одинаковый код, одинаковое содержимое регистров и операнды расположены в одинаковых ячейках памяти.) Обратите внимание на то, что Х~ ж 0(пш!'э), а потому (Л' !оба) = 0(К).) 13. (Мйб) (А. Шенхаге.) Основываясь на результатах этого раздела для ш = и, получите хорошую верхнюю оценку для времени, необходимого, чтобы умножить т-битовое числа на и-битовое число в случае, если оба числа очень большие, но число и значительно больше числа яз.
14. [М42] Напишите программу реализации алгоритма Т с учетом сделанных в упр. 4 усовершенствований. Сравните ее с программой, разработанной для алгоритма 4.3.151, и с программой. основанной на использовании (2), чтобы увидеть, насколько большим должно быть числа и, чтобы проявилось усовершенствование алгоритма Т. 15. [М4Р) (Ш. А. Кук (Б. А. Соо1с).) Алгоритм умножения называется алгариотмом реольноге времени, если ввод (к+ 1)-го бита операнда выполняется только после вычисления А-го выходного бита.
Какие самые быстрые алгоритмы умножения в реальном времени можно реализовать на различных автоматах? ь 16. (25] Докажите, что для дискретного преобразования Фурье по (35) требуется всего 0(К 1аб К) арифметических операций, даже если К не равно степени 2. (Указание. Перепишите выражение (35) в виде э<ген и выразите этот результат в виде свертки.) 17. (Мйб) Схема умножения (2) Карацубы при получении и-разрядного произведения выполняет К 1-разрядных операций умножения, где К~ — — 1, Кэ = ЗКь и Кэьэ~ = 2К +~ + К» при и > 1. "Решите" это рекуррентное уравнение путем поиска точной формулыдляК, когдап=2ы+2а+ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
