Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 95
Текст из файла (страница 95)
Так как на нулевом проходе ошибок нет, по индукции можно показать, что после з-го прохода ошибка будет ограничена (21 — 1) 2йб и вычисленные значения й, будут удовлетворять неравенству )(й„)' — й,! < (2» — 1) ° 2йб. Аналогичное неравенство можно получить и для (6,)', тогда )(ю,)' — Ф,) < 2(2" — 1) ° 2йб+ б < (412 — 2Й)б. В процессе обратного преобразования накапливаются дополнительные ошибки, однако большинство нз ннх подавляется при делении на К = 2". По втой же причине приходим к выводу, что вычисленные значения величии ю, будут удовлетворять неравенству )(зЬ,)' — зЬ„~ < 2 (4Й2з-2Ь)б+ (2з — 1)2Ьб; )ю„' — зл,) < 4Ь2зб.
(60) Для округления 2ть+шш'„до правильного целого числа И'„необходимо обеспечить достаточную точность вычислений, поэтому должно выполняться неравенство 2зь+и+з+!в ь+ь~.1/т- < Х (51) — й~ т. е. т > Зя+ 21+!к й+ 7/2. Для этого достаточно потребовать, чтобы выполнялось й > 7 и т > 45+21. (52) Соотношения (41) и (52) могут быть использованы для определения таких значений параметров й, 1 н т, чтобы на операцию умножения затрачивалось О(и) + 0(Мэй/1) единиц времени, где М вЂ” время умножения т-битовых дробных частей.
Например, для компьютера й1Х предположим, что перемножаются двоичные числа, каждое из которых представлено и = 2ы = 8192 бит. Можно выбрать значения параметров Й = 11, 1 = 8, т = 60, так что требуемые операции с т-битовыми числами будут ни чем иным, как операциями умножения с числами в арифметике с удвоенной точностью. Поэтому необходимое время выполнения М операций умножения т-битовых комплексных чисел будет сравнительно малым. Если положить, к примеру, !г = 1 = 15, то придется иметь дело с операциями утроенной точности, что выходит за пределы возможностей памяти машины 61Х. На компьютере с ббльшими возможностями можно, положив й = 1 = 27 и гп = 144, перемножить два гигабитовых числа. Дальнейший анализ выбора значений параметров Й, 1 и т приводит к удивительному выводу: для большинства практических случаев можно считать М постоянным, а время выполнения процедуры умножения Шенхаге-Штрассена пропорционально и.
Суть в том, что можно выбрать Й = 1 и т = бй; такой выбор Й приводит к тому, что время выполнения всегда меньше !8п, поэтому потребуется не более чем ушестеренная точность вычислений, даже если и больше размера машинного слова.
(В частности, и может быть больше размера индексного регистра, так что, возможно, числа и и и не поместятся в основной памяти.) Таким образом, практическая сторона быстрого умножения решена, за исключе. нием возможного усовершенствования процедуры выбора констант.
Действительно, алгоритм свертки для произвольных целых чисел, приведенный в упр, 4.6.4-59, является лучшим практическим решением проблемы умножения с высокой точностью, Наш интерес к проблеме умножения больших чисел отчасти теоретический, поскольку интересно исследовать предельные ограничения на вычислительную сложность алгоритма.
Итак, оставим на время практическую сторону вопроса и предположим, что число и чрезвычайно. велико, возможно, значительно больше числа атомов во Вселенной. Можно считать т приблизительно равным 618и и нспользовать для умножения т-битовых чисел тот же алгоритм рекурсивно. Время его выполнения будет удовлетворять выражению Т(и) = 0(иТ(!ой и)). Следовательно, Т(п) < Сп(С!8п)(С!к!8и)(С!818!йп)..., (53) где произведение продолжается до тех пор, пока множитель 1к...!8и < 2. Шенхаге и Штрассен в своей работе показали, как улучшить эту теоретическую верхнюю границу до 0(и !ой и !ок !ой и), используя целые числа ы, чтобы распростра нить быстрое преобразование Фурье на целые числа по модулю 2' + 1.
Эта верхняя граница применима к машине Тьюринга, т. е. к компьютерам с ограниченной памятью и конечным числом лент произвольной длины. Для более мощного компьютера со случайной выборкой любого числа слов ограиичеииого размера Шеихаге обратил виимапие иа то, что верхняя граница сиижается до 0(п !об п). Теперь можно выбрать параметры Й = 1 и ш = бй и появляется время для формирования полкой таблицы всевозможных произведений кр при 0 < к, р < 21'ч~'з) . (Количество таких произведений равно 2ь или 2"+'. После этого можно вычислить любой элемент таблицы за 0(Й) шагов, добавив к иему одного из предшественников.) Следовательно, 0(Л 2") = 0(п) шагов будет достаточно для вычисления. В этом случае М вЂ” время, иеобходимое для выполиеиия 12-разрядной' арифметической операции по основанию 2('"~1з", а отсюда следует, что М = 0(Л) = 0(1ойн), так как 1-разрядиое умножение можио выполиить по таблицам.
(Время выборки слова из памяти считается пропорциональным количеству битов. содержащемуся в адресе слова.) Более того, в 1979 году Шеихаге обнаружил, что машина с рказагпелями может выполиять умножение и-битовых чисел за 0(п) шагов (см. упр. 12). Такие устройства (которые называются также машинами с модификацией храпения и связными автоматами) при и -+ оо реализуют, как иам кажется, лучшие вычислительиые модели, что было описано в разделе 2.6. Таким образом, можно сделать вывод о том, что умножение за 0(п) шагов возможно как иа практике, так и теоретически. В 1986 году Д.
В. Чудновский, Г. В. Чудновский, М. М. Денно (М. М, Реппеаи) и С, Г. Юиис (8. С. Уоип1э) скоиструировали необычный компьютер общего иазиачеиия, названный Маленьким Ферма (ЫЫ1е Регшаг), который мог быстро умножать большие числа. Компьютер оснащен аппаратными средствами быстрого выполнения арифметических операций по модулю 2ые + 1 иад 257-битовыми словами. Тогда свертка массивов, состоящих из 256 слов, может выполняться с помощью 256 умиожеиий одиословиых чисел вместе с тремя дискретными преобразованиями, требующими только операций сложения, вычитания и сдвига.
Это позволило. основываясь иа конвейерном прииципе организации цикла длительностью примерно 60 ис, перемножить два 10в-битовых целых числа меньше чем за 0.1 с [Ргос, ТЛ1гб 1пп Сопб оп Бирегсотригшд 2 (1988), 498-499; Сопсетрогвгу МайЛ. 143 (1993), 136).
Т1. Делецие. Теперь при наличии эффективных программ для умножения рассмотрим обратную проблему. Оказывается, что деление может быть выполнено так же быстро, как и умножение, с точностью до постояпиого множителя. Чтобы разделить и-битовое число и иа п-битовое число е, можно сиачала иайти н-битовое приближение к числу 1/е, затем умножить его иа и, что даст приближеиие д к и/и, и наконец выполнить еще одно умножеиие для виесения небольшой коррекции в б, чтобы убедиться, что выполняется иеравеисгво 0 < и — оо < и. Исходя из сказанного, достаточно иметь эффективный алгоритм, который формировал бы по заданному и-битовому числу приближенное значение числа, обратного и-битовому числу. Это может быть реализовано следующим алгоритмом, который использует "метод Ньютона", рассмотренный в разделе 4.3.1.
Алгоритм й. (Полрчение обратной величиям с высокой пючносгпью). Пусть число и имеет двоичное представление и = (О.е~озиз...)з, где и1 = 1. Этот алгоритм вычисляет приближение х числа 1/и, такое, что )л — 1/е) < 2 ". (54) К1. [Начальное приближение.] Присвоить»»- Ц 32/(4е» + 2гт + ез)) и Ь»- О. К2. [Итерация по Ньютону,) (Здесь имеем число г в двоичном виде (хх.хх...х)» с 2» + 1 знаками после разделяющей точки и» < 2.) Прн помощи программы быстрого умножения точно вычислить зз = (ххх,хх...х)з. После этого точно вычислить 1»зз, где 1» = (О.в»вз...в»а~.
„.з)». Затем присвоить з»- 2» — Ъ~ з + г, где г, удовлетворяющее неравенству О < г < 2», прибавля- 3 зм»1 »»м» ется при необходимости для округления», чтобы з было кратным 2»». И наконец присвоить й»- й + 1. КЗ. [Завершеноу) Если 2» < и, то вернуться к шагу К2; в противном случае выполнение алгоритма заканчивается. $ Этот алгоритм основывается на алгоритме, предложение»» С. А. Куком (Б. А. Соо)»).
Похожий алгоритм использовался прн разработке арифметического блока компьютера [см. Апс)егзоп, Еаг1е, Со!ОэсЬш1»(», Рожег», ХВМ Х Яеа Нем 11 (1967), 48-52]. Конечно, нужно тщательно проверять точность алгоритма К, так как он находится иа грани того, чтобы быть некорректным. По индукции докажем, что в начале и в конце шага В2 выполняются неравенства »<2 и [з — 1/в[<2» . (55) Обозначим через з» значение з, вычисленное после й итераций иа шаге К2, и пусть б» =1/е — »». При А =О имеем бе = 1/в — 8/е'+ (32/е' — [32/и'))/4 = »»» + пз где е' = (е»етез)з и»Ь — — (е' — 8е)/сг'. Прн этом параметры и» н г»з удовлетворяют неравенствам -! <»»» < О и 0 < г»з < -', Значит, [Бе~ < -'. Теперь предположим, что второе неравенство в (55) удовлетворяется при 1». Тогда б»+» = 1/е — з»+» = 1/е — з» вЂ” з»(1 -- »»Ю — г = 5» — з»(1 — »»е) — х»(е — г») — г = 6» — (1/е — б»)еỠ— з»з(с — 1'») — г 3 = ед» вЂ” »»(е — %») — г.
Отсюда следует, что О < еб»» < 5»» < (2 т )» = 2 з и О < »е(е — 1' ) + г < 4(2 з з) + 2 з ' = 2 з так что [5»+»[ < 2 . Осталось еще проверить первое неравенство в (55). Чтобы з».~1 убедиться в том, что»».»~ < 2, рассмотрим три случая: а) г» = 1», тогда»»+» = 2; з»~1 Ь) 1» ~ 1» = Ъ»», тогда»» = 2, поэтому 2»» — »»1'» < 2 — 2 з с) г» ~ ~,тогда»»~~ =1/е — Ю»+, <2 — 2 з < 2,таккак й >О. Время., затрачиваемое на выполнение алгоритма К, ограничено сверху количеством циклов, равным 2У(4п) + 2У(2п) + 22'(и) + И'(»,и) + - + О(п), где Т(п) †верхн оценка времени, необходимого для выполнения оперении умножения и-битовых чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
