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) |