Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 96
Текст из файла (страница 96)
Если для некоторой монотонно неубывающей функции Х(п) выражение для Т(я) имеет вид пХ(п), то (56) Т(4п) + Т(2п) + Т(я) + < Т(йп)з так что деление может быть выполнено со скоростью, сравнимой со скоростью умножения, с точностью до постоянного множителя. Р. П. Брент (В, Р. Вгепт) в работе,ИСЛХ 23 (1976), 242-251, показал, что если для умножения и-битовых чисел затрачивается М(п) единиц времени, то для функций вида!ойх, ехря и агсФапх значения с и значащими битами можно вычислить за Р(М(п) 1ойп) шагов. Е. Умножение в реальном времени. Вполне естественно возникает вопрос, можно ли в действительности выполнить умножение и-битовых чисел точно за и шагов, Мы уже сократили время выполнения с пг до порядка и шагов, но, может быть, его удастся сократить еще больше — до абсолютного минимумау Если мысленно покинуть бренный мир и вообразить себя в мире компьютеров с неограниченным числом компонентов, действующих одновременно, то возможен положительный ответ на этот вопрос.
ггинейнол итерационная конфигуроцнл автоматов — это ряд устройств ЛХь Мз, Мэ,..., каждое нз которых может на каждом шаге находиться в некотором конечном множестве состояний. Все машины Мг, ЛХз, ... имеют одннакоеме схемы, и их состояние в момент г + 1 является функцией их собственного состояния в момент $, а также состояний в момент г их соседок справа и слева. Первая машина ЛХ1 несколько отличается от остальных. Ее состояние в момент г + 1 есть функция ее собственного состояния и состояния в момент г машины ЛХг, а также состояния на входе в момент б Выход линейной итерационной конфигурации — это некоторая функция состояний машины Мм Пусть и = (и„1...и1ие)г, о = (оп-1 ..шве)з и д = (4,-1 41до)г — двоичные числа и пусть пи+ 4 = го = (гез„1 ... ш1ше)з.
Примечательно, что линейная итерационная конфигурация может быть построена независимо от и, и, если в моменты 012,... ввести (невеое), (им ем 41), (иг, езог), ..., то в моменты 123,... на ее выходе будет шэ, глм шг,.... Это свойство можно сформулировать в терминах языка конструирования компьютеров, сказав, что можно сконструировать один модуль интегральной схемы, обладающий следующим свойством: если последовательно так смонтировать достаточно много подобных чипов, чтобы каждый из них соединялся только со своим соседом слева и справа, то результирующая схема выдаст 2п-битовое произведение и-битовых чисел точно через 2п тактовых импульсов. В основе этой конструкции лежит следующая идея. В момент 0 машина ЛХг обрабатывает (ие, ее, 4э), поэтому в момент 1 она способна выдать результат (несо + йа) шод 2.
Затем она обрабатывает (им е„д1) и в момент 2 может выдать результат (иее1 + и1ге + 41 + й1) шод 2, где )г1 — "перенос" влево, выполненный на предыдущем шаге. После этого машина обрабатывает (иг, вг, дг) н выдает результат (нэгэ+ и1о1 + пэпе+ юг + Йг) пюд 2. Кроме того, ее состояние регистрирует значения иг и гз с тем, чтобы машина Мг смогла обрабатывать эти величины в момент 3 и чтобы Мг в момент 4 могла вычислить значение игег для ЛХм Машина М1 дает х! у! хо уо х! у! О 1 0 1 1 О 3 1 1 З 1 З о з 3 0 о з о 1 6 О 0 3 1 о 1 7 О 3 0 1 8 0 3 0 0 о з 0 1 10 0 З О о з 0 1 Таблица 2 УМНОЖЕНИЕ В ЛИНЕЙНОЙ ИТЕРАЦИОННОЙ КОНФИГУРАЦИИ Время Вход Модуль М! Модуль Ме Модуль Мл команду машине Мз начать умножение последовательности (из, оз), (нз, оз), а ЛХз в конечном итоге дает команду машине Мз выполнить умнОжение (и4,и4), (нз, оз) и т.
д. К счастью, этот процесс выполняется без потери времени. Дальнейшие подробности читатель может почерпнуть из приводимого ниже формального описания. Любой автомат может принимать 2" состояний (с, хо Ро, хм Рм х, Р, гз, гм го), где 0 < с < 4 и каждое из х, Р н г равно либо О, либо 1. Первоначально все устройства находятся в состоянии (О, О, О, О, О, О, О, О, О, 0) . Предположим, что при з > 1 в момент З машина М находится в состоянии (с, хо, Ро,хмрм х, Р, гг, хм го)., ее соседка слева М„4 находится в состоянии (с-', хо, Ро, х„РЫ х', Р, гз, гм го), а соседка справа АХХез — в состоянии (с",хог,р~,х,",Р~г,х",Р',гзг,г~г,г~).
Тогда машина М4 перейдет в момент с+ 1 в состоанне (с',хо,ро,х'„Рз,х',Р',гз,гз,го), где с' = ппп(с+ 1, 3), если с' = 3, иначе 0; (хо, Ро) = (х', Р'), если с = О, иначе (хо, Ро); (57) (хыР,') = (х',Р'), если с= 1, иначе (хмрз); (х',Р') = (х', Р'), если с > 2, иначе (х, Р),. (го г4 го) з — двоичная запись для ЛР4 хоР +х4Ро хоР +хзрз+х Ро хоР +х Р+хрз+хРо при с=О; при с= 1; при с= 2; при с = 3.
л~+г4+гз+ (56) Крайняя слева машина М4 ведет себя почти так же, как и все остальные. Она функционирует так, как если бы в момент поступления (н, о, д) на ее вход слева от нее находилась машина в состоянии (3, О, О, О, О, и, о, д, О, 0). Выход всей конфигурации— компонента го машины Мм Пример такой конфигурации, работающей с вводом и =и = (...0001011Цз, 4Х= (...00001011)з, приведен в табл.
2. Выходная последовательность дается в нижней части состояний машины Мз. О, О, 1, 1, 1, О, О, О, О, 1, О, ..., что представляет собой число (... 01000011100)з, прочитанное справа налево. В основу описанной конструкции положена похшкая конструкция, предложенная А, Дж. Атрубиным (А, 1. Азги)з)п) и описанная в ХЕЕЕ 2?апз. ЕС-14 (1965), 394-399, Скорее всего, итеративная конфигурация оптимальна только в том случае, когда входные биты появляются последовательно. Если же они появляются одновременно, то следует предпочесть параллельные схемы реализации, которые вычисляют произведение двух и-битовых чисел после 0(1о6 и) задержек. Эффективные схемы такого рода описаны, например, К, С. Уазлесом (С.
8. 9ра))асе) в ХЕЕЕ 2?апз. ЕС-13 (1964), 14-17, и Д. Э. Кнутом (П. Е. Кппг)з) в Тйе 9зллХог4Х Сг рИВазе (4зезз Уог)п АСМ Ргезз, 1994), 270-279, Ш. Виноград (8. %шойга4)) [,ХАСМ 14 (1967), 793-802] исследовал минимальное время умножения, достижилюе в логической цепи, когда и задано и когда входные данные поступают одновременно в произвольно закодированном виде. Аналогичные вопросы для случая, когда операции умножения и сложения должны поддерживаться одновременно, исследованы в работах А. С. Уао, БТОС 13 (1981), 308-311; ь1апзоцг, И(зап апг) Трлап', БТОС 22 (1990), 235-243.
Умноженье — мое раздраженье, И леленье — совсем не песня: Золотое правило вызывает смятенье, Ну а практика просто бесит! — ИЗ РУКОПИСНОЙ КОЛЛЕКЦИИ АРК. О. ХЭЛЛИУЭЛЛА (Д О. НАШИтЕьь) 1С. 15701 УПРАЖНЕНИЯ 1. [ЗЗ] Идея, выраженная в нерэвенстве (2), прн замене основания 2 основанием 10 может быть обобщена для десятичной системы. Используя зто обобщение, вычислите произведение чисел 1234 и 2341 (сведите это произведение четырехзначных чисел х трем п1ювэведенням двузначных чисел, а каждое нэ последних — к произведениям однозначных чисел).
2, ]МЗЗ) Докажите, что если на шаге Т1 алгоритма Т присвоить В +- 1У"ь)], то значение В останется неизменным или увеличится на единицу. (Поэтому, как было отмечено при описании данного шага, нет необхоллмоств вычислять квадратный корень.) 3. ]МЗЗ] Докажите, что последовательности о» н г», определенные в алгоритме Т, удовлетворяют неравенству Зг»+'(2т»)"» < 2»»-1+»ь при (г > О. 4. ]ЗЗ] (К.
Бейкер (К. Ва)гег),) Покажите, что попиком И'(я) лучше вычислять в точках я = -г, ..., О, ..., т, чем в неотрицательных точках я = О, 1, ..., 2г, как это делается в алгоритме Т. Полипом С(я) можно записать в виде П(х) = П.(я') + явь(х'). Полиномы Ъ'(х) и И'(л) могут быть выражены аналогично. Покажите, как испольэовать эту идею лля повышения скорости вычислений на шагах Т7 и ТЗ. б. ]Зб] Покажите, что если на шаге Т1 алгоритма Т вместо В»- (угу присвоить В» — (У'2ь)] +! при соответствующих начальных значениях величин еь, Ф, ге и гн то оценку (20) можно улучшить до Г» < е»,.»2~ге»»' (162»+1). б, ]МЗЗ] Докажите, что шесть чисел в уравнении (24) попарно просты.
]МЗЗ] Докажите (23). 6. ]МЗО) Истинно ли следующее утверждение: можно игнорировать бит, обратный (а» п...,ва) -+ (аь,...,а» 1) в (39), так как обратное преобразование Фурье в любом случае снова обратит биты. О. ]М13] Предположим, что в методе преобразования Фурье, изложенном в разделе, во всех случаях параметр ы заменяется на ыг, где о — некоторое Фиксированное целое число. Найдите простую сэнзь между числами (бе,йп...,вк 1), вычисленными при помощи обобщенного преобразования Фурье, н числами (Оь, йн..., Ол 1), полученными прн о = 1.
10. ]МЗО] В процессе вычислений по алгоритму умножения Шенхаге-Штрассена значений О, н Ю, после масштабирования в (43) становится ясно, что все комплексные числа А91, вычисленные прн выполнении прохода 2 подпрограммы преобразования, будут по абсолютной величине меныпе 21». Покажите, что при выполнении тпретпьгго преобразования Фурье (вычислении»г,) все значения А01 будут по абсолютной величине меньше 1. ° 11. (М26) Сколько должно быть автоматов в линейной итерационной конфигурации, определяемой (57) и (58) при фиксированном значении и, чтобы можно было вычислить произведение и-битовых чисел? (Заметим, что на автомат >М> влияет только компонента ге машины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
