FFT et multiplication

[Pole]

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.

[Quinto]

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+

[g_h]

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

[Quinto]

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)

[Pole]

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.

[Pole]

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

[Lord]

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

[Pole]

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

A plus

[Pole]

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)?

[cricri]

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

[Pole]

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?

[cricri]

snif j ai oublier hier soir promi ce soit j y pense

[cricri]

et voila
ca semble hyper complique et long a calculer mais pour des nombres avec des centaine de millier de chiffre c est hyper efficace

je t ai mit 2 exemple 1234*4789
et 12345678*87654321

comme ca tu vois que chaque fois qu on x2 par le nombre de chiffre
il suffit d une etape de plus sur 2x plus de nombre donc que la methode est quasi lineaire

http://craftac2.free.fr/a2.xls

[Pole]

C'est quoi cette règle? Elle ressemble à :
-mettre dans un ordre bizarre (Il faudrait que tu m'expliques)
-rajouter des zéros entre chaque chiffre.

Ca à l'air de prendre énormément de place!!!!!!!!!!!!!!!

[Pole]

on divise par 8 vu qu on a fait une fft 8

8? C'est la somme des chiffres des deux nombres?

[cricri]

la regle est asser simple faut ecrire en binaire
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7

puis inverser la on a 3 bit ca donne
000 0
100 4
010 2
110 6
001 1
101 5
011 3
111 7

sur 2 bit
00 00
01 10
10 01
11 11

ca c est pour une fft 8 une 16 c est sur 4 bit etc
oui ca prend de la place en memoire mais on est pas obliger de metre 1 chiffre par case on peut aller jusqua 3 sans probleme juqua 1 million de case