Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 93
Текст из файла (страница 93)
Поскольку и > д»»+д» з, той»» < и, Получаем 2!ъг1вт» ~1 2 Лап н д»=т» ~д»»<и2~1в Таким образом, , < Сд,2а»,~Гам < С„2 % +а»1,% +0 и, учить»вая, что Т(и) = 0(д») + Ф» ы мы сформулировали следуюшую теорему. Теорема В. Существует консшнта се, иван, что время выполнения алгорнтча Т меньше, чем сои2з'з~ "в" циклов. ! Поскольку п2з-в'~'в" = и'+з вэ 'в", этот результат существенно сильнее, чем теорема А. Несколько усложнив алгоритм и распространив эти идеи вплоть до очевидных ограничений (см.
упр. 6), можно улучшить время выполнения, добившись оценки Т(п) = 0(рр2Рмв "1о8 и). (21) Чв =1, Ф:+р =3чв — 1, (22) так что 4» = 3" — 3~ ' — — 1 = -'(3" + 1). Исследуем процедуру, выполняющую умножение рв-битовых чисел, где рв = (189в + 8), в терминах метода умножения рь мбнтовых чисел. Итак, если известно, как умножать числа, состоящие пз рв = 26 бит, описываемая ниже процедура покажет, как умножать числа из рр = 44, 98, 260 бит и т. д., увеличивая количество битов почти в трн раза на каждом шаге.
При умножении рв-битовых чисел идея состоит в использовании шести модулей: т1 = 2ар' ' — 1, рпв=2 Р' — 1, тз = 2ввв+з 1 (23) 2вРР+Р тз —— 2вв" +' — 1, тв = 2вв""в — 1, Эти модули взаимно просты согласно соотношению 4.3.2-(19), так как показатели степени в (23) бйв — 1, бар+1, ЬУв+2, бар+3, 647в+5, бар+7 (24) всегда взаимно просты (см.
упр, 6). При помощи шести модулей в (23) можно пРедставлЯть числа вплоть до т = т1тртзгпргпвтв > 2эвв"+ы = 2~"", и поэтомУ при умножении рв-битовьгх чисел и и и возможность переполнения совершенно исключена, Таким образом, при й > 0 можно использовать следующий метод. а) Вычислить и1 —— ипюр1ты ..., ив —— ипюбтв и и1 = ипюдгпм ..., ив = и пюр( тв. Ъ) Умножить и1 па им из на вт, ..., ив на ив. Эти числа состоят не более чем нз бар + 7 = 189в р + 1 < рв р бит, поэтому операции умножения могут быть выполнены при помощи процедуры, используемой для умножения рв р-битовых чисел. с) Вычислить рвр — ирнр шод рпм раз = изнв шоб тш ..., рвв ивпв шод тв.
6) Вычислить ю, такое, чтобы выполнялось неравенство 0 < ю < т, ш пюб т1 = рс„..., рв шод тв = рвв. вВ, Модулярный метод. Существует еще один метод очень быстрого перемножения больших чисел, основанный на идеях модулярной арифметики, которые представлены в разделе 4.3.2.
На первый взгляд, трудно поверить„что он может иметь какие-либо преимущества, так как алгоритм умножения, основанный на модулярной арифметике, кроме собственно операции умножения, должен включать процедуры выбора модуля и перевода чисел в модулярное представление н обратно. Несмотря на такие пугающие трудности А. Шенхаге (А. БсЬопЬабе) обнаружил, что все эти операции можно очень быстро реализовать. Чтобы лучше понять суть метода А. Шенхаге, рассмотрим один частный случай — последовательность, определенную по правилам Пусть время, требуемое для выполнения этого процесса, равно 1ы Нетрудно заметить, что на выполнение операции (а) необходимо 0(рь ) циклов, нбо определение и шод (2' — 1) осуществляется совсем просто (подобно "'выбрасыванию девяток'), как описано в разделе 4.3.2. Аналогично на операцию (Ь) уходит 0(рь) циклов. Остается операция (и), которая, на первый взгляд, требует выполнения сложных вычислений.
Но Шенхаге нашел оригинальный способ выполнения операции (4) за 0(рв 1ойрь) циклов. В этом и состоит сущность предложенного метода. Как следствие имеем 1ь = б1ь ~ + 0(Рь 1ойРь). Так как рь = 3~+э + 17, можно показать, что время, затрачиваемое на умножение и-битовых чисел, раино Т( ) О( 1аа~ 6) О( г.ез!) (25) (См. упр. 7.) Хотя модулярный метод сложнее, чем описанная в начале этого раздела процедура, на выполнение которой требуется 0(п'аз) циклов, в действительности время, затрачиваемое на умножение согласно формуле (25), существенно меньше времени 0(пз) на умножение и-битовых чисел. Таким образом, используя один из совершенно разных методов, рассмотренных выше, можно усовершенствовать классический метод умножения и-битовых чисел.
Теперь проанализируем упомянутую выше операцию (с1). Предположим, что дан ряд положительных попарно взаимно простых целых чисел с~ < ез < - ° < е,. Пусть т~ = 2" — 1, тт —— 2" — 1, ..., т„= 2'" — 1. (26) Пусть также даны числа юм ..., ю„, такие, что О < и~у < гп . Задача состоит в том, чтобы определить двоичное представление чисел ю, удовлетворяющих условиям О < ю < т~тз...
т (27) ю = ю~ (по модулю т~), ю ьз ю„(по модулю т„). Метод основан на использовании соотношений (24) и (25) из раздела 4.3.2. Вычис- лим'сначала ю1 = (... ((ю — ю',)сц — ю') сзу — "— и',) с11,О шод тз (28) для 7' = 2, ..., г, где ю', = ю, шос)тм Затем вычислим ю = (...(ю'„т„, +ю'„,)т„, +" +юз) т, +ю',. (29) В этом равенстве с;. — такое число, что с; т, ьз 1 (по модулю гпу); числа сб должны быть определены по числам е . При любых у для вычисления по формуле (28) требуется (") операций сложения по модулю т, на каждую из которых затрачивается 0(е„) циклов, плюс (') операций умножения на с;, по молу~по т .
Вычисление ю по формуле (29) требует т операций сложения и г операций умножения на т1. Но операция умножения на т выполняется легко, ибо это просто сложение, вычитание н сдвиг, поэтому ясно, что на выполнение вычислений по формуле (29) затрачивается 0(гтс,) циклов. Как вскоре будет видно, каждая операция умножения на с;. по модулю т требует Ье = 1 (по модулю ~), (30) При помощи алгоритма Евклида это можно сделать за 0((!ой у)~) циклов, так как данному алгоритму для обработки чисел е и у требуется 0(!оя ~) итераций и каждая итерация выполняется за О((!ой у)з) циклов. Число Ь можно было бы пайти и путем простого перебора, ие изменяя общее время выполиения, а просто применяя Ь = 1, 2 и т.
д. до тех пор, пока це будет удовлетвориться (30). Этот процесс существеино не сказывается на общем времени выполиения, поскольку на него потребовалось бы всего 0(~ !ой у) циклов. После того как Ь найдено, в силу упр. 4.3.2-6 имеем Прямого умножения (си) щи (2г — 1) может оказаться иедостаточио л,ля решения зш»ачи, потому что иам неизвестно, как умножить у-битовые числа общего вида за 0(у !ой~) циклов. Но специальная форма числа с дает ключ к решению: двоичное представление числа с имеет некоторую регулярную структуру битов, и из формулы (31) видно, что число с[2Ь] может быть простым способом получено из числа с[Ь]. Это свойство наводит на мысль, что можно быстро умножить число и иа с[Ь], если подходящим образом получить число с[Ь]и за !6Ь шагов.
Например, это можно выполнить следующим образом. Пусть в двоичной системе счисления число Ь имеет вид Ь = (Ь,... Ь,Ь Ь,). Можно вычислить четыре последовательности чисел а», д», вы с», которые опреде лены правилами а» =2а» ~ шойу'; й» = (~4» 1+ Ь»о») шов ~; и» = (и»»+2ы-'и»») шос) ф -1); е» = (е» ~ + Ь» 2Я"-'в») шоп (2У вЂ” 1).
ае = е, 4~ = Ьее, ие = в, - =Ьи, (32) Ицдукцией по й легко доказать, что а» = (2»е) шоб У; й» = ((Ь»...Ь»Ье)ге] шоб у'; и» = (с[2" ]и) щи (2У вЂ” 1); (33) с» = (с[(Ь» ° ° . Ь1ЬО)2]и) пюг) (21 — 1). Следовательно, искомый результат (с[Ь]п) шой(2г — 1) будет равен с,, Для вычисления а», о», и» и в» по а» м и» ы и» ы с»» требуется О(!ой у) + 0(!оба) + для выполнения только 0(е„1оя е,) циклов, а потому весь процесс перехода можно выполол гь за О(гзс„!ой с„) циклов. После этого остается решить следующую задачу. Для заданных положительных целых чисел с и у (е < у) и неотрицательного целого числа в < 2г найти значение (си) щи (2г — 1), где число с таково, что (2е — 1)с ш 1 (по модулю 2г — 1), причем вычисления должны быть выполнены за 0(у 1ояу) циклов. В ответе к упр.
4.3.2-6 приведена формула для с, которая яаводит иа мысль о необходимости использовать здесь ту же процедуру. Прежде всего найдем наименьшее положительное целое число Ь, такое, что О(у) + 0(,К) = 0(у) циклов, поэтому весь объем вычислений можно выполнить, как и требовалось, за вО(у) = 0(7" 1ойу) циклов. Тщательный анализ оригинального метода, представленного формулами (32) и (33), принесет читателю мною пользы. Подобные методы рассматриваются в разделе 4.6.3. В работе Шенхаге, опубликованной в СошриО(п8 1 (1966), 182-196, показано, что зти идеи могут быть распространены на операции умножения и-битовых чисел с использованием модулей г ж 2 з)к", в результате чего будет создан метод, аналогичный алгоритму Т. Мы не будем здесь останавливаться на деталях зтого метода, поскольку алгоритм Т всегда имеет приоритет.
К тому же сейчас будет рассмотрен еще лучший метод. С. Умножение прн помощи дискретного преобразования Фурье. Основной проблемой прн умножении с высокой точностью является вычисление "свертки"', например ивео+и, 1е) + ° ° ° +ион„, (34) а между свертками и важным математическим понятием, называемым "преобразование Фурье", имеется тесная связь. Если ы = ехр(2к(/К) есть корень К-й степени нз единицы, то можно определить одномерное преобразование Фурье последовательности комплексных чисел (ио,им...,ик 1) как последовательность (йшйп .., ...,йк 1), где й, = ~ ымип 0< в С К.
(35) о<с<к Положив, что (йо,йм...,йк 1) — такое же преобразование Фурье для последовательности (ео,ем...,ек )), нетрудно заметить, что (йой),610),...,йк-1ек )) будет преобразованием Фурье для (юо, шы..., юк 1), где ю, = и„ео + и„~и~ + " + иое„+ ик-~е,+1+ " + и„+1ек ~ (36) )+тнг (пв модглю к) В случае, когда К > 2п — 1 и и„= и„+~ = ° - -ик 1 — — е„= е„+1 = ° = ек-1 = 0: числа ю — это как рвз то, что необходимо для операции умножения, поскольку в (36) члены ик 1е,+1+ ° + и„+1ек ) при 0 < г < 2п — 2 исчезают. Другими словами, преобразование от свертка есть обычное произведение преобразований компонентов.
Это частный случай идеи Тоома, связанной с использованием полиномов (см. выражения (9) и (10)), причем я заменяется корнями из единицы. Для К, равного степени 2, дискретное преобразование Фурье (35) может быть получено очень быстро, если вычисления выполняются в определенной последовательности; именно таким образом выполняется обратное преобразование Фурье (определенне чисел ш из ш). Такое свойство преобразования Фурье было использовано в 1968 году Ф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
