Multiplication rapide

[n.duhame]

Certains peut être connaissent l'algorithme de Karatsuba il tient en
une relation :
(a*10^k + b)(c*10^k + d) = ac*10^2k + (ac + bd – (a – b)(c – d))*10^k
+ bd

On fait ainsi seulement 3 multiplications au lieu de 4.
L'algorithme a ainsi une complexité en O(n^log_2(3)) = O(n^1,58)
L'algorithme est très bien et on peut l'améliorer encore en séparant
les nombres non pas en deux mais en trois, quatres parties et même
plus.

Donc j'essaie de trouver une relation dans le même genre que celle de
l'algorithme de karatsuba mais en séparant les nombres en trois
parties.

J'ai réussi à trouver une relation avec seulement 6 multiplications :
(a*10^2k + b*10^k + c)(d*10^2k + e*10^k + f) = ad*10^4k + ( (a+b)(d+e)
- ad - be )*10^3k + ( (a+c)(d+f) - ad - cf - be)*10^2k + ( (b+c)(f+e)
- be - cf )*10^k + cf

Seulement j'ai une complexité en O(n^log_3(6)) = O(n^1.63) qui est
moins bien que l'algorithme de karatsuba.
Donc il faudrait arriver à écrire une relation avec seulement 5
multiplications.

Je pense qu'une des multiplications est (a - b - c)(f - e - d) mais ce
n'est qu'une supposition de même je pense qu'il y a aussi les 2 autres
multiplications ad et cf.

[zwim]

Le Sat, 14 Nov 2009 14:12:50 -0800 (PST)
n.duhame a �crit
>Certains peut �tre connaissent l'algorithme de Karatsuba il tient en

>une relation :
>(a*10^k + b)(c*10^k + d) = ac*10^2k + (ac + bd � (a � b)(c � d))*10^k
>+ bd
>
>On fait ainsi seulement 3 multiplications au lieu de 4.

>L'algorithme a ainsi une complexit� en O(n^log_2(3)) = O(n^1,58)
>L'algorithme est tr�s bien et on peut l'am�liorer encore en s�parant
>les nombres non pas en deux mais en trois, quatres parties et m�me
>plus.
>
>Donc j'essaie de trouver une relation dans le m�me genre que celle de
>l'algorithme de karatsuba mais en s�parant les nombres en trois
>parties.
>
>J'ai r�ussi � trouver une relation avec seulement 6 multiplications :

>(a*10^2k + b*10^k + c)(d*10^2k + e*10^k + f) = ad*10^4k + ( (a+b)(d+e)
>- ad - be )*10^3k + ( (a+c)(d+f) - ad - cf - be)*10^2k + ( (b+c)(f+e)
>- be - cf )*10^k + cf
>

>Seulement j'ai une complexit� en O(n^log_3(6)) = O(n^1.63) qui est

>moins bien que l'algorithme de karatsuba.

>Donc il faudrait arriver � �crire une relation avec seulement 5

>multiplications.
>
>Je pense qu'une des multiplications est (a - b - c)(f - e - d) mais ce

>n'est qu'une supposition de m�me je pense qu'il y a aussi les 2 autres
>multiplications ad et cf.

A priori tu as besoin de calculer au moins les 3 produits sym�triques

M1 = ad
M2 = be
M3 = cf

Et il te reste � obtenir 3 coeffcients � partir de l�

ae+bd
af+be+cd
bf+ce

donc 6 multiplications paraissent n�cessaires.

Une l�g�re variation possible par rapport � ce que tu as :

M4 = (a+b)(d+e)
M5 = (b+c)(e+f)
M6 = (a+b+c)(d+e+f)

10^4k ( M1 )
10^3k ( M4 - M2 - M1 )
10^2k ( M6 + M2 + M2 - M4 - M5 )
10^1k ( M5 - M3 - M2 )
10^0k ( M3 )

Mais l'une comme l'autre peuvent faire apparaitre des d�bordements
arithm�thiques.

Dans la version de Karatsuba le terme ad+bc peut s'obtenir de deux
fa�ons diff�rentes :

ad+bc = (a+b)(c+d) - ac - bd
ad+bc = ac + bd - (a-b)(c-d)

La seconde forme est pr�f�rable car a-b et c-d restent en valeur
absolue < 10^k et leur produit < 10^2k
Tandis que (a+b)(c+d) peut aller jusqu'� 4.10^2k et provoquer un
d�bordement arithm�tique.

C'est pourquoi il est plus judicieux d'avoir :

M4 = (a - b)(d - e)
M5 = (b - c)(e - f)
M6 = (a - c)(d - f)

10^4k ( M1 )
10^3k ( M1 + M2 - M4 )
10^2k ( M1 + M2 + M3 - M6 )
10^1k ( M2 + M3 - M5 )
10^0k ( M3 )

--
zwim.
Rien n'est impossible que la mesure de la volont� humaine...