AOP_Tom2 (1021737), страница 96
Текст из файла (страница 96)
В, Чудновский, Г. В. Чудновский, М. М. Денно (М. М. Пеппеан) и С. Г. Юнис (Я. О. Уонп1э) сконструировали необычный компьютер общего назначения, названный Маленьким Ферма (ЫШе Регшас), который мог быстро умножать большие числа. Компьютер оснащен аппаратными средствами быстрого выполнения арифметических операций по модулю 2тве + 1 над 257-битовыми словами. Тогда свертка массивов, состоящих из 256 слов, может выполняться с помощью 256 умножений однословных чисел вместе с тремя дискретными преобразованиями, требующими только операций сложения, вычитания и сдвига. Это позволило. основываясь на конвейерном принципе организации цикла длительностью примерно 60 нс, перемножить два 10е-битовых целых числа меньше чем за 0.1 с (Ргос.
ТЬ|гд 1пп Сопб оп Яирегсотрнйпй 2 (1988), 498-499; Соо1етрогагу МагЬ. 143 (1993), 136]. 1з. Деление. Теперь при наличии эффективных программ для умножения рассмотрим обратную проблему. Оказывается, что деление может быть выполнено так же быстро, как и умножение, с точностью до постоянного множителя. Чтобы разделить и-битовое число и на и-битовое число о, можно сначала найти и-битовое приближение к числу 1/о, затем умножить его на и, что даст приближение д к и/о, и наконец выполнить еще одно умножение для внесения небольшой коррекции в д, чтобы убедиться, что выполняется неравенство 0 < и — уо < о.
Исходя из сказанного, достаточно иметь эффективный алгоритм, который формировал бы по заданному п-битовому числу приближенное значение числа, обратного и-битовому числу. Это может быть реализовано следующим алгоритмом, который использует "метод Ньютона", рассмотренный в разделе 4.3.1. Алгоритм К (Получение обратной величини с высокой точностью). Пусть число о имеет двоичное представление о = (О,о1озоз...)м где о1 = 1. Этот алгоритм вычисляет приближение е числа 1/о, такое, что (е — 1/о( < 2 ". (54) В1.
(Начальное приближение ) Присвоить 2 +- -'(32/(4е1 + 2ег + ег)) и й +- О. В2. (Итерация по Ньютону.) (Здесь имеем число 2 в двоичном виде (хх.хх...х)2 с 2" + 1 знаками после разделяющей точки и г < 2.) При помощи программы быстрого умножения точно вычислить 22 = (ххх.хх...х)2. После этого ТОЧНО ВЫЧИСЛИтъ 7~22, ГдЕ 1!», = (ОШ,Е2...Егь ь+г)г. ЗатЕМ ПрИСВОИтЬ 2»- г -2ьэ! — 1 22 — Ъ!» 2 + г, где г, удовлетворяющее неравенству О < г < 2, прибавлягьь! ется при необходимости для округления 2, чтобы г было кратным 2 2 '.
И наконец присвоить к »- Й + 1. ВЗ. (Завершено".) Еа»и 2» < п, то вернуться к шагу В2; в противном случае выполнение алгоритма заканчивается. ! Этот алгоритм основывается на алгоритме, предложенном С. А. Куком (Я. А. Соо)»). Похожий алгоритм использовался при разработке арифметического блока компьютера (см. Ап»1егаоп, Еаг1е! Со1бэсЬш1»1», Роьеегэ, 1ВМ Х Веэ. Век 11 (1967), 48 — 52]. Конечно, нужно тщательно проверять точность алгоритма В., так как он находится на грани того, чтобы быть некорректным. По индукции докажем, что в начале и в конце шага В2 выполняются неравенства 2<2 и (2 — 1/е(<2 (55) Обозначим через 2» значение 2, вычисленное после й итераций на шаге В2, и пусть 6» = 1/е — гю При к = О имеем бо = 1/е — 8/е' + (32/е' — (32/е') ) /4 = П» + Пг, где е' = (е1 егег)г и 111 — — (е' — 8е)/ее'.
При этом параметры 91 н пг удовлетворяют неравенствам —.1 < ц» < О и О < 112 < — '. Значит, (6о( < 1. Теперь предположим, что второе неравенство в (55) удовлетворяется при 1». Тогда д»е» — — 1/е — г»+1 = 1/е — 2» — 2»(1 — г» 1») — г 2 = Б» — 2»(1 — х»е) — 2»(е — 1») — г = 5» — (1/е — 6») еБ» — 2»(е — Р») — г = еБ» — 21,(е — е») — г, гьь! Отсюда следует, что О < е5» < 5» < (2 г )1 = 2 г и 0<22(е — $~)+с<4(2 2 г)+2 2 '=2 г ' ! так что (5»+1( < 2 . Осталось еще проверить первое неравенство в (55).
Чтобы убедиться в том, что 2» 1 < 2, рассмотрим три случая: а) Ъ~, = „-, тогДа гь»1 = 2; 1, 11) 1'» 1Š— = 1'»-1, 'тогда х» = 2, поэтому 22» — г Ъ~ < 2 — 2 г — 2ьч -1. 1. ,ь.',! с) ~'а — 1 ~ —; тогда х»ь» = 1/е — 5».11 < 2 — 2 < 2, так как й > О. Время, затрачиваемое на выполнение алгоритма В, ограничено сверху количеством циклов, равным 2Т(4п) + 2Т(2п) + 2Т(п) + 2Т(2 и) +... Ч- 0(п), где Т(п) — -верхняя оценка времени, необходимого для выполнения операции умножения и-битовых чисел, Если для некоторой монотонно неубывающей функции г (и) выражение для Т(п) имеет вид п,((п), то (56) Т(4п) + Т(2п) + Т(п) + ( Т(8п), так что деление может быть выполнено со скоростью, сравнимой со скоростью умножения, с точностью до постоянного множителя. Р.
П. Брент (В. Р. ВгепФ) в работе дАСМ 23 (1976), 242-251, показал, что если для умножения и-битовых чисел затрачивается М(п) единиц времени, то для функций вида!охх, ехрх и агссапх значения с и значащими битами можно вычислить за О(М(п) !оба) шагов. Е. Ъ'множение в реальном времени. Вполне естественно возникает вопрос, можно ли в действительности выполнить умножение и-битовых чисел точно за и шагов. Мы уже сократили время выполнения с пг до порядка и шагов, но, может быть, его удастся сократить еще больше — до абсалютнага минимума? Если мысленно покинуть бренный мир и вообразить себя в мире компьютеров с неограниченным числом компонентов, действующих одновременно, то возможен положительный ответ на этот вопрос.
г7инепноя итерационная конфигурация автоматав — это ряд устройств Мь ЛХг. Мг...., каждое из которых может на каждом шаге находиться в некотором конечном множестве состояний. Все машины ЛХг, Мг, ... имеют одинаковые схемы, и их состояние в момент г + 1 является функцией их собственного состояния в момент 1, а также состояний в момент ! их госедок справа и слева. Первая машина И, несколько отличается ат остальных.
Ее состояние в момент ! + 1 есть функция ее собствениога состояния и состояния в момент ! машины Мг, а также состояния но входе в момент б Выход линейной итерационной конфигурации — это некоторая функция состояний машины ЛХм ПУсть и = (и„г... и1ио)г, о = (ио 1... игоо)г и 4 = (лл-г .. Дгдо)г — двоичные числа и пусть ио + д = ю = (юго ~ ... ю1юо)г. Примечательно, что линейная итерационная конфигурация может быть построена независимо от и, и, если в моменты О, 1,2,...
ввести (ио, оо,оо), (им оп лг), (иг, ог, ог), ..., то в моменты 1, 2,3,... на ее выходе будет и~о, ип, юг, .... Это свойство можно сформулировать в терминах языка конструирования компьютеров, сказав, чта можно сконструировать один модуль интегральной схемы, обладающий следующим свойством: если последовательно так смонтировать достаточно много подобных чипов, чтобы каждый из них соединялся только са своим соседом слева и справа, то результирующая схема выдаст 2п-битавае произведение и;битовых чисел точно через 2п тактовых импульсов. В основе этой конструкции лежит следующая идея. В момент О машина М1 обрабатывает (ио, оо, Чо), поэтому в момент 1 ана способна выдать резулыат (иоио+ до) шод2.
Затем она обрабатывает (имом дг) и в момент 2 может выдать Результат (моиг + иг го + дг + Йг) шой 2, где Йг -- "перенос" влево, выполненный на предыдупгем шаге. После этого машина обрабатывает (иг, иг, дг) и выдает результат (иоог+игиг+игио+дг+Лг) шод 2. Кроме того, ее состояние регистрирует значения иг и ог с тем, чтобы машина Иг смогла обрабатывать эти величины в момент 3 и чтобы Мг в момент 4 могла вычислить значение игиг для Мь Машина Мг дает Таблицэ 2 УМНОЖЕНИЕ В ЛИНЕЙНОЙ ИТЕРАЦИОННОЙ КОНФИГУРАЦИИ Время Вход Модуль Мг Модуль ЛХг Модуль Мз Яг хо хг ог с уо уг хо хг с уо уг хо х~ с уо уг 0 0 0 0 0 О 0 О 1 1 0 0 0 0 0 0 0 0 2 0 2 1 1 0 0 0 0 0 0 0 0 3 1 3 0 1 0 0 0 0 0 0 0 0 4 0 3 1 1 1 0 1 О 0 0 0 0 5 0 3 О 1 0 0 0 0 0 0 0 0 О О 0 3 1 О 1 1 0 1 0 7 0 3 0 1 1 0 1 0 1 О 1 0 1 0 1 0 О 0 3 1 О 1 1 0 1 О 1 О 1 0 0 3 0 1 1 0 1 0 1 0 1 0 0 1 а 3 1 0 1 О 10 1 0 1 0 0 3 0 1 1 0 1 0 О 1 1 О 0 1 0 г хг гр 1 О 1 0 гг гг го хг гг гр команду машине Мг начать умножение последовательности (иг,вг), (иг, ог), ..., а Мг в конечном итоге дает команду машине Мг выполнить умножение (иэ,оэ), (ио, оо) и т.
д. К счастью, этот процесс выполняется без потери времени. Дальнейшие подробности читатель может почерпнуть из приводимого ниже формального описания. Любой автомат может принимать 2" состояний (с, хо, уо, хм уг, х, у, гг, гм го) где 0 с с с 4 и каждое из х, у и г равно либо О, либо 1. Первоначально все устройства находятся в состоянии (0,0,0,0,0,0,0,0,0,0). Предположим, что при г' > 1 в момент г машина М, находится в состоянии (с, хо, уо, хг, уг, х, у, гг, гг, го); ее соседка слева М, находится в состоянии (с", хо, уо~, х'„у(, х', у', гг~, г~„гог), а соседка справа М, е г — в состоянии (с", хо, уо, х', у,", х", у", гг, г,', го ). Тогда машина Мг перейдет в момент 1+ 1 в состоЯние (с',хо,Уо,х',,У'„х',У',гг,г'„го), гДе с' = ппп(с+ 1, 3), если с' = 3, иначе 0; (хор, Уо) = (х',У'), если с = О, иначе (хо, Уо); (57) (х'„у',) = (х',у'), если с = 1, иначе (хмуг); (х',у') = (х',у'), если с > 2, иначе (х,у); (ггг(го)г — двоичная запись для хгу' хоу +х'уо тоу + хгуг + х'уо хоу'+хгу+ху, +х'уо при с=О; при с= 1; при с= 2; при с= 3.
го + гг + гг + т (58) Крайняя слева машина Мг ведет себя почти так же, как и все остальные. Она функционирует так, как если бы в момент поступления (и, о, у) на ее вход слева от нее находилась машина в состоянии (3, О, О, О, О, и, и, д, О, 0). Выход всей конфигурации— компонента го машины Мг. Пример такой конфигурации, работающей с вводом и = о = (...00010111)г, ч = (...00001011)г, приведен в табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
