AOP_Tom2 (1021737), страница 92
Текст из файла (страница 92)
Итак, доказана следующая теорема. и = (0100 1101 0010) э на число е = (1001 0010 0101) г (12) Пусть г = 2. Полиномы ГГ(х) и И(х) в (8) имеют вид Н(х) = 4хэ+13х+2, И(х) = 9х + 2х+5. Отсюда находим для Иг(х) = У(х) г'(х): (7(1) = 19, Н(2) = 44, (Г(3) = 77, (Г(4) = И(1) = 16, И(2) = 45, И(3) = 92, 1г(4) = 157; И'(1) = 304, Иг(2) = 1980, Иг(3) = 7084, И'(4) = 18526. (13) ГГ(0) = 2, И(0) = 5, И'(О) = 10, Теперь нужно найти пять коэффициентов полинома Рг'(х), используя пять последних величин.
Чтобы найти коэффициенты полинома Иг(х) = Иг гх ' + + Иг1х+ Иэ при заданных значениях И'"(О), И"(1), ..., И'(т — 1), можно воспользоваться одним интересным алгоритмом. Сначала запишем И'(х) =а |х=+а эх=+ +а1х1+ао, (14) где хй = х(х — 1)... (х — )г+ 1), а коэффициенты а.
неизвестны, Полиномы вида (14) обладают важным свойством: И'(х+ 1) — И~(х) = (т — 1)а гх=~ + (т — 2)а гх=з + + аН отсюда по индукции получаем, что для всех й > 0 — ~Иг(х+й) — ( )И'(х+/г — 1) + ( )Иг(х+/с — 2) — + ( — 1) И'(х) 1 / /Йй //с~ ь Н~ ~1/ ~2) =( )а ~х ' +( )а эх +..+( )аы (15) теоретической точки зрения, так как в ней не в полной мере используется лежащий в ее основе полиномиальный метод. Если предположить, что г варьнруетсл вместе с и, то, выбирая по мере увеличения и все ббльшие и ббльшие значения г, можно получить лучший результат. Эта идея предложена А,,Л.
Тоомом (ДАН СССР 150 (1963), 496-498). Тоом использовал ее для доказательства того факта, что прн возрастающем и можно построить автомат для умножения и-разрядных чисел, состоящий из довольно малого числа компонентов. Позднее С. А. Кук (8. А. Спок) в работе Оп гЬе Мш1тшп Сошрпгайоп Типе оГ г1шсбопэ (ТЬеэ1э, Нагтагб 11шнегэйу, 1966), 51 — 77, показал, как применить идею Таама для ускорения работы компьютерных программ. Прежде чем продолжить обсуждение алгоритма Таама-Кука, рассмотрим простой пример перехода от Н(х) и Ъ'(х) к коэффициентам функции И~(х). На этом примере нельзя ощутить эффективность метода, поскольку используемые в нем числа слишком малы.
Но пример демонстрирует полезные упрощения, которые можно применять и в общем случае. Предположим, что нужно умножить и = 1234 на г = 2341 или в двоичной системе счисления число Обозначив левую часть (15) через (1/Ы) ~Зь И'(х), замечаем, что — Ь И'(х) = — ~ Ь Иг(х + 1) — Ь И'(х) 1/ 1 й) й ),(~ — ц( (к — 1)! и (1/Ы) йь И'(0) = аь. Таким образом, коэффициенты а можно вычислить при помощи очень простого метода, который иллюстрируется здесь на примере полинома И'(х), определенного соотношениями (13).
10 304 1382/2 = 691 294 7084 5104 6338Д = 3169 1455/3 = 85 18526 11442 Крайняя слева колонка этой таблицы состоит из заданных значений И'(О), Иг(1),... ..., Иг(4). Чтобы вычислить элементы в й-й колонке, нужно найти разность между соседними элементами предыдущей колонки и разделить эти разности на к. Коэффициенты а, — это верхние числа в колонках, так что ае — — 10, а1 = 294, ..., а4 = 36; отсюда имеем И'(х) = Збх4 + 341хз + 691хй + 294х1 + 10 = (((36(х — 3) + 341)(х — 2) + 691)(х — 1) + 294)х + 10. (17) В общем случае можно записать И (х)= (...
((а ~(х — т+2)+а„, г)(х — т+3)+а -з)(х — т+4)+ +а|)х+ае. Данная формула показывает, каким образом с помощью коэффициентов а„, можно вычислить коэффициенты И' -ы..., %, Ио. (18) 10 В этой таблице числа, расположенные ниже горизонтальных линий, являются соответственно коэффициентами полиномов а„, м а ~(х — т+ 2) +а -г, (а 1(х — пт + 2) + а э)(х — гп + 3) + а -з и т.
д. Согласно данной таблице имеем И'(х) = Збх +125хз+64х + 69х+10, (19) так что ответом будет 1234. 2341 = Иг(16) = 2888794, где И'(16) вычисляется с помощью операций сложения и сдвига. В разделе 4.6.4 рассмотрено обобщение этого метода вычисления коэффициентов. Из основного тождества для чисел Стирлинга (см. упр.
1.2.6-(45)), х" = ( ~хв+ ° + ( ~х-+( видно, что, если коэффициенты полинома И'(х) неотрицательны, таковыми же будут и числа а . В этом случае все промежуточные результаты в вышепрнведенных вычислениях неотрнцательны. Данное обстоятельство еще больше упрощает алгоритм умножения Таама-Кука, который теперь будет рассмотрен подробно. (Нетерпеливые читатели могут перелистать страницы подраздела С.) Алгоритм Т (Умножение с высокой точностью двоичных чисел). Для заданных положительного целого числа п и двух неотрицательных и-битовых целых чисел и и е этот алгоритм (рис. 8) формирует их 2п-бнтовое произведение ю. Для хранения длинных чисел, представляющих промежуточные результаты выполнения алгоритма, используются четыре вспомогательных стека.
Временное хранение П(1) и У(у) на шше Т4 Сомножители и управляющие коды Сохранение величин И'(у) Стеки П, У Стек С Стек И' 1се — 1, до е — 91+-16, гв < — гз ~ — 4, Ю з — 4, Ле — 2. Если теперь дз 1 + д„< п, присвоить 1с+- 1+1, (~ < — О+Л, Л»- (чД), дь < — 2С1, гз е-2н и повторять эту операцию до тех пор, пока не выполнится условие дз з+йь > и. (Примечание. Для вычисления Л < — (ъЯ) нет необходимости в извлечении корня квадратного, так как при (Л+ 1) < б) можно просто присвоить Л е- Л+ 1, а если (Л+ 1)з > Ц, то нужно оставить Л неизменным (см.
упр. 2). На этом шаге строятся такие последовательности. 1 2 3 4 5 6 2з 2е 2з 2зо 2~з 2гв 2з 2г 2з 2з 2з 2з йь = 24 гз = 2з Эти стеки могут содержать либо двоичные числа, либо специальные управляющие символы, называемые "код-1", "код-2" и "код-3". Алгоритм формирует также дополнительнукз таблицу чисел йеэ гь, построенную таким образом, что ее можно хранить в запоминающем устройстве как линейный список, единственный указатель которого, перемещающийся по списку в обоих направлениях, может использоваться для выбора нужного текущего элемента из этого списка.
(Стеки С и И' используются для контроля рекуррентного механизма алгоритма умножения довольно простым способом, который является частным случаем общей процедуры, рассматриваемой в главе 8.) Т1. (Вычислить таблицы д, г.) Очистить стеки П, $', С и Иг и присвоить Рис. 8. Алгоритм Таама-Кука умножения с высокой точностью. При умножении 70 000-битовых чисел этот шаг закончился бы при значении й = 6, так как 70000 < 2гэ + 2гв ) Т2. [Занести и, с в стек.] Занести "код-1" в стек С, затем поместить и и с в стек С как числа, каждое из которых содержит ровно дь 1 + дь бит. ТЗ. (Проверить уровень рекурсии.) Уменьшить )г на 1.
Если й = О, то в вершине стека С находится в данный момент двв 32-битовых числа и н с. Извлечь из стека эти числа, присвоить га с- ис, пользуясь встроенной программой для умножения 32-битовых чисел, и перейти к шагу Т10. Если к > О, то присвоить г +- гь, а < — аы р +- аь г + дь и перейти к шагу Т4. Т4. (Разбить на г + 1 частей.] Число, находящееся в вершине стека С, будем рассматривать как список из г+ 1 чисел, каждое из которых состоит из д бнт. (П,... Сгибе)э». (В вершине стека С находится (г+ 1)е = (аь + дь+г) битовое число.) Для у = О, 1,...,2г вычислим р-битовые числа ( .
(Ну+ П-~)3+'''+С1)э+(7о = П(т) и поместим эти значения в стек Г (На самом дне стека П сейчас находится ЦО), затем следует П(1) и т. д., а на вершине стека — С(2г). Согласно упр. 3 имеем П(т) < П(2г) < 2т((2г)" +(2 )' '+. +1) < 2т+'(2г)" < 2э.) Далее извлекаем из стека С значения б'„... П1 Па. Теперь на вершине стека С находится другой список г+ 1 д-битовых чисел Ъ'„...
'гг)те, а р-битовые числа таким же образом должны быть помещены в стек 1т. После завершения этих действий переместить из стека С числа г'„...1т1)тэ. ТБ. [Выполнить рекурсию.) Величины код-2., И(2г), (7(2г), код-З, Ъ'(2г — 1), Б'(2г — 1), ..., код-З, Ъ'(1), (7(1), код-З, Ъ'(0)., 0(0) поместить последовательно в стек С, одновременно освобождая стеки 17 и !С "Код-4" поместить в стек Ж. Вернуться к шагу ТЗ. Т6. [Сохранить одно произведение.] [В этот момент алгоритм умножения сформировал в ю одно нз произведений И'(1) = Г(1)Р(1).) Поместить ю в стек И'.
(Число и содержит 2(щ+ йь ~) бит.) Вернуться к шагу ТЗ. Т7. [Найти все а.) Присвоить г +- гы д < — 7ы р < — 4ь ~ + пю (Сейчас в стек И' последовательно от дна к вершине помещена последовательность чисел, оканчивающаяся И'(О), И'(1),..., И'(2г), где числа И'(1) представлены как 2р-битовые.) Теперь для,~ = 1,2, 3,..., 2г выполнить следующий цикл: для Ф = 2г,2г — 1, 2г — 2,...,1 присвоить Иг(1) ь- (И'(1) — И'(! — 1))Д. (В цикле у должно увеличиваться, а 1 — уменьшаться.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
