Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/02/10.pdf Дата изменения: Fri Dec 23 19:25:04 2005 Дата индексирования: Tue Oct 2 00:09:30 2012 Кодировка: Windows-1251

ную запись некоторого числа х:
x = x0 + x1 10 + x2 10 + K + xn 10 ,
1 2 n

КВАНT$ 1999/?2

где xi цифры. Не правда ли, это очень похоже на запись многочлена? Да и умножению в столбик чисел соответствует умножение в столбик многочленов. (Разница только в отсутствии переноса разрядов у многочленов.) А нельзя ли два многочлена умножить быстрее, чем в столбик, используя меньшее число умножений коэффициентов? Оказывается, можно! Пусть P t и Q t два многочлена степеней m и n соответственно. Тогда их произведение P t Q t есть многочлен степени m + n. А он определяется своими значениями в m + n + 1 точке. Например, в точках 0, + 1 , +2 , ..., + m + n . Поэтому, чтобы найти многочлен PQ, ищем значения Р и Q в этих точках и перемножаем (получается m + n + 1 умножение). Тем самым мы найдем значения PQ в m + n + 1 точке, по которым восстанавливается PQ и находятся все его коэффициенты. Например, пусть P t = At + B, Q t = Ct + D линейные двучлены. Их произведение квадратный трехчлен PQ t = AC t 2 + BC + AD t + + BD . Найдем его коэффициенты. 1. Находим BD = P 0 Q 0 первое умножение. A+B C+D = 2 . Находим = P 1 Q 1 второе умножение. 3. Находим B - A D - C = = P -1 Q -1 третье умножение. Беря полуразность выражений A + B C + D и B - A D - C , находим второй коэффициент PQ, т.е. BC + AD, а вычитая BD из полусуммы A + B C + D и B - A D - C , находим АС. И мы пришли почти что к формулам Карацубы! 1 Идея метода КарацубыТоома заключается в том, чтобы разбить запись 2n-значных чисел X = AB, Y = =CD на блоки по n разрядов. Тем самым числа Х и Y представляются в виде At + B и Ct + D, где t = 10 n для десятичной системы счисления (в n общем случае t = q , q основание системы счисления). А после этого можно перемножить полученные (линейные) многочлены. Теперь ясно, как обобщить этот метод. Попробуем разбивать числа не

bg

bg bg bg g

b

bg

bg

bg

bg b g

bg b g b gb g b gb g b

bg bg b gb g b gb g
gb g

b

g

на два, а на большее число блоков. Например, на три. Пусть x1 = A1 B1C1 , x2 = A2 B2 C2 разбиение 3n-значных чисел x1 , x2 на блоки по n разрядов. Пусть t = 10 n . Тогда числа x1 , x2 можно представить в виде P t = 2 = At 2 + B1t + C1 и Q t = A2 t + B2 t + 1 + C2 соответственно. Будем действовать, как в предыдущем случае. Найдем произведение многочленов Р и Q. Для этого найдем их значения в точках 0, +1, + 2 и перемножим. Получится 5 умножений k-значных чисел (и еще несколько сложений и умножений на 2 и 4). Далее, зная значения многочлена PQ в этих точках, найдем его коэффициенты. Они получаются путем умножения и деления на небольшие числа. Это требует не более 40 сложений (см. упражнение 1). Таким образом, мы свели задачу умножения 3n-разрядных чисел к пяти операциям для n-разрядных чисел и еще к операциям сложения, деления на маленькие числа и сдвига. Это дает оценку порядка nlog 3 5 на число операций. В самом деле, пусть 3 k <
щее рассуждение. Пусть х и у два n r + 1 -значных числа. Представим их в виде rn n x = 10 r + K + 10 1 + 0 ,

bg

bg

bg

y = 10 r + K + 10 1 +

rn

n

0

и положим
pt =

bg
k=0 2r

r

k t , q t =
kt
k

k

bg
k=0

r

k t ,
n

k

st =

bg
k =0

xy = s 10 .

ej

В следующем пункте будет показано, что Коэффициенты полинома s вычисляются через линейные выраже,и ния от 2r + 1 чисел k=0 это требует C r n операций. Таким образом, нахождение произведения n r + 1 -значных чисел требует 2r + 1 'больших умножений' n + Dr -значных чисел, где Dr некоторая константа, зависящая от r, и C r n элементарных операций.

c

bg

Упражнение 7. Докажите, что константу Dr можно положить равной числу знаков в r числе r r +1 = r t , t = r.

bg

h

bg

bg

bg mpbkgqbkgr

2r

В итоге приходим к оценке

5=3

k

ej
k

log 3 5

n

log 3 5

n .

1.3

T r + 1 n 2 r + 1 T n + Dr + cn .
s

b

gb

gb

gb

g

Упражнения 3. Выведите формулы для коэффициентов многочлена R t четвертой степени по его значениям в точках 0, + 1 , +2 . 4. Пусть е фиксированное натуральное число. а) Докажите, что алгоритм 'умножения в столбик' n-значных чисел на число е имеет сложность порядка n. Его сложность можно оценить величиной 10k n , где k число разрядов в числе е. б) Докажите, что алгоритм 'деления в столбик' n-значных чисел на число е имеет сложность порядка n. Его сложность можно оценить величиной 10k n , где k число разрядов в числе е. 5. Покажите, что для нахождения произведения двух квадратных трехчленов с nзначными коэффициентами достаточно ограничиться 5n-значными умножениями и 30n элементарными операциями. 6. Докажите рекуррентное неравенство

cb g h b Пусть br + 1g bg

n

gc h b r + 1g .
s +1

bg

Тогда легко видеть, что при некотором r имеет место неравенство

T n r 2r + 1 ,
из которого вытекают асимптотические соотношения

b

g

s

T n ?n

bg

log r +1 2 r +1

b

g

?n

1+ log r +1 2

.

Поскольку для любого наперед заданного при достаточно большом r 1+ верно неравество r > 3, то r > 3r. Теперь ясно, что можно выбрать такое r, что при достаточно больших n выполняется неравенство

Tn
T 3n 5T n + 30 n .

bg

bg

Выведите из него асимптотическое неравенство

T n ?n

1 (B цуба ент

bg

log 3 5

.

Мы получили такой результат: Теорема (А.Тоом). Для любого > 0 существует такая постоянная c и такой метод умножения, что число элементарных операций T n , которые необходимо выполнить, чтобы умножить два n-разрядных числа, удовлетворяет оценке

bg

1+

.

bg

bg

Разница только в том, что мы брали A)(D C)значение в (1), а Каравместо этого брал АС коэффиципри главном члене на бесконечности.

Естественно, десятичную запись чисел можно разбивать не на три, а на большее число блоков. Проведем об-

T n c n1+ . Чтобы доказать теорему Тоома и построить алгоритм быстрого умно-

bg bg

10