Множення Карацуби

Цей варіант заснований на формулі

${\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({\frac {3}{2}}\right)^{m-1}+\left({\frac {3}{2}}\right)^{m-2}+\ldots +\left({\frac {3}{2}}\right)+1\right)=}$

${\displaystyle =3^{m}+2cn\left(\left({\frac {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+((a+b)(c+d)-ac-bd)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},\ quadB=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}((A_{1}+A_{2})(B_{1}+B_{2})-(A_{1}B_{1}+A_{2}B_{2}))+2^{n}A_{2}B_{2}.\quad (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 }$

Перемножимо 648*356.

Перший множник подамо як 6*100+48 Другий множник подамо як 3*100+56 За формулою Карацуби x*y= (x1*B^m+x0)*(y1*B^m+y0)=x1*y1*B^2m+Z1*B^m+x0*y0,

де Z1=(x1+x0)*(y1+y0)-x1*y1-x0*y0, маємо: 648*356=(6*100+48)*(3*100+56)=6*3*100^2+Z1*100+48*56. Тут Z1 = (6+48)*(3+56)- 6*3 - 48*56=3186-18-2688=580.

В цілому, 6*3*100^2+Z1*100+48*56 = 180 000+580*100+2 688 = 230 688. З прикладу виплаває два висновки: 1) при обрахунку Z1 можна знову застосувати формулу Карацуби до чисел 54*59 та 48*56. Тобто, маємо рекурсію. 2) Оскільки ЕОМ оперують двійковими числами B =2 при обрахунку машиною.

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

Якщо розбивати ${\displaystyle X}$ не на два, а на більшу кількість доданків, то можна отримувати асимптотично кращі оцінки складності обчислення добутку (піднесення до квадрату). Зокрема, такий шлях застосовано в алгоритмі Тоома — Кука.

Метод множення Шенхаге — Штрассена має меншу асимптотичну складність, ніж алгоритм Карацуби, однак на практиці він має перевагу лише для великих значень n.