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