Répondre à la discussion
Affichage des résultats 1 à 16 sur 16

FFT et multiplication



  1. #1
    Pole

    FFT et multiplication


    ------

    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.

    -----

  2. #2
    Quinto

    Re : FFT et multiplication

    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+

  3. #3
    g_h

    Re : FFT et multiplication

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

  4. #4
    Quinto

    Re : FFT et multiplication

    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)

  5. A voir en vidéo sur Futura
  6. #5
    Pole

    Re : FFT et multiplication

    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.

  7. #6
    Pole

    Re : FFT et multiplication

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

  8. #7
    Lord

    Re : FFT et multiplication

    J'ai fait un exposé dessus y a 6 mois ... Voici les notes (en format doc) si tu veux !
    Suis-je Amour le Phébus, Lusignon ou Biron ?

  9. #8
    Pole

    Re : FFT et multiplication

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

    A plus

  10. #9
    Pole

    Re : FFT et multiplication

    J'ai éxécuter l'algorithme :
    u=12
    v=17
    n=4
    8<=22*3<16
    k=2 l=3
    K=4 L=8
    u=(12,0,0,0)8
    v=(17,0,0,0)8
    2k+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)?

  11. #10
    cricri

    Re : FFT et multiplication

    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

  12. #11
    Pole

    Re : FFT et multiplication

    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?

  13. #12
    cricri

    Re : FFT et multiplication

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

  14. #13
    cricri

    Re : FFT et multiplication

    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

  15. #14
    Pole

    Re : FFT et multiplication

    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!!!!!!!!!!!!!!!

  16. #15
    Pole

    Re : FFT et multiplication

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

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

  17. #16
    cricri

    Re : FFT et multiplication

    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

Discussions similaires

  1. FFT reelle
    Par Julieng31 dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 03/12/2008, 10h48
  2. analyseur FFT
    Par ABN84 dans le forum Électronique
    Réponses: 3
    Dernier message: 10/09/2007, 18h02
  3. l'application de la fft
    Par atrasse dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 25/07/2007, 11h41
  4. Fft
    Par philvl dans le forum Électronique
    Réponses: 2
    Dernier message: 09/03/2007, 22h20
  5. Fft
    Par Ravaner dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 15/03/2006, 14h49