FFT et multiplication

[invite3d7be5ae]

Bonjour,
il paraît que l'on peut faire des multiplication très rapidement avec la FFT.Est-ce qu'on peut me l'expliquer? (J'aimerais la programmer!)


P.S. : Je sais, ce n'est pas de mon âge.

[inviteab2b41c6]

Ca va être très difficile à t'expliquer.
L'idée est de considérer deux nombre , mettons 1278 et 2589 comme un polynôme.
On sait multiplier des polynômes très rapidement avec la transformée rapide de Fourier, et en fait on remarque que 1278 2589 sont des polynômes si on les écrit ainsi
1278->x^3+2x²+7x+8
2589->2x^3+5x²+8x+9

On fait la multiplication des 2 polynômes, on en trouve un troisième, et il correspond à la multiplication de nos deux nombres. Pour celà il suffit en effet de poser x=10.

Je sais que ca ne répond pas entièrement à ta question, mais une réponse claire va être trop compliquée, et trop longue.
A+

[invite97a92052]

Je ne vois pas ce qu'il y a de "très rapide" dans cette méthode !

[inviteab2b41c6]

Ce qu'il y'a de très rapide c'est que le produit est en log de base 2 si mes souvenirs sont bons.(vagues souvenirs)

[A voir en vidéo sur Futura]

[invite3d7be5ae]

Presque Quinto, c'est en L*ln(L)*ln(ln(L))) (c'est quasiment linéaire) où L est la taille du plus grand nombre. (pour la multiplication que qu'on à appris, c'est en L^2)
Tu ne m'expliques pas comment on multiplie rapidement ces deux polynômes. Il y a une autre méthode, celle de Karatsuba qui est en L^(ln(3)/ln(2)) c'est à dire environ L^1.32.

[invite3d7be5ae]

Pourrais tu m'expliquer la FFT sur le polynômes?

[invitec7b3f097]

J'ai fait un exposé dessus y a 6 mois ... Voici les notes (en format doc) si tu veux !

[invite3d7be5ae]

Lord, tu peux donner un exemple (avec des nombres petits genre 12 et 17)?

A plus

[invite3d7be5ae]

J'ai éxécuter l'algorithme :
u=12
v=17
n=4
8<=2²*3<16
k=2 l=3
K=4 L=8
u=(12,0,0,0)₈
v=(17,0,0,0)₈
2_k+l=32
u=(0.375,0,0,0)
v=(0.53125,0,0,0)
û=(0.375, 0.375, 0.375, 0.375)
v~=(0.53125, 0.53125, 0.53125, 0.53125)
w~=(0.53125*0.375,idem,idem,id em)=
(0.19921875,idem,idem,idem)
w=(0.796875,idem, idem,idem)
W=(816,idem,idem,idem)
W(L)=59568

Alors Lord, où je me suis trompé?
Où alors if faut diviser 59568 par 292, mais comment on trouve le 292 (autrement qu'en calculant 12*17)?

[invitedebe236f]

tu a excell pole ?
je te metrais un lien avec exemple et meme source de programme si tu veux

et je rajouterai la hartley tranformation plus rapide que fourier

[invite3d7be5ae]

Oui cricri j'ai Excel. Allez envoi vite : tu me fais jubiler.
Et pour ma "multiplication" où est le problème?
Tu ne peux pas me l'indiquer?