Le merveilleux algorithme de Schonhage et Strassen pour la multiplication rapide de polynômes s'effectue en n.log(log log n).
C'est vraiment la classe mais....
 
A QUOI IL SERT, CET ALGORITHME ??!!    
 
Si quelqu'un connaissait des aplications concrètes de ce truc là ça me serait bien utile...

 
traitmeent du signal
 
Tu écoute des MP3 ? Et bien voila un bel exemple de traitement du signal dans la vie de tous les jours.
Tu vois sur ton logiciel de lecture l'affichage de l'équaliseur graphique avec les barres suivant la fréquence ? C'est calculé par une FFT

On a besoin de faire des multiplications pour ça ?
 
En fait je parlais de l'algo de multiplication de Schonhage et Strassen qui utilise la FFT ( tu sais, celui qui est immonde, avec le corps des classes d'équivalences de polynômes modulo X^m + 1 ).
 
Ce que je me demandais c'est à quelle occasion on était amené à multiplier des trucs très grands...

essaie d'écrire un algo pour convertir une chaine hexadécimale de longueur arbitraire en chaine décimale.
Tu vas vite comprendre.
 
Sinon pour la cryptographie, ou le traitement du signal.

Pour la traitement du signal tu dois multiplier ? ça marche comment, j'y connais rien à tout ça...

 
wouahahahaha
(pas mechant)
 
Non, le traitement du signal est une matiere tellemnt vaste que l'expliquer ici prendrait des heure (j'en ai mange pendant deux ans!!!)
Disons que pour analiser un signal (tu a par exemple un son et tu veux savoir quel "sons" le compose - en gros, un son a 30 Hz, un a 256 Hz, un a 8542 Hz, etc...- ), tu devra calculer la transformee de fourrier.
 
Pour se faire, La theorei est geniale mais pas applicable en pratique (calculs sur un temps infini et une bande de frequence infinie).
 
On utilise alors des artefact pour calculer des "pseudo-transformee de fourrier (proches de la realite).
 
La FFT (ou Fast Fourier Tranform) permet de calculer cette transformee de maniere assee rapide.
 
Mais ceci n'est qu'un exemple d'application...

On utilise aussi la FFT pour la multiplication de grands nombres (plusieurs millions de chiffres), en théorie des nombres.
 
Voir www.mersenne.org pour lequel a été développé un logiciel de calcul utilisant la FFT dans la recherche de nouveuax nombres premiers (l'utilisation des algorithmes de multplication classique en O(n^2) aurait rendu cette recherche impossible !)

le bon vieux Schonhage-Strassen, ça me rappelle des souvenirs de mes cours d'arithmétique des ordinateurs. Très utile en effet en traitement du signal, mais surtout en cryptographie. Il faut vraiment des nombres d'une taille colossale pour être gagnant par rapport à un Karatsuba (oui la complexité est un comportement asymptotique...). Mon prof de l'époque m'avait parler d'application dans la multiplication de matrice de très grande taille.