AOP_Tom2 (1021737), страница 94
Текст из файла (страница 94)
Но специальная форма числа с дает ключ к решению: двоичное представление числа с имеет некоторую регулярную структуру битов, и из формулы (31) видно, что число с[26] может быть простым способом получено из числа с[6]. Это свойство наводит на мысль, что можно быстро умножить число и на с[6], если подходящим образом получить число с[Ь]и за !к6 шагов. Например, зто можно выполнить следующим образом. Пусть в двоичной системе счисления число 6 имеет вид Ь = (6, ... 6,6,6.),. Можно вычислить четыре последовательности чисел а», й», и», с», которые опреде- лены правилами а» = 2а» ь пюй 1; й» = (й» ь + Ь»а») пюйУ; и» = (и» ь + 2~' 'и» ь) той (2У вЂ” 1); в» = (с» ь + 6» 2~'-'и») пюй (2у — 1). по=е, йо = Ьое, ио — — и, со = Ьои, (32) Индукцией по Ь легко доказать, что а» = (2"е) пьой У; й» = [(Ь» ЬьЬо)з е) той У; и» = (с[2" ]и) пюй (2У вЂ” 1); (ЗЗ) о» = [с[(6» ..ЬьЬо)з]и) той (2У вЂ” 1).
Следовательно, искомый результат (с[Ь]и) пюй (2т — 1) будет равен с,. Для вычисления а», й», и» и г» по а» „й» ы и» ы о» ь требуется О(!оба') + О(!ой ~) + для выполнения только 0(е„!обе„) циклов, а потому весь процесс перехода можно выполнить за 0(гое„!ой е,) циклов. После этого остается решить следующую задачу. Для заданных положительных целых чисел е и у (е < у) и неотрицательного целого числа и < 2у найти значение (си) шой (2У вЂ” 1), где число г таково, что (2' — 1)с = 1 (по модулю 21 — 1), причем вычисления должны быть выполнены за 0(у !ок () циклов.
В ответе к упр. 4.3.2-6 приведена формула для с, которая наводит на мысль о необходимости использовать здесь ту же процедуру. Прежде всего найдем наименьшее положительное целое число 6, такое, что 0(У) + 0(У) = 0(1) циклов, позтому весь объем вычислений можно выполнить, как и требовалось, за о 0(у) = 0(1 !о8 /) циклов. Тщательный анализ оригинального метода, представленного формулами (32) и (33), принесет читателю много пользы, Подобные методы рассматриваются в разделе 4.6.3. В работе Шенхаге, опубликованной в Сошриоспя 1 (1966), 182 — 196, показано, что зти идеи могут быть распространены на операции умножения и-битовых чисел с использованием модУлей г — 2 осо" с в РезУльтате чего 6Удет создан метод, аналогичный алгоритму Т.
Мы не будем здесь останавливаться на деталях этого метода, поскольку алгоритм Т всегда имеет приоритет. К тому же сейчас будет рассмотрен еще лучший метод. С. Умножение прн помощи дискретного преобразования Фурье. Основной проблемой при умножении с высокой точностью является вычисление "свертки", например и„ее+ и. се) +... +иое„, (34) а между свертками и важным математическим понятием, называемым "преобразование Фурье", имеется тесная связь. Если ьс = ехр(2яс/К) есть корень К-й степени из единицы, то можно определить одномерное преобразование Фурье последовательности комплексных чисел (ио, ис,..., ик с) как последовательность (йо, йс,...
...,йк-с), где й,= с се"ис, 0<о<К. (35) о<с<к Положив, что (йо,йс...,,дк с) — такое же преобразование Фурье для последовательности (ео, ес,..., ек с ), нетрудно заметить, что (йойо, йс ос,..., йк с ек — с ) будет преобразованием Фурье для (шо, исс,..., иск-с), где ис« — — и„ео+и„се, + +иве, +ик-се«+с+... + и +сок-с (36) сс-ун«спо модулю К) В случае, когда К > 2п — 1 и и„= и„.«с —— — — ик с —— е„= е .«с = . — — ек-с = 0: числа ш — зто как раз то, что необходимо для операции умножения, поскольку в (36) члены ик се,.ь) + + и,ч.сок с при 0 < г < 2п — 2 исчезают.
Другими словами, преобразование от свертки есть обычное проссзвелессие преобразований компонентов. Это частный случай идеи Тоома, связанной с использованием полиномов (см. выражения (9) н (10)), причем х заменяется корнями из единицы. Для К, равного степени 2, дискретное преобразование Фурье (35) может быть получено очень быстро, если вычисления выполняются в определенной последовательности; именно таким образом выполняется обратное преобразование Фурье (определение чисел ю из Ф). Такое свойство преобразования Фурье было использовано в 1968 году Ф.
Штрассеном ('Ч. Ясгаозеп), который предложил способ умножения больших чисел, более быстрый, чем зто было возможно с использованием любых известных к тому времени методов. Позже вместе с Шенхаге он уточнил метод и опубликовал модифицированные алгоритмы в Сотрибпй 7 (1971), 281-292, Похожие идеи, но для произвольных целых чисел, были независимо от Ф.
Штрассена предложены Дж. М. Поллардом (Л. М. Ро!!агс)), Маз)з. Сопзр. 25 (1971), 365-374. Чтобы понять значимость их вклада в решение проблемы, рассмотрим для начала механизм быстрого преобразования Фурье. Для данной последовательности К = 2в комплексных чисел (ио,..., ик з) и данного комплексного числа ы = ехр(2з з/К) (37) последовательность (йо,..., йк з), определенная выражением (35), может быть быстро вычислена по следующей схеме. (Параметры в, и з в зтих формулах равны либо О, либо 1, так что на каждый "проход" приходится 2" элементарных вычислительных операций.) Проход О. Пусть А)о)(вь ы...,1о) = ин где! = (зь з 1о)з.
Проход 1. Присвоить А(~)(вь ызь з,...,во) е- А)~)(0, зв з,..., !о) + ьзз '*-'А~ ~(1, Зз-з,, зо). Проход 2. Присвоить А(з)(вь ы вь з,зв-з,, 1о) е- А)~)(вь з,0,1в з,...,1о) +ыз ! в з)з.4! )(вь ы1,1ь — з " ° 1о) Проход )с. Присвоить А)~)(вз ы..., вы во) е- А(ь ')(в,..., вы 0) + ы!"" -"-')гА!" з! (вь ы..., вз, 1). По индукции очень просто доказать, что А(з)(в, ... в З ...,1 ) = ~ ~ьзз бм з"" ')зр'-' -"- )*и (38) вь-з ...
вь-з ь-1-~ ..., о) = иь о«м „...,ю,,бз где 1 = (сз-~ ззво)з, так что А!")(вь ы...,выво) = йт, где в= (вовз...вь з)з. (39) (Важно отметить, что двоичные цифры числа в в конечном результате (39) обращены. В разделе 4.6.4 приводится дальнейший анализ такого рода преобразований.) Прежде чем приступить к поиску обратного преобразования Фурье (ио,... ...,ик з) по значениям (йо,...,йк з), заметим, что "двойное преобразование" имеет вид сии Х~~ ~ с и о<е<к о<ив<к — из ~~ ы ~ —— ° иб г)п аК, з(з+г) з о<з<к о«к (40) 2п<2"1<4п, К=2", (41) так как для з, кратных К, сумма геометрической прогрессии 2 о«,коз'з равна нулю. Поэтому обратное преобразование может быть получено точно так, как и прямое, за исключением того, что конечный результат делится на К и немного сдвинут. Возвращаясь к проблеме умножения целых чисел, предположим', что нужно вычислить произведение двух и-битовых целых чисел и и и.
Будем оперировать (как и в алгоритме Т) группами битов. Положим и запишем (42) и = (Ук-1 Ь1Пе)ш г = (1''к-1 .. 1)Ъо)ь, полагая числа и и е К-разрядными чигламн по основанию Е, так что каждый из разрядов б' или Ъ' есть 1-битовое целое число. Поскольку 2ь 1! > и, ведущие разряды в (!! и 1гу для всех 2 > К/2 равны нулю. Соответствующие значения для ?г и ! будут выбраны позже, когда в процессе решения задачи прояснится общая ситуация и можно будет при выборе к и ! учесть всю имеющуюся информацию. Следующим шагом в процедуре умножения является вычисление преобразований Фурье (йе,...,йк 1) и (йе,,.,,дк ~) последовательностей (ие,...,ик 1) и (ее,, ек 1), где по определению н~ = ('с/2~~~, е~ — — К/2~+~.
(43) Для удобства масштабирование выполнено так, что любые и~ и и, меньше 2 а это, в свою очередь, обеспечивает то, что абсолютные значения )й,( и )ь',) оказываются меньше 1 для всех э. Здесь возникает очевидная проблема, связанная с тем, что комплексное чигло ы не может быть точно представлено в двоичной системе счисления.
Как же вычислить достоверное преобразование Фурье? Провидению было угодно, чтобы результат получился правильным даже в случае, если в процессе вычислений предъявить весьма скромные требования к точности представления чисел. Оставим на время эту проблему и предположим, что вычисления выполняются с бесконечной точностью. Анализ необходимой точности будет приведен несколько ниже (через пару страниц). Для полученных й, и О, положим ю, = й,й, (О < э < К) и определим обратное преобразование Фурье (юе,..., юк ~).
Как было разъяснено выше, получим е„= ~: и;е = С (',Ъ;/2 так что целые числа Иг„= 2зь+т'и:, являются коэффициентами искомого произве- дения (4 К-2 1' + ' ' ' + И 1/' + )4 О. (44) Поскольку О < И"„< (г + 1)Ез < КЬз, каждое Иг, содержит не более й+ 2! бит, поэтому нетрудно получить двоичное представление для известных величин Игю если только й не слишком велико по сравнению с !. Например, пусть нужно умножить и = 1234 на е = 2341 при к = 3 и ! = 4. Вычисление изображения (йе,..., йт) по оригиналу и выполняется следующим образом (см.
(12)). (г, э, Г) = (О, О, 0) (О, О, 1) (О, 1, О) (О, 1, 1) (1, О, 0) (1, О, 1) (1, 1, О) ( 1, 1, 1) 2 А~~~(г,э,с) = 2 13 4 0 0 О 0 0 2 АО~(г,э,Г) = 2 13 4 0 2 13 4 0 2~АОО(г, э, г) = 6 13 — 2 13 2 + 4а 13 2 — 41 13 2~А~~1(г,э,1) = 19 — 7 -2+ 13а — 2 — 131 6+ 3 о — д 6 — рЗ 6+ 3Г Здесь а = 2+41, р = 13ы и ы = (1+!)/ьГ2. Это дает нам колонку й, в табл. 1. Данные в колонке д, получаются из о аналогично. После этого находим ф„умножив й, на й,. Выполняем еще одно преобразование, учитывая соотношение (40), и получаем и, и Иг,.
Итак, мы получили свертку (19), но на этот раз используя комплексные Таблица 1 УМНОЖЕНИЕ ПРИ ПОМОЩИ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 2 оза 80 0 0 0 288 1000 512 552 1б 5 + 9г + 2м -4+ 2г 5 — 9г — 2Ф 12 5+ 9г -з,г -4 — 2г 5 — 9г+ 2Ф числа вместо того, чтобы оставаться верными методу, оперирующему только целыми числами. Попробуем теперь оценить время, необходимое этому методу при больших числах, если использовать ш-битовую арифметику в формате с фиксированной точкой. Из упр.
10 видно, что в процессе преобразования все величины А(!! будут меньше 1 из-за масштабирования (43). Следовательно, достаточно иметь дело только с дробными ш-битовыми частями (.а,...а )2 для действительной и мнимой частей любых промежуточных результатов. Так как входные величины иг и ег являются действительными числами, можно упростить вычислительную процедуру, а именно — вместо 2К действительных значений на каждом шаге преобразований использовать только К значений (см. упр. 4.6А — 14). Чтобы не усложнять выкладки, далее эти тонкости учитывать не будем. Прежде всего необходимо вычислить го и ее степени. Для простоты сформируем таблицу значений иго,..., огк '.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
