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

Сложение и умножение
Рассмотрим простейший алгоритм сложения двух чисел столбиком. При применении этого алгоритма, например, к числам 1018 и 1105 когда требуется сложить тысячу восемнадцать и тысячу сто пять в десятичной системе на вход подается пара (1018, 1105) и мы поступаем так: 1 1018 + 1105 2123 Произведено шесть элементарных операций по сложению однозначных чисел: 8 + 5 = 13 (три пишем, один 'в уме'), 1 + 1 + 0 = 2, 0 + 1 = 1, и, наконец, 1 + 1 = 2. А меньше четырех и нельзя: ведь хоть по разу необходимо было употребить каждую цифру чисел. А теперь умножим друг на друга два числа (в десятичной системе): 1011 1101 1011 0000 1011 1011 1113111
Ч

Тем не менее, всего тридцать семь лет назад московским математиком Анатолием Александровичем Карацубой (тогда 25-летним молодым ассистентом, а ныне он профессор МГУ, известный специалист по теории чисел) было совершено открытие, которого трудно было ожидать. Он обнаружил метод, куда более эффективный, чем умножение в столбик!

суждать и так. Из нашего построения вытекает рекуррентное неравенство
T 2n 3T n + cn ,

bg

bg

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

T n ?n

bg

log2 3

.

Упражнение 2. Проведите соответствующие рассуждения аккуратно.

Метод Карацубы
Пусть х и у два 2n-значных десятичных числа:

x = x2

c

n -1

, K, x0 , y = y2

h

c

n -1

, K , y0 ,

h

xi , yi = 01, K9 . ,

Представим их в виде

Продемонстрируем метод Карацубы на примере умножения чисел, с которыми мы оперировали: 1101 1011. Воспользовавшись тождеством a1 - a0 b0 - b1 = a1b1 a0b0 + + a1b0 + a0b1 , представим четырехзначные числа А и В в виде А = = 10 2 a1 + a0 и В = 102 b1 + b0 , где a0 , a1 , b0 , b1 двузначные числа. Тогда

c

hc

h

x = 10n 1 + 0 , y = 10 n 1 + 0 , (i)
где i , i n-значные числа. Воспользовавшись тождеством

AB = 102 a1 + a0 102 b1 + b0 =

e

c

1 -

0

= 1 1 0 0 + 1 0 + 0 1 , (ii)
i bg

hc

0 - 1 =

h

+ 10 a1 - a0 b0 - b1

2

c

= 10 + 10 ab1 + 1

e

je

4

2

hc

j h + e10 + 1j
2

j

a0b0 .

получаем:

xy = 10 1 +
+ 10 1 -
n

e

n

Сколько операций мы совершили здесь? Элементарных умножений 4 Ч 4 = 16, и еще некоторое количество сложений. Из этого примера вытекает, что при умножении двух n-значных чисел столбиком нужно произве2 2 сти n элементарных умножений ( n раз заглянуть в таблицу умножения и заведомо не больше по порядку n2 раз произвести элементарные сложения.)
Упражнение 1. Покажите, что алгоритм деления в столбик n-значного числа на mзначное требует по порядку величины mn элементарных операций (не менее mn и не более 10mn).

А какова сложность процедуры умножения? Каково минимальное необходимое число элементарных операций? Умножение столбиком известно многие столетия, едва ли еще не со времени выхода в свет 'Алгебры' аль-Хорезми. Эта процедура, которую все изучали еще в начальных классах средней школы, выглядит как самый быстрый алгоритм: ведь каждая цифра одного числа должна вроде бы провзаимодействовать с каждой цифрой другого.
3 Квант ? 2

Мы свели задачу умножения 2n-разрядных чисел к трем операциям для n -разрядных чисел 1 1 , 1 - 0 0 - 1 , 0 0 и еще к операциям сложения и сдвига. На первый взгляд может показаться, что выигрыш по сравнению с обычным умножением незначителен только 3/4. Но ведь и сами nзначные числа мы будем умножать таким же образом! Поэтому множитель 3/4 будет возникать при каждом удвоении числа разрядов. И, например, при умножении 1024-значных чисел накопится более чем десятикратный выигрыш. Умножение Карацубы на n-значных числах будет эффективнее умножения в столбик по порядку величи-

c

= 10
0

e

0

2n

je10

n
n

hc

+ 10 1 1 +
n

0 - 1

j h + e10 + 1j

1 +

0

j

b iig
=

0 0 .

Видно, что достаточно произвести всего три умножения двузначных чисел a1 Ч b1 , a1 - a0 Ч b0 - b1 и a0 Ч b0 , на каждое из которых мы затратим не больше четырех элементарных умножений, т.е. всего мы затратим 12 умножений вместо 16 (и некоторое количество сложений). В нашем случае

c

hc

h

c

hc

h

a1 = 11 , a0 = 1 , b1 = 10 , b0 = 11 ,

откуда
1101 1011 =

= 10 11 + 1 10 10 + 11 = = 10 + 10

e

e

2

4

2

+ 10 + 1 1 11 = 111311 1.

e

j

je

2

11 10 + 10 10 1 +
2

2

j

j

Числа и многочлены
Первоначально метод Карацубы выглядел трюком. Но в следующем, 1963 году студент механико-математического факультета МГУ Андрей Тоом (он был участником первой международной математической олимпиады 1959 года, где получил третью премию) осознал природу этого метода и нашел его замечательное обобщение. В чем идея метода Карацубы и Тоома? Известно, что многие свойства чисел и многочленов очень похожи. Многие проблемы, связанные с уравнениями, сперва решались для многочленов. Посмотрим на десятич-

ны в C

порядка nlog2 3 n на число операk ций. В самом деле, пусть 2 < n < k -1 < 2 . Тогда T n число необходимых операций для умножения n-значных чисел оценивается по порядку

FG 3 IJ H 4K

log 2 n

раз. Это дает оценку
16 .

bg

как 3k = 2

ej

k log 2 3

n

log2 3

. Можно рас-

'