WikiSort.ru - Не сортированное

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

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

${\displaystyle (a+bx)^{2}=a^{2}+((a+b)^{2}-a^{2}-b^{2})x+b^{2}x^{2}.}$

Поскольку ${\displaystyle 4ab=(a+b)^{2}-(a-b)^{2}}$ , то умножение двух чисел ${\displaystyle a}$ и ${\displaystyle b}$ эквивалентно по сложности выполнения возведению в квадрат.

Пусть ${\displaystyle X}$ есть ${\displaystyle n}$ -значное число, то есть

${\displaystyle X=e_{0}+2e_{1}+\ldots +2^{n-1}e_{n-1},}$

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

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

${\displaystyle X=X_{1}+2^{k}X_{2},}$

где

${\displaystyle X_{1}=e_{0}+2e_{1}+\ldots +2^{k-1}e_{k-1}}$

и

${\displaystyle X_{2}=e_{k}+2e_{k+1}+\ldots +2^{k-1}e_{n-1},}$

находим:

${\displaystyle X^{2}=(X_{1}+2^{k}X_{2})^{2}=X_{1}^{2}+((X_{1}+X_{2})^{2}-(X_{1}^{2}+X_{2}^{2}))2^{k}+X_{2}^{2}2^{n}.\qquad (1)}$

Числа ${\displaystyle X_{1}}$ и ${\displaystyle X_{2}}$ являются ${\displaystyle k}$ -значными. Число ${\displaystyle X_{1}+X_{2}}$ может иметь ${\displaystyle k+1}$ знаков. В этом случае представим его в виде ${\displaystyle 2X_{3}+X_{4}}$ , где ${\displaystyle X_{3}}$ есть ${\displaystyle k}$ -значное число, ${\displaystyle X_{4}}$  — однозначное число. Тогда

${\displaystyle (X_{1}+X_{2})^{2}=4X_{3}^{2}+4X_{3}X_{4}+X_{4}^{2}.}$

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

${\displaystyle \varphi (n)\leqslant 3\varphi (n2^{-1})+cn,\qquad (2)}$

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

${\displaystyle \varphi (n2^{-1}),\;\varphi (n2^{-2}),\;\ldots ,\;\varphi (n2^{-m+1})}$

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

${\displaystyle \varphi (n2^{-m})=\varphi (1)=1,}$

получаем

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

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

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

${\displaystyle =3^{m}+2cn\left(\left({\tfrac {3}{2}}\right)^{m}-1\right)<3^{m}(2c+1)=(2c+1)n^{\log _{2}3}.}$

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

${\displaystyle \varphi (n)<(2c+1)n^{\log _{2}3},\quad \log _{2}3=1{,}5849\ldots }$

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

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

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

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

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

${\displaystyle (a+bx)(c+dx)=ac+{\Big (}(a+b)(c+d)-ac-bd{\Big )}x+bdx^{2}.}$

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

${\displaystyle A=A_{1}+2^{k}A_{2},\quad B=B_{1}+2^{k}B_{2},}$

где ${\displaystyle A_{1},\;A_{2},\;B_{1},\;B_{2}}$  — ${\displaystyle k}$ -значные числа, находим:

${\displaystyle AB=A_{1}B_{1}+2^{k}{\Big (}(A_{1}+A_{2})(B_{1}+B_{2})-(A_{1}B_{1}+A_{2}B_{2}){\Big )}+2^{n}A_{2}B_{2}.\qquad (3)}$

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

${\displaystyle \varphi (n)<(2c+1)n^{\log _{2}3},\quad \log _{2}3=1{,}5849\ldots }$

Замечания

Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до ${\displaystyle n}$ знаков функции ${\displaystyle y=x^{2}}$ в некоторой точке ${\displaystyle x=x_{1}}$ .

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

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