Algoritmo de Karatsuba
Assenálio ou Método de Multiplicação de Karatsuba é um método utilizado para multiplicar números grandes eficientemente, descoberto por Anatolii Alexeievitch Karatsuba em 1960; e publicado em 1962. Este algoritmo reduz a multiplicação de dois números de dígitos a no máximo: multiplicações de dígitos simples e a exatamente quando é uma potência de 2.
A demonstração será feita por fórmulas. Seja a igualdade: ( a + b x ) 2 = a 2 + ( ( a + b ) 2 − a 2 − b 2 ) x + b 2 x 2 . {\displaystyle (a+bx)^{2}=a^{2}+((a+b)^{2}-a^{2}-b^{2})x+b^{2}x^{2}.} Desde que 4 a b = ( a + b ) 2 − ( a − b ) 2 {\displaystyle 4ab=(a+b)^{2}-(a-b)^{2}} , a multiplicação dos números a {\displaystyle a} e b {\displaystyle b} possui desempenho equivalente à ordem quadrática. Seja X {\displaystyle X} um número de n {\displaystyle n} dígitos, que é igual a onde e j ∈ 0 , 1 , j = 0 , 1 , … , n − 1 {\displaystyle e_{j}\in {0,\;1},\;j=0,\;1,\;\ldots ,\;n-1} . Assume-se por simplicidade que n = 2 m , m ⩾ 1 ; n = 2 k {\displaystyle n=2^{m},\;m\geqslant 1;\;n=2k} . Escrevendo-se X {\displaystyle X} como então calculando X 2 {\displaystyle X^{2}} , fica como X 1 {\displaystyle X_{1}} e X 2 {\displaystyle X_{2}} possuem k {\displaystyle k} dígitos. X 1 + X 2 {\displaystyle X_{1}+X_{2}} podem ter no máximo até k + 1 {\displaystyle k+1} dígitos. Neste caso, serão representados como 2 X 3 + X 4 {\displaystyle 2X_{3}+X_{4}} , onde X 3 {\displaystyle X_{3}} é um número de k {\displaystyle k} dígitos e X 4 {\displaystyle X_{4}} é um número de um único dígito. Então
