Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 92
Текст из файла (страница 92)
(18) 10 В этой таблице числа, расположенные ниже горизонтальных линий, являются соот- ветственно коэффициентами полиномов а а ~(х — т+2)+а э, (а~ ~(х — го+2)+а,„-э)(х — т+3)+а з ит.д. Согласно данной таблице имеем Иг(х) 36х4+125хэ»64хэ»бйх» 10 (19) так что ответом будет 1234 2341 = И"(16) = 2888794, где И'(16) вычисляется с помощью операций сложения и сдвига. В разделе 4.6.4 рассмотрено обобщение этого метода вычисления коэффициентов. Нз основного тождества для чисел Стирлинга (см. упр. 1.2.6-(45)), х" =( ~хв+. +( )я»+) видно, что, если коэффициенты полинома Иг(х) неотрицательны, таковыми же будут и числа а . В этом случае все промежуточные результаты в вышеприведенных вычислениях неотрицагельны.
Данное обстоятельство еще больше упрощает алгоритм умножения Тоома-Кука, который теперь будет рассмотрен подробно. (Нетерпеливые читатели могут перелистать страницы подраздела С.) Алгоритм Т (Умножение с высокой п«ачносглью двоичных чисел). Для заданных положительного целого числа и и двух неотрицательных и-битовых целых чисел и и е этот алгоритм (рис. 8) формирует их 2п-битовое произведение ш. Для хранения длинных чисел, представляющих промежуточные результаты выполнения алгоритма, используются четыре вспомогательных стека. Стеки П, Ъ' Временное хранение (7(у) и $'(у) на шаге Т4 Стек С Сомножители и управляющие коды Стек И' Сохранение величин И'(1') Эти стеки могут содержать либо двоичные числа, либо специальные управляющие символы, называемые "код-1"', "код-2" и "код-3". Алгоритм формирует также дополнительную таблипу чисел 4»„г», построенную таким образом, что ее можно хранить в запоминающем устройстве как линейный список, единственный указатель которого, перемещающийся по списку в обоих направлениях, может использоваться для выбора нужного текущего элемента из этого списка.
(Стеки С и И' используются для контроля рекурреитиого механизма алгоритма умножения довольно простым способом, который является частным случаем общей процедуры, рассматриваемой в главе 8.) Т1. (Вычислить таблицы 4, г.] Очистить стеки П, У, С и И' и присвоить й«-1, 4о« вЂ” д««-16, го« вЂ” г» «-4, Я«-4, Н« — 2. Если теперь 4»» + 4» < и, присвоить й«-1+1, Д«-9+Н, Н«- (Я), «1» «-2ч, г» «-2" и повторять эту операцию до тех пор, пока не выполнится условие ®,. «+4» > и.
(Пр«ьмечаипс. Для вычисления Н «- (т/Ц) нет необходимости в извлечении корня квадратного, так как при (Н+ 1)з ( (~ можно просто присвоить Н «- Н + 1, а если (Н+ 1)э > 9, то нужно оставить Н неизменным (см. упр. 2). На этом шаге строятся такие последовательности.
й = 0 1 2 3 4 5 6 2в 2» 2ш 2»з 2и г» = 2э 2э 2з 2э 2з 2» 2« Рис. 8. Алгоритм Топив-Еука умножения с высокой точностью. При умножении 70 000-битовых чисел этот шаг закончился бы при значении й = б, так как 70000 < 2'з + 2'е.) Тй. (Занести и, о в стек.] Занести "код-1" в стек С, затем поместить и и о в стек С как числа, каждое из которых содержит ровно й»» + Е» бит.
ТЗ, (Проверить уровень рекурсии.] Уменьшить Й на 1. Если Й = О, то в вершине стека С находится в данный момент два 32-битовых числа н и е. Извлечь из стека эти числа, присвоить а~ Ф- ие, пользуясь встроенной программой лля умножения 32-битовых чисел, и перейти к шагу Т10. Если Й > О, то присвоить г+- гы7+-о», р» — е»» +~Ь и перейти к шагу Т4. Т4. (Разбить на г + 1 частей.) Число, находящееся в вершине стека С, будем рассматривать как список из г+ 1 чисел, каждое из которых состоит из е бит. Щ... (7»17о)т». (В вершине стека С находится (г + 1)й = (й» + о»+~)-битовое число.) Для у = О, 1,..., 2г вычислим р.битовые числа (" (С„у+С.-»)у'+" +С~)у+Се =(7(,() и поместим этн значения в стек Г (На самом дне стека П сейчас находится (У(0), затем следует П(1) и т.
д., а на вершине стека — (7(2г). Согласно упр. 3 имеем П(у) < П(2» ) < 2»((2г)" + (2г)" ~ + ° + 1) < 2т+'(2г)" < 2г,) Далее извлекаем из стека С значения С„... (7»бге. Теперь на вершине стека С находится другой список г+ 1 о-битовых чисел $'„... Ъ~ $'е, а р-битовые числа ( " Ку + 1: — )у + " + Юу + Уе = ~'(у) таким же образом должны быть помещены в стек г". После завершения этих действий переместить из стека С числа Ъ;...
Ъ|'ге. Т5, ]Выполнить рекурсию.] Величины код-2, (г(2г), П(2г), код-З, И(2г — 1), П(2г — 1), ..., код-З, И(1), С(1), код-З, (г(0), П(0) поместить последовательно в стек С, одновременно освобождая стеки о и Г. "Код-4" поместить в стек %. Вернуться к шагу ТЗ. Тб. (Сохранить одно произведение.] (В этот момент алгоритм умножения сформировал в ю одно из произведений И'(у) = ПЦ)У(у).) Поместить ш в стек И~.
(Число ш содержит 2(оь + йа 1) бит.) Вернуться к шагу ТЗ. Т7. (Найти все а.] Присвоить г +- гы д +- ды р <- йь 1+ йы (Сейчас в стек И' последовательно от дна к вершине помещена последовательность чисы, оканчивающаяся И'(О), И'(1),..., И'(2г), где числа И'(у) представлены как 2р-битовые.) Теперь для у = 1, 2, 3,..., 2г выполнить следующий цикл: для 1 = 2г, 2г-1, 2г — 2,,7 присвоить И'(1) +- (И'(8) — И'(1 — 1))Д. (В цикле,у должно увеличиваться, а 1 — уменьшаться. Величина (И'(1) — И'(Ф - 1)) /у всегда будет неотрицательным целым числом, занимающим 2р бит (см. табл, (16),) Т6.
(Найти все И'(у) ] Для у = 2г — 1,2г-2,...,1 выполнить следующий цикл: для 1 = у, 7+ 1, ..., 2г — 1 присвоить И'(8) +- 1т'(1) -уИ'(1+ 1). (В цикле у должно уменьшаться, а 1 — увеличиваться. Результатом этой операции снова будет неотрицательное целое число, занимающее 2р бит; см. табл. (16).) Т9. ]Сформировать ответ.] Сформировать в ш 2(йь + оьз.1)-битовое целое число (... (Иг(2г)2т + И'(2г — 1)) 2г + -+ И"(1))2г + И~(0). Удалить И" (2г), ..., И'(0) из стека И'. Т10. [Возвратиться.] Присвоить й +- й + 1. Извлечь число из вершины стека С. Если это "код-3", перейти к шагу Т6.
Если это "код-2", поместить тг в стек И' и перейти к шагу Т7. Закончить выполнение алгоритма, если это "код-Г (ш является искомым результатом.) ) Оценим время выполнения Т(и) алгоритма Т в некоторых единицах, называемых циклами, т. е. в количестве элементарных машинных операций. На выполнение шага Т1 уходит 0(дь) циклов даже в том случае, когда число 47э представлено в виде длинной цепочки из оь бит, за которой следует некоторый разграничитель, так как йь + Ь 1 + ° + ов равно 0(оь). Шаг Т2 выполняется за 0(йь) циклов. Обозначим через Фь объем вычислений, которые необходимо выполнить, чтобы от шага ТЗ перейти к шагу Т10 для некоторого конкретного значения к (после того, как в начале шага ТЗ значение й было уменьшено на 1).
На выполнение шага ТЗ требуется не более 0(о) циклов. На шаге Т4 выполняется г умножений р-битовых чисел на !6(2г)-битовых числа и г сложений р битовых чисел. Все эти операции повторяются 0(гзо1ойг) раз. Таким образом, общее количество циклов равно 0(гт4!ойг). На шаге ТЗ выполняется перемещение 4г + 2 р-битовых чисел, и на каждой итерации перемещение повторяется 2г + 1 раз. Для выполнения рекурсии, которая появляется, когда алгоритм повторяет сам себя (возвращаясь к шагу ТЗ), необходимо по 8э 1 циклов на каждой из итераций 2г + 1. На шаге Т7 требуется выполнить О(тз) вычитаний р.битовых чисел и делений р.битовых чисел на 1й(2т)-битовые числа, на что затрачивается 0(т~д)ойт) циклов, как и на шаге ТЗ. Для шаха Т9 необходимо 0(тд) циклов, а на выполнение шага Т10 время практически вовсе не затрачивается. Суммируя, получаем Т(и) = О(д») + 0(д») + 8» и где (при д = д» и г = г») основной вклад во время выполнения алгоритма удовлетворяет равенству 1» = 0(д) + 0(тзд1ояг) + 0(тд) + (йг+ 1)0(д) + О(тзд1ояг) + 0(тзд 1ой т) + О(тд) + 0(д) + (2т + 1)1»-» = 0(тзд)ойт) + (2г+ 1)1» и Следовательно, найдется константа с такая, что 1» < ст»д» 1я т» + (2т» + 1)$» м Чтобы завершить оценку »ы докажем (довольно грубо), что для некоторой константы С 1„< Сд~~, 2а»,т1в т,~, (20) Выберем С > 20с.
н пусть, кроме того, С настолько велико, что неравенство (20) справедливо для й < )ге, где йе будет уточнено ниже. Далее, для й > йе положим Я» = )яд», В» = )я т». По индукции имеем Ф» < сд»г»з)ят»+ (2т»+)Сд»2а» ч» = Сд»+~2 ' 'вг"+'(д»+ г1з), ш = — В»2~" а»"~'+' < — В»2 Я" < 0.05, С 20 дз = ~2+ — ра»1"~' -"~"+ 1- 2-'~' < о.йб, аз г» %, — 'с - 'а+ТЮ~- Я. при й -+ оо. Отсюда следует, что можно найти ке, такое, что дз с 0.95 для всех к > йе. На этом доказательство по индукции неравенства (20) завершается. С учетом полученного результата теперь можно оценить Т(и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
