Умножение Карацубы - Описание метода

Интернет магазин китайских планшетных компьютеров

Компьютеры - Умножение Карацубы - Описание метода

22 января 2011

Оглавление:
1. Умножение Карацубы
2. Описание метода

Первый вариант

Этот вариант основан на формуле

= a + − a − b)x + bx.

Поскольку 4ab = −, то умножение двух чисел a и b эквивалентно по сложности выполнения возведению в квадрат.

Пусть X есть n-значное число, то есть

$X=e_0+2e_1+\ldots+2^{n-1}e_{n-1},$

где $e_j\in{0,\;1},\;j=0,\;1,\;\ldots,\;n-1$ .

Будем считать для простоты, что $n=2^m,\;m\geqslant 1;\;n=2k$ . Представляя X в виде

X = X₁ + 2X₂,

где

$X_1=e_0+2e_1+\ldots+2^{k-1}e_{k-1}$

$X_2=e_k+2e_{k+1}+\ldots+2^{k-1}e_{n-1},$

находим:

$X^2=^2=X_1^2+^2-)2^k+X_2^22^n.\qquad$

Числа X₁ и X₂ являются k-значными. Число X₁ + X₂ может иметь k + 1 знаков. В этом случае представим его в виде 2X₃ + X₄, где X₃ есть k-значное число, X₄ — однозначное число. Тогда

$^2=4X_3^2+4X_3X_4+X_4^2.$

Обозначим $\varphi$ — количество операций, достаточное для возведения n-значного числа в квадрат по формуле. Из следует, что для $\varphi$ справедливо неравенство:

$\varphi\leqslant 3\varphi+cn,\qquad$

где c > 0 есть абсолютная константа. Действительно, правая часть содержит сумму трёх квадратов k-значных чисел, k = n2 , которые для своего вычисления требуют $3\varphi=3\varphi$ операций. Все остальные вычисления в правой части, а именно умножение на $4,\;2^k,\;2^n$ , пять сложений и одно вычитание не более чем 2n-значных чисел требуют по порядку не более n операций. Отсюда следует. Применяя последовательно к

$\varphi,\;\varphi,\;\ldots,\;\varphi$

и принимая во внимание, что

$\varphi=\varphi=1,$

получаем

$\varphi\leqslant 3+cn2^{-1})+cn=3^2\varphi+3c+cn\leqslant\ldots\leqslant$

$\leqslant 3^m\varphi+3^{m-1}c+3^{m-2}c+\ldots+3c+cn=$

$=3^m+cn\left^{m-1}+\left^{m-2}+\ldots+\left+1\right)=$

$=3^m+2cn\left^m-1\right)<3^m=n^{\log_23}.$

Тем самым для количества $\varphi$ операций, достаточного для возведения n-значного числа в квадрат по формуле выполняется оценка:

$\varphi<n^{\log_23},\quad \log_23=1{,}5849\ldots$

Если же n не является степенью двух, то определяя целое число m неравенствами $2^{m-1}<n\leqslant 2^m$ , представим X как 2-значное число, то есть полагаем последние 2 − n знаков равными нулю:

$e_n=\ldots=e_{2^m-1}=0.$

Все остальные рассуждения остаются в силе и для $\varphi$ получается такая же верхняя оценка по порядку величины n.

Второй вариант

Это непосредственное умножение двух n-значных чисел, основанное на формуле

= ac + − ac − bd)x + bdx.

Пусть, как и раньше n = 2, n = 2k, A и B — два n-значных числа. Представляя A и B в виде

$A=A_1+2^kA_2,\quad B=B_1+2^kB_2,$

где $A_1,\;A_2,\;B_1,\;B_2$ — k-значные числа, находим:

$AB=A_1B_1+2^k-)+2^nA_2B_2.\qquad$

Таким образом, в этом случае формула заменяется формулой. Если теперь обозначить символом $\varphi$ количество операций, достаточное для умножения двух n-значных чисел по формуле, то для $\varphi$ выполняется неравенство, и, следовательно, справедливо неравенство:

$\varphi<n^{\log_23},\quad\log_23=1{,}5849\ldots$

Замечания

Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до n знаков функции y = x в некоторой точке x = x₁.

Если разбивать X не на два, а на большее количество слагаемых, то можно получать асимптотически лучшие оценки сложности вычисления произведения.

Метод умножения Шёнхаге — Штрассена имеет меньшую асимптотическую сложность, чем алгоритм Карацубы.

<<< Метод умножения Шёнхаге Штрассена

CBC-MAC >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие