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