effectivement autant pour moi, je trouve un autre exemple alors :D
Je crois que la multiplcation par karatsuba et fft correspondent bien à ca.
karatsuba = en n^2 (un peu plus rapide que l'algo naif qui est aussi en n^2)
fft = en n log(n) (de tete).
Quand j'avais demandé a mon prof si il fallait pas mieux qu'on implémente les multiplications par fft (je connais juste de nom) ils nous a dis que non, car sur les nombres sur lesquels on travaillait (clé rsa classique) le coefficient du n log(n) était tellement important que ca mettait plus de temps.
[^] # Re: Plop !
Posté par briaeros007 . En réponse au journal "L'informatique Paradoxale". Évalué à 2.
Je crois que la multiplcation par karatsuba et fft correspondent bien à ca.
karatsuba = en n^2 (un peu plus rapide que l'algo naif qui est aussi en n^2)
fft = en n log(n) (de tete).
Quand j'avais demandé a mon prof si il fallait pas mieux qu'on implémente les multiplications par fft (je connais juste de nom) ils nous a dis que non, car sur les nombres sur lesquels on travaillait (clé rsa classique) le coefficient du n log(n) était tellement important que ca mettait plus de temps.