Szorzás másként?

Ezek szerint nincs itt okos ember?:)Én fejben szorzok mindig!Midig kerekítve szorozz és a maradékot kivonod!Ez a leggyorsabb!Pl 123X123=15129

120X120=14400

6X120=720+14400=15120

3x3=X+15120:)

Vagy így bonyolultabb?Én így játszom le.

A Karatsuba algoritmus aszimptotikusan hatékonyabb.

[link]

Például 1234 * 6543 akarod kiszámítani. Ez felírható (12*10^2+34)*(65*10^2+43) alakban is.

Legyen:

a2=12*65=780,

a0=34*43=1462,

a1=(12+34)*(65+43)-a2-a0=4968-780-1462=2726.

Ezt követően az eredmény a2*10^4+a1*10^2+a0=780*10000+2726*100+1462=7948926.

A 2 négy jegyű szám szorzásához 3 két jegyű szám szorzására volt szükség és eltoláshoz(10 hatvánnyal szorzás) összeadás és kivonás, általában kettes számrendszerben végzik, tehát az eltolás 2 hatvánnyal szorzás. A futási ideje a két n-bites szám esetén: 3*n^1.585, ez gyorsabb az iskolában tanult algoritmusnál, az négyzetes n függvényében. Vannak ennél is aszimptotikusan hatékonyabb algoritmusok, pl. Toom–Cook, Schönhage–Strassen, ez a linknél megtalálható.

Egyszer találtam egy könyvet, érdemes olvasgatni:

[link]