AOP_Tom2 (1021737), страница 95
Текст из файла (страница 95)
Положим ог,. = ехр(2хг/2") (45) таким, что сог — — — 1, ыг = г', ыз = (1+ г)/г/2г ..., ыь = ог. Если ог, = х„+ 49„, то ИМЕЕМ и,+г — — Х„41 + грг41, ГДЕ 1+ х„ Х,Ч.1 = гг/ 2 рг 'яь +г— 22ххг4г (46) ]См. 3. В.. Тасе, 1ЕЕЕ Тгалбасйопб БР-43 (1995), 1709 — 1711.] На вычисление ыг, го2,..., иь затрачивается по сравнению с остальнылси операциями относительно немного времени, так что вполне можно использовать любой стандартный способ извлечения квадратных корней. После ог„можно легко вычислить все степени ыг, учитывая, что ы' = ы,'г ' ...го'„',го'„г, если у = (21-1 .2120)2 (47) Поскольку каждое значение огг получается как результат умножения и„не более чем й раз, оспибки вычислений при таком методе не накапливаются.
Общее время вычисления всех значений ог! равно 0(КМ), где М вЂ” время выполнения операций умножения пг-битовых комплексных чисел, поскольку на вычисление каждого из следующих значений ьг! по известному предыдущему требуется одна операция умножения. На выполнение последующих операций необходимо больше циклов, чем 0(КМ), поэтому на вычисление степеней го требуется сравнительно мало времени. 276г 19 24-4г+ 13м -2-г 13г 2 — 4г — 13Ф -7 2 .С- 4г — 1згг -2 — 13г 2 — 4г + 1зв 2ггй 304 — 26 + 64г -'г 69м — 125Ф вЂ” 18 — 5бг -26 — 64г + 125ы — 69Ф -84 -26 4- 64г — боы 4- 125Ф вЂ” 18+ ббг -26 — 64г — 125ы + 69Ы 2ггго, = Игг 10 69 64 125 36 0 0 0 Каждое из трех преобразований Фурье состоит из Ь проходов, а каждый из проходов включает К операций вида а +- Ь+ ыэс, так что общее время вычисления преобразований Фурье равно 0(ЬКМ) = 0(Мпй/1).
В итоге для вычисления двоичных разрядов и и согласно (44) требуется 0(К(1+1)) = 0(п + пЬ/1) машинных циклов. Если просуммировать все операции, получим, что обгцее время умножения и-битовых чисел и и г равняется 0(п) + 0(Мпй/1) циклам. Теперь, зная, какой должна быть величина М, посмотрим, какой должна быть точность вычисления промежуточных результатов гп. Для простоты вместо поиска наилучших оценок точности будем рассматривать оценки с запасом, гарантирующие получение при помощи этого алгоритма требуемых результатов. Достаточно вычислить все значения ыз в таком виде, чтобы приближения (ы~)' удовлетворяли неравенству ((из)'( < 1. Это условие легко обеспечить, если значения не округлять, а усекать до нуля, так как в (46) х~+ + д~+, — — (1 + х~ + угэ + 2х„)/(2+ 2к„).
Все операции с пэ-битовыми числами в комплекснозначной арифметике с фиксированной точкой выполняются посредством замены точных вычислений вида а +- Ь+ ызс приближенными: (48) а' < — усечение(Ь' + (из)'с'), где Ь', (ыз)' и с' — приближения, вычисленные предварительно. Все эти комплексные числа и их приближения по абсолютному значению ограничены единицей. Если (Ь' — Ь| < бм ((ыу)' — ы'! < Ьэ и (с'-с! < Бэ, то нетрудно увидеть, что будет выполняться ~а' — а~ < Ь + 4 + Бг + дз, где б=(2 +2 1(=2'~э (49) поскольку имеем )(ыэ)'с' — ы'с~ = (((ыз)' — ыз)с'+ыз(с' — с)) < бэ + бэ, а б превышает максимальную погрешность усечения. Вычисления приближений (ы')' начинаются с приближений ы,' к числам, определенным в уравнениях (46), и можно считать, что вычисления в (46) выполняются с допустимой погрешностью, такой, что выполняется ~и,' — и„( < Б.
Тогда из уравнения (47) следует, что ((ыз)' — ыэ ~ < (2Й вЂ” 1) б при всех у, поскольку ошибка обусловлена не более чем Ь приближениями и не более чем Ь вЂ” 1 усечениями. Если перед началам любого прохода быстрого преобразования Фурье ошибка не превышает е, то операции этого прохода имеют вид (48), где Б~ — — бэ — — с и бэ = (2й — 1) б. Тогда ошибки после выполнения прохода не будут превышать 2е+2Ы Так как на нулевом проходе ошибок нет, по индукции можно показать, что после у-го прохода ошибка будет ограничена (21 — 1) 2И и вычисленные значения й, будут удовлетворять неравенству ((й,)' — 6,) < (2ь — 1) 2йб. Аналогичное неравенство можно получить и для (6,)'; тогда ~(Ф,)' — Ф,~ < 2(2" — 1) 2И+ Б < (412" — 2Ь)б.
В процессе обратного преобразования накапливаются дополнительные ошибки, однако большинство из них подавляется при делении на К = 2э. По этой же причине приходим к выводу, что вычисленные значения величин ю„ будут удовлетворять неравенству ~(п~„)' — ю„~ < 2~(4Ь2" — 2Ь)б+ (2~ — 1)2йд; )ю', — ю„( < 4Ь2~4.
(50) Для округления 2з"" ыш'„до правильного целого числа И', необходимо обеспечить достаточную точность вычислений, поэтому должно выполняться неравенство 2ы+г~~г+~я ь+ь~-~7г — < Х Я ~ (51) т. е. гп ) 31с+ 21+ !8/с+ 7/2. Для этого достаточно потребовать, чтобы выполнялось (52) Й > 7 и т > 4/с+ 21. (53) Т(п) < С п(С !кп)(С 18!8 п)(С !8 18 !пи)..., где произведение продолжается до тех пор, пока множитель 18... 18 и < 2.
Шенхаге и Штрассен в своей работе показали, как улучшить зту теоретическую верхнюю границу до 0(п !об и !об! об и), используя целые числа ы, чтобы распространить быстрое преобразование Фурье на целые числа по модулю 2' + 1. Эта верхняя граница применима к машине Тьюринга, т. е. к компьютерам с ограниченной памятью и конечным числом лент произвольной длины. Соотношения (41) и (52) могут быть использованы для определения таких значений параметров й, ! и гп, чтобы на операцию умножения затрачивалось 0(п) +0(Мпк/1) единиц времени, где М вЂ” время умножения т-битовых дробных частей. Например, для компьютера М1Х предположим, что перемножаются двоичные числа, каждое из которых представлено и = 2~з = 8192 бит.
Можно выбрать значения параметров й = 11, 1 = 8, гп = 60, так что требуемые операции с т-битовыми числами будут ни чем иным, как операциями умножения с числами в арифметике с удвоенной точностью. Поэтому необходимое время выполнения ЛХ операций умножения т-битовых комплексных чисел будет сравнительно малым. Если положить, к примеру, й = ! = 15, то придется иметь дело с операциями утроенной точности, что выходит за пределы возможностей памяти машины й1Х. На компьютере с ббльшими воэможностями можно, положив й = 1 = 27 и гп = 144, перемножить два гигабитовых числа. Дальнейший анализ выбора значений параметров Й, ! и гп приводит к удивительному выводу: для большинства практических случаев можно считать М постоянным, а время выполнения процедуры умножения Шенхаге-Штрассена пропорционально и. Суть в том, что можно выбрать 1с = ! и гп = бй; такой выбор и приводит к тому, что время выполнения всегда меньше 1яп, поэтому потребуется не более чем ушестеренная точность вычислений, даже если п больше размера машинного слова.
(В частности, и может быть больше размера индексного регистра, так что, возможно, числа и и е не поместятся в основной памяти.) Таким образом, практическая сторона быстрого умножения решена, за исключением возможного усовершенствования процедуры выбора констант. Действительно, алгоритм свертки для произвольных целых чисел, приведенный в упр. 4.6.4-59, является лучшим практическим решением проблемы умножения с высокой точностью. Наш интерес к проблеме умножения больших чисел отчасти теоретический, поскольку интересно исследовать предельные ограничения на вычислительную сложность алгоритма.
Итак, оставим на время практическую сторону вопроса и предположим, что число и чрезвычайно. велико, возможно, значительно больше числа атомов во Вселенной. Можно считать т приблизительно равным 61кп и использовать для умножения т-битовых чисел тот же алгоритм рекурсивно.
Время его выполнения будет удовлетворять выражению Т(п) = 0(пТ(!о8 и)) . Следовательно, Для более мощного компьютера со случайной выборкой любого числа слов ограниченного размера Шенхаге обратил внимание на то, что верхняя граница снижается до 0(п!ойп). Теперь можно выбрать параметры 1е = 1 и тп = 61е и появляется время для формирования полной таблицы всевозможных произведений ху при 0 < х,у < 2~ 7ы . (Количество таких произведений равно 2" или 2"'~'. После этого можно вычислить любой элемент таблицы за 0(1е) шагов, добавив к нему одного из предшественников.) Следовательно, 0(к2ь) = 0(п) шагов будет достаточно для вычисления.
В этом случае М вЂ” время, необходимое для выполнения 12-разрядной арифметической операции по основанию 21 7'з1, а отсюда следует, что М = О(/е) = 0(1обп), так как 1-разрядное умножение можно выполнить по таблицам. (Время выборки гдова из памяти считается пропорциональным количеству битов. содержащемуся в адресе слова.) Более того, в 1979 году Шенхаге обнаружил, что машина с указателяии может выполнять умножение и-битовых чисел за 0(п) шагов (см.
упр. 12). Такие устройства (которые называются также машинами с модификацией хранения и связными автоматами) при и — > оо реализуют, как нам кажется, лучшие вычислительные модели, что было описано в разделе 2.6. Таким образом, можно сделать вывод о том, что умножение за 0(п) шагов возможно как на практике, так и теоретически. В 1986 году Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
