Usuari:Aniolgarcia/Algorisme de Karatsuba

L'algorisme de Karatsuba és un procediment per multiplicar nombres grans de manera eficient, que va ser descobert per Anatoly Alexeevitch Karatsuba el 1960 i publicat per primer cop el 1962. L'algorisme aconsegueix reduir la multiplicació de dos nombres de $n$ dígits a com a màxim ${\displaystyle 3n^{\log _{2}3}\approx 3n^{1.585}}$ multiplicacions d'un sol dígit (i a exactament $n^{log_{2}3}$ multiplicacions quan $n$ és potència de 2). És, per tant, més ràpid que l'algorisme clàssic de multiplicació, que requereix $n^{2}$ productes d'un sol dígit. Per exemple, l'algorisme de Karatsuba necessita $3^{10}=59049$ multiplicacions d'un sol dígit per tal de multiplicar dos nombres de $1024$ dígits, mentre que l'algorisme clàssic n'utilitzaria $(2^{10})^{2}=1048576$.

L'algorisme de Karatsuba va ser el primer algorisme de multiplicació asimptòticament més ràpid que l'algorisme clàssic de multiplicació, que és de complexitat quadràtica. L'algorisme de Toom-Cook és una generalització més ràpida del de Karatsuba i, per a un $n$ suficientment gran, l'algorisme de Schönhage-Strassen és fins i tot més ràpid que l'algorisme de Karatsuba.

Història

El procediment estàndard per multiplicar dos nombres de n dígits requereix un nombre d'operacions elementals proporcional a $n^{2}$ o $\Theta (n^{2})$ en la Notació O gran. El 1952, Andrey Kolmogorov va intentar demostrar que l'algorisme clàssic era òptim asimptòticament, volent demostrar així que qualsevol algorisme per a aquesta tasca requeriria $\Omega (n^{2})$ operacions elementals.

A la tardor de 1960, Kolmogorov va organitzar un seminari sobre problemes matemàtics de cibernètica a la Universitat Estatal de Moscou, on va plantejar la seva suposició de $\Omega (n^{2})$ i altres problemes de complexitat computacional. En una setmana, Karatsuba, un estudiant de 25 anys, va trobar un algorisme de tipus "divideix i venceràs" que multiplicava dos nombres de n dígits en $\Theta (n^{\log _{2}3})$ operacions elementals, refutant així la suposició inicial de Kolmogorov. Kolmogorov es va sentir molt desil·lusionat per tal descobriment, i ho va fer públic en la seva següent i última trobada del seminari.

El mètode va ser publicat l'any 1962, a la revista científica soviètica Proceedings of the USSR Academy of Sciences. L'article havia estat escrit per Kolmogorov, possiblement en col·laboració amb Yuri Ofman, però nomenava a "A. Karatsuba i Yu. Ofman" com els autors. Karatsuba només es va adonar de la publicació quan va rebre una còpia de l'article per part de l'editorial de la revista.

Algorisme

El pas bàsic

El pas bàsic de l'algorisme de Karatsuba consisteix en una fòrmula que permet calcular el producte de dos nombres grans $x$ i $y$ usant tres multiplicacions de nombres més petits, cadascun amb més o menys la meitat dels dígits de $x$ o $y$, més algunes sumes i desplaçaments de dígits.

Suposem que $x$ i $y$ estan representats com a cadenes de $n$ dígits en alguna base $B$. Per a qualsevol enter positiu $m$ menor que $n$, un pot dividir els dos nombres donats de la manera següent:

$x=x_{1}B^{m}+x_{0}$

$y=y_{1}B^{m}+y_{0}$,

on $x_{0}$ i $y_{0}$ són menors que $B^{m}$. El producte és, llavors:

$xy=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})$

$xy=z_{2}B^{2m}+z_{1}B^{m}+z_{0}$,

on

$z_{2}=x_{1}y_{1}$

$z_{1}=x_{1}y_{0}+x_{0}y_{0}$

$z_{0}=x_{0}y_{0}$

Aquestes fòrmules requereixen quatre multiplicacions, i ja eren conegudes per Charles Babbage. Karatsuba va observar que es pot calcular $xy$ en tan sols tres multiplicacions, pel cost d'unes sumes addicionals. Si agafem $z_{0}$ i $z_{2}$ tal com abans, podem calcular

$z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}$

ja que

$z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-x_{1}y_{1}-x_{0}y_{0}$.

Una implementació més eficient de la multiplicació de Karatsuba és

$xy=(b^{2}+b)x_{1}y_{1}-b(x_{1}-x_{0})(y_{1}-y_{0})+(b+1)x_{0}y_{0}$, on $b=B^{m}$.

Exemple

Suposem que volem calcular el producte de 1234 i 5678. Triem la base 10 ($B=10$) i $m=2$. Aleshores tenim:

1234 = 12 × 10² + 34

5678 = 56 × 10² + 78

Només amb tres multiplicacions, que operen amb nombres més petits, serà possible calcular els tres resultats parcials:

z₂ = 12 × 56 = 672

z₀ = 34 × 78 = 2652

z₁ = (12 + 34)(56 + 78) − z₂− z₀ = 46 × 134 − 672 − 2652 = 2840

Ara tan sols cal tornar a unir els resultats parcials desplaçats correctament:

resultat = z₂×B^2m + z₁×B^m + z₀, en aquest cas

resultat = z₂ × 10^2x2 + z₁ × 10² + z₀

resultat = 672 × 10000 + 2840 × 100 + 2652 = 7006652

Aplicació recursiva

Si $n$ és quatre o major que quatre, les tres multiplicacions en del pas bàsic de Karatsuba suposen operands amb menys de $n$ dígits. Per tant, aquests productes poden ser calculats per crides recursives de l'algorisme de Karatsuba. La recursivitat pot ser aplicada fins que els nombres siguin tan petits que poden (o han de) ser calculats directament.

Anàlisi d'eficiència

El pas bàsic de Karatsuba funciona per a qualsevol base B i qualsevol m. Però pel teorema Master sabem que l'algorisme recursiu és més eficient quan m és igual a n/2, arrodonit per excés. En particular, si n és 2^k, per a un enter k, i la recursivitat para només quan n és 1, llavors el nombre de multiplicacions d'un sol dígit és 3^k, és a dir, n^c on c = log₂3.

Com que es pot ampliar qualsevol entrada amb dígits zero fins que la seva longitud sigui una potència de 2, el nombre de multiplicacions elementals, per a qualsevol n, és com a màxim $3^{\lceil log_{2}n\rceil }\leq 3n^{log_{2}3}$.

Com que les sumes, restes, i desplaçaments de dígits (multiplicacions per potències de B) en el pas bàsic de Karatsuba requereixen temps proporcionals a n, el seu cost es fa insignificant a mesura que creix n. Concretament, si t(n) denota el nombre total d'operacions elementals que l'algorisme realitza quan es multipliquen dos nombres de n dígits, llavors podem escriure:

$T(n)=3T(\lceil n/2\rceil )+cn+d$

per a algunes constants c i d. Per a aquesta relació de recurrència, pel teorema Master obtenim la cota superior asimptòtica $T(n)=\Theta (n^{log_{2}3})$.

Així, per a un n suficientment gran, l'algorisme de Karatsuba realitzarà menys desplaçaments i sumes d'un sol dígit que la multiplicació feta a mà, fins i tot quan el seu pas bàsic utilitzi més sumes i desplaçaments que la fórmula senzilla. No obstant això, per a valors petits que n, els desplaçaments i operacions de suma poden fer que l'algorisme sigui més lent que el mètode a mà. Tot depèn de la plataforma de l'ordinador i del context. Per norma general, Karatsuba sol ser més ràpid quan els factors són de l'ordre de 320-640 bits.