5 de juliol de 2012

Una multiplicació més "ràpida": l'algoritme de Karatsuba

L'algoritme de la multiplicació ha variat força al llarg del temps. Però en la majoria d'algoritmes que s'han fet servir el que no canvia és la quantitat de subproductes que hem de fer. Per exemple, si multipliquem 45 · 738 farem 6 subproductes:

4·700      4·30     4·8     5·700     5·30     5·8

Com que les sumes són més fàcils no les comptem i, considerant que en realitat cada subproducte és realment de nombres d'una xifra, diem que el cost d'aquesta multiplicació és 6. Si multipliquem un nombre de 15 xifres per un altre de 23 el cost serà de 15·23 = 345 subproductes. En general es considera que el cost de l'algorisme tradicional de la multiplicació és de n2.

El que és curiós és que el problema de trobar una algoritme millor es continués estudiant i que, a mitjans del segle XX, s'inventés un altre amb un cost menor, de forma que, per exemple, una multiplicació de dos nombres de 1000 xifres, que amb els mètodes normals requereix 1 000 000 subproductes, es pugui resoldre amb poc menys de 60 000.

Quan veiem l'algorisme per primera vegada ens sembla estrany, però en realitat no ho és tant. El va inventar Anatoli Karatsuba a l'any 1962. El mètode demostra tota la seva potència amb nombres molt grans i està pensat per fer els càlculs amb ordinador. Tot i així li podem fer una ullada i podem provar el seu funcionament amb nombres més petits.

Anatoli Karatsuba
(1937-2008)
Mirem l'algorisme de Karatsuba?