Discussion :

[progfou]

Salut !
J'ai ouvert un nouveau topic, car c'est indépendant de la fft

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
(a+bi)(c+di)
=ac-bd+i[bc+ad]
=a(c+d)-(a+b)d+i[a(c+d)+(b-a)c]
=ac-bd+i[(a+b)(c+d)-ac-bd

Dans le premier calcul, on a 4 multiplications et 2 additions, dans la seconde, on a 3 multiplications et 5 additions, de même que la dernière.
Ce genre de code est intéressant pour des calculs sur des machines pour lesquelles la multiplication est plus lente que l'addition.
Quels sont les risques ?

[Jean-Marc.Bourguet]

La technique est bien connue. Le risque principal me semble etre la perte de precision par annulation si bc+ad est petit par rapport a ac+db.

[progfou]

A quel point bc+ad peut être petit par rapport à ac+db ?
C'est lié à la taille des données, je suppose ?

[progfou]

Mais si mes nombres sont codés en virgule fixe, je n'ai plus ce problème, si ?

[Jean-Marc.Bourguet]

Mais si mes nombres sont codés en virgule fixe, je n'ai plus ce problème, si ?

Exact.

[progfou]

Ah ben c'est une bonne nouvelle ça :o !
Il existe d'autres techniques aussi simples applicables pour d'autres calculs récurrents ?

[Tellmarch]

pour le calcul de multiplication de matrices on a la méthode de strassen qui utilise le meme genre d'astuces... enfin c'est pas exactement ça, mais bon ça y ressemble de loin '_'
d'ailleurs pour des matrices 2x2 ça doit revenir au meme (ou pas).

voila un lient par exemple sur cet algo (je sais c'est en italien, mais les maths sont universelles, et j'ai pas trouvé en français en cherchant rapidement)
http://it.wikipedia.org/wiki/Algoritmo_di_Strassen

[j.p.mignot]

Pour des situations impliquant des multiplications et/ou divisions successives, (propagation, abaques smith, ... ) j'utilise plutôt la représentation polaire où la multiplication et la division de complexes demande une multiplication resp. division et une adition (resp. soustraction) de réels.
Cela est intéressant si
1- on a les coordonnées polaires au départ
2- on passe cartésien ->polaire au début, on fait les calculs, finalement retour en cartésien

si on doit convertir à chaque étapes cartésien <-> polaire, cela devient évidemment trop lourd