Schönhage-Strassen : explications ?

[mivan]

Bonjour à tous,

Je dois implémenter une méthode de calcul de Schönhage-Strassen.
Mon soucis, c'est que je ne suis pas mathématicien et que tout ce que
je lis est assez flou pour moi.

J'ai bien compris la méthode pour des nombres à 2 chiffres. On a n=2
ce qui donne 2n - 1 = 3

45 * 23 = 4 * 2 / 4*3+2*5 / 3*5
Ce qui donne : 08 22 15
On garde le 5
On ajoute le 1 au 2 -> 3
On ajoute le 2 au 8 -> 10
Soit 1035

Maintenant, pour des nombres à 3 chiffre, je ne vois pas :
453 * 861 (n=3 --> 2n-1 = 5)
Avec la méthode de découpage, on obtient : 32 / 64 / 30 / 23 / 03
390 033
On garde le 3 à droite
0 + 3 = 3 -> j'ai obtenu les 2 derniers chiffres....
je trouve pas comment calculer le reste.

Si quelqu'un s'y connait et voudrait bien me donner un petit coup
de main. Merci beaucoup d'avance.

Vinko

[Doraki]

Ton 30 au milieu est faux.
4*1+5*6+3*8 = 4+30+24 = 58

[mivan]

Ahh ! OK, il faut croiser les paires 2 à 2.

Donc, j'obtiens :

32 64 58 23 03

Je garde le dernier 3
-> J'additionne le 0 et le 3 = 3
-> J'additionne le 2 et le 8 = 0 (et je garde le 1 de la retenue)
-> Je prends le 5 + 1 (de la retenue) que j'ajoute à 4 = 0 (je garde le 1)
-> Ensuite 2 + 6 + 1 = 9
-> Et le 3

--> 390 033

Merci pour cet aiguillage !

VinkoB

[Ben314]

Salut,
Je doit être un peu con, mais je fait pas bien la différence entre la "Méthode de Schönhage-Strassen" et... la méthode qu'on m'a apris dans le primaire... :cry:

[mivan]

C'est une question de rapidité d'exécution.

Je t'explique à ma façon, en français :
453 * 861 = 390 033

Ligne 1
1 * 3
1 * 5
1 * 4
Ligne 2 (décalage de 10)
6 * 3 = 18 -> pose 8 / retient 1
6 * 5 = 30 -> j'ajoute la retenue : 31 -> pose 1 / retient 3
6 * 4 = 24 -> j'ajoute la retenue : 27
Ligne 3 (décalage de 100)
8 * 3 = 24 -> pose 4 / retient 2
8 * 5 = 40 -> j'ajoute la retenue : 42 -> pose 2 / retient 4
8 * 4 = 32 -> j'ajoute la retenue : 36

J'obtiens
453
+ 27180
+362400

Recalcul : 3 + 0 + 0 = 3
5 + 8 + 0 = 13 -> pose 3 / retient 1
4+1+4 = 9 / 9 +1 = 10 je pose 0 et retiens 1
7+2 = 9 -> 9+1 = 10 -> pose 0 retient 1
2+6 = 6 -> 8+1 = 9
3

3 9 0 0 3 3

J'ai fait plein d'opérations

Avec S-S, c'est plus rapide :
453
*861

4 * 8 = 32
4 * 6 + 8 * 5 = 64
4 * 1 + 5 * 6 + 8 * 3 = 58
5 * 1 + 6 * 3 = 23
3 * 1 = 03

32 64 58 23 03

Ensuite, tu garde le dernier chiffre de droite et tu cumules les 2 d'avant :
3
0 + 3 = 3
2 + 8 = 10 -> pose 0 / garde 1
5 + 4 (+1) = 10 -> pose 0 / garde 1
6 + 2 (+1) = 9
3

3 9 0 0 3 3

Certes, c'est pas super flagrant sur des 3 * 3 mais essaye avec 6 * 6 et c'est
déjà plus visible.

J'espère que ma démonstration a été assez claire.

VinkoB

[Ben314]

Bon, on va dire que je ne suis que trés moyennement convaincu :
On fait trés exactement les mêmes multiplications dans les deux cas et la seule différence réside dans l'ordre dans lesquelles on fait les additions : il y a peut-être légèrement moins de retenues (dans les additions) avec la deuxième façon de faire la somme, mais ça me parrait pas totalement évident.
Par exemple dans ton calcul de :
4 * 1 + 5 * 6 + 8 * 3 = 58
tu ne détaille pas les retenues nécessaires à faire cette addition alors que dans la méthode "primaire" tu as détaillé tout les calculs de retenue.

[Ben314]

Il me semble que, dans tout les cas, on fait ces calculs là :

et que la seule différence réside dans l'ordre dans lequel on ajoute les différentes colonnes :
La méthode "primaire" consiste à calculer les "sous totaux" entre chaque traits alors que la "Méthode machin-chose" consiste à ajouter toute la colonne d'un coup : je vois vraiment pas de preuve que cela permet forcément de limiter le nombre de retenues dans les additions et vu que c'est la seule différence (dans tout les cas, on ajoute autant de nombres qui sont d'ailleurs... les mêmes...)

[mivan]

Bonjour,

Je comprends bien que la méthode ne parait pas très rapide
quand on maîtrise parfaitement la bonne vieille méthode dite
"scolaire".

http://fr.wikipedia.org/wiki/Algorithme_de_multiplication

Les méthodes dites 'rapides' permettent d'économiser des
calculs mais la différence ne se fait vraiment sentir que sur
les très grosses opérations.

Celà dit, toutes les méthodes ont un point commun non
négligeable : il faut connaître ses tables de multiplication....

[Ben314]

Les méthodes dites 'rapides' permettent d'économiser des
calculs mais la différence ne se fait vraiment sentir que sur
les très grosses opérations.

Calcule moi donc juste pour voir combien de multiplications et d'adittion demandent ta méthode lorsque l'on fait le produit de deux nombres de 500 chiffres.
Compare ensuite avec la méthode "primaire".
Conclusion.

[Doraki]

J'ajouterais que ce que t'es en train de faire c'est absolument pas l'algorithme de Schönhage Strassen

[mivan]

Oh oh ! Je ne suis pas mathématicien. Juste curieux.
Et c'est pas moi qui dit que c'est plus rapide, ce sont les
vrais mathématiciens. Y'a d'autres méthode qui sont aussi
très rapides (Karatsuba / Toom par exemple).

VinkoB

[mivan]

J'ajouterais que ce que t'es en train de faire c'est absolument pas l'algorithme de Schönhage Strassen

C'est quoi alors ce que je fais ? Il me semblait bien pourtant ? Tu peux expliquer facilement ?

Merci,

VinkoB

[Doraki]

[url]http://en.wikipedia.org/wiki/Schönhage–Strassen_algorithm[/url]

[mivan]

Bonjour Doraki,

J'avais bien vu cette explication mais j'avais trouvé une video qui
faisait ce que j'expliquais ici (mais avec 2 x 2) :

[url]http://wn.com/Schönhage-Strassen_algorithm[/url]

Tu peux m'expliquer clairement les étapes de la multiplication avec
par exemple 789 * 654 ?

Merci d'avance,

[Doraki]

Cette vidéo, si tu regardes sa description, n'a aucun rapport avec Schonage Strassen.

L'algorithme m'a l'air d'etre expliqué sur wikipedia.
Je ne l'ai jamais regardé en détail je peux pas t'aider plus que ça.

[mivan]

Ok, je vais me pencher là dessus. Je vais essayer de trouver
une bibliothèque avec du code source, ce qui est plus parlant
pour moi que des théories mathématiques.

Encore merci,