Multiplication Optimissée

[kangourex]

Bonjour, Bonsoir, je ne sais pas quel est le niveau de mon problème donc je l'ai posté dans le plus élevé.

Dans le cadre d'un projet informatique, je me dois d'être optimisé sur mes temps d’exécution. Je suis arrivé au moment ou je dois optimiser mon opération de multiplication.

J'ai fais des recherches tout de même ! La manière la plus optimisée serait : l'algorithme de Fürer. (lien ci dessous)

Je poste car les rares sources sur ce dernier ne se trouve que dans Wikipédia (à moins que :stupid_in ) Et j'avoue que pour comprendre de telle chose Wikipédia détaille peu les choses.

C'est pourquoi je vous demande si vous pouvez m'expliquer avec des termes adéquats l'algorithme de Fürer ainsi qu'en avoir un exemple.

Lien Wikipédia : http://fr.wikipedia.org/wiki/Algorithme_de_F%C3%BCrer

Je vous remercie du temps que vous consacrerez à mon sujet.

[sylvainc2]

La note 3 sur la page wiki dit que l'algo est avantageux pour des nombres de l'ordre de 2^(2^64), donc environ 2^(10^19) soit 2^(1000...000) avec 19 zéros à l'exposant. C'est très grand. Est-ce que tu dois vraiment l'utiliser par principe (parce qu'un prof l'impose, par exemple) ou est-ce qu'un autre algo, par exemple la transformée de Fourier rapide, ferait l'affaire?

[kangourex]

La note 3 sur la page wiki dit que l'algo est avantageux pour des nombres de l'ordre de 2^(2^64), donc environ 2^(10^19) soit 2^(1000...000) avec 19 zéros à l'exposant. C'est très grand. Est-ce que tu dois vraiment l'utiliser par principe (parce qu'un prof l'impose, par exemple) ou est-ce qu'un autre algo, par exemple la transformée de Fourier rapide, ferait l'affaire?

Bonsoir,

Je ne sais pas du tout si cet algo est vraiment adéquat j'ai juste vu la note "plus performant".
Sinon pour préciser un peu, je compte travailler avec des nombres comportant 100 à 300 chiffres environs cela dans le domaine du crypte, une simple multiplication met beaucoup de temps d'où l'idée d'un algorithme plus souple. Cela est un projet personnel, où mes profs m'aident un peu. Je vais jeter un coup d'oeil à la transformation de Fourier en attendant. :lol3:

[sylvainc2]

Des entiers de 300 chiffres, ce n'est pas très grand. La fft est efficace pour des milliers de chiffres et plus. Tu devrais peut-être regarder l'algo de Karatsuba à la place: http://en.wikipedia.org/wiki/Karatsuba_algorithm#Implementation

[kangourex]

//Serait- il possible de changer le nom de mon sujet en "Multiplication Optimisée" Merci

Des entiers de 300 chiffres, ce n'est pas très grand. La fft est efficace pour des milliers de chiffres et plus. Tu devrais peut-être regarder l'algo de Karatsuba à la place: http://en.wikipedia.org/wiki/Karatsuba_algorithm#Implementation

En effet j'avais déjà regardé cela, mais j'ai trouvé quelque erreur je m'explique (fin j'ai trouvé des erreurs sûrement que j'applique mal les choses)

Je vais prendre exemple du Wikipédia http://fr.wikipedia.org/wiki/Algorithme_de_Karatsuba

37 × 87 = 3219

D'après l'algorithme on : 3 * 7 = 21
8 * 7 = 56
(3-7)(8-7) = -4*1= -4
21*10^2*1 + (21+56+4)*10^1 + 56 = 2100 + 810 + 56 = 2966
Cela me donnerait 37 * 87 = 2966 grosse erreur :/ si vous pouvez me faire un petit corrigé de cette opération en mode détaillé si possible (comme j'ai fais) Et me faire une explication sur le choix des base j'ai crû comprendre que c'était :
NombreDeChiffre/ 2 = La base à prendre.

//Edit : Encore Merci à Sylvain pour tes réponses

[Ben314]

37 × 87 = 3219

D'après l'algorithme on : 3 * 7 = 21
8 * 7 = 56
(3-7)(8-7) = -4*1= -4
21*10^2*1 + (21+56+4)*10^1 + 56 = 2100 + 810 + 56 = 2966

a=3; b=7 ; c=8 ; d=7
ac = 3x8 = 24
bd = 7x7 = 49
(a-b)(c-d) = -4x1 = -4
37 x 87 = 24x100 + (24+49+4)*10 + 49 = 2400 + 770 + 49 = 3219

Même si l'algo utilise une "astuce" pour les dixaine, pour les centaines et les unités, t'a pas trop le choix : les centaines c'est le produit des deux dixaines et les unités, c'est le produit des 2 unités...
Tu peut aussi "vérifier" que le 24+49+4=77 des dixaines avec l'algo en question, c'est bien les même qu'avec l'algo qu'on apprend dans le primaire, c'est à dire 3x7+8x7=77.

[kangourex]

Même si l'algo utilise une "astuce" pour les dixaine, pour les centaines et les unités, t'a pas trop le choix : les centaines c'est le produit des deux dixaines et les unités, c'est le produit des 2 unités...
Tu peut aussi "vérifier" que le 24+49+4=77 des dixaines avec l'algo en question, c'est bien les même qu'avec l'algo qu'on apprend dans le primaire, c'est à dire 3x7+8x7=77.

Pour des petits nombres, c'est vrai que c'est le même et bien sûr si on reste dans le domaine des mathématiques purs. Mais quand on lie les mathématiques à l'informatique la multiplication reste un problème crucial. Et comme il est très bien dit : "Le calcul complet ne demande que 27 produits de deux chiffres au lieu de 64 par la méthode usuelle. Bien entendu, cette méthode, fastidieuse à la main, révèle toute sa puissance pour une machine devant effectuer le produit de grands nombres"et cette citation prend tout son sens quand on traite des grands nombres.

Merci de ta correction l'exemple donné sur Wikipedia m'a perturbé vu qu'il a présence de deux 2. :zen:

[Ben314]

J'ai du mal m'exprimer : je ne voulais pas du tout dire que l'algo était le même que celui du primaire.
Il donne le même résultat que l'algo "du primaire" pour les dizaine (çe qui te permet de vérifier si tu t'est pas gouré si tu fait "à la main") mais ne demande qu'une seule multiplication au lieu de 2 donc ça gagne gros si on l'utilise de façon récursive (on remplace un 4^p par un 3^p pour le même p...)

Concernant le choix de la base, effectivement, c'est le "diviser pour mieux régner" : tu as intérêt à scinder ton nombre binaire en 2 parties égales et à procéder de façon récursive pour optimiser le truc. (à mon avis, tu arrête la récursion lorsque tu arrive en dessous de la taille que sait gérer directement le copro. de calcul)