Discussion :

[navyg]

Bonjour,

Je ne sais pas si je suis au bon endroit, mais j'essaye de traduire une fonction récursive python en delphi pascal et je n'y arrive pas .
La fonction python est un calcul de fft :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def fft(u):
    # u : numpy.ndarray
    N = len(u)
    if N==1:
        return u
    pair = u[0::2]
    impair = u[1::2]
    tfd_pair = fft(pair)
    tfd_impair = fft(impair)
    tfd = numpy.zeros(N,dtype=numpy.complex64)
    W = numpy.exp(-1j*2*numpy.pi/N)
    N2 = N//2
    for n in range(N2):
        tfd[n] = tfd_pair[n]+tfd_impair[n]*W**n
    for n in range(N2,N):
        tfd[n] = tfd_pair[n-N2]+tfd_impair[n-N2]*W**n
    return tfd

j'ai essayé de faire la traduction en delphi mais ça ne semble pas marcher.
Il a fallu que j'implémente un type Tcomplex qui n'existe pas en delphi, avec quelques fonctions associées

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
type 
   TComplex=packed record
      re: double;
      im: double;
 
      class function Pui(const x: TComplex; n: Integer): TComplex; static;
      class operator Multiply(const x, y: TComplex): TComplex;
      class operator Add(const x, y: TComplex): TComplex;
   end;
 
 
type
   taocx=array of TComplex;
   ptaocx=^taocx;
 
function PuiCx(const x: TComplex; n: Integer): TComplex; overload;
 
implementation
 
{$R *.fmx}
{$R *.LgXhdpiPh.fmx ANDROID}
{$R *.iPhone4in.fmx IOS}
 
// opérations sur nombres complexes
class function TComplex.Pui(const x: TComplex; n: Integer): TComplex;
var
  r, theta: Double;
begin
// Convertir x en coordonnées polaires
r := Hypot(x.Re, x.Im);
theta := ArcTan2(x.Im, x.Re);
 
// Appliquer la formule de Moivre
r := Power(r, n);
theta := theta * n;
 
// Convertir le résultat en coordonnées rectangulaires
Result.Re := r * Cos(theta);
Result.Im := r * Sin(theta);
end;
 
function PuiCx(const x: TComplex; n: Integer): TComplex;
begin
result:=TComplex.Pui(x, n);
end;
 
class operator TComplex.Add(const x, y: TComplex): TComplex;
begin
Result.Re := x.Re + y.Re;
Result.Im := x.Im + y.Im;
end;
 
class operator TComplex.Multiply(const x, y: TComplex): TComplex;
begin
Result.Re := x.Re * y.Re - x.Im * y.Im;
Result.Im := x.Re * y.Im + x.Im * y.Re;
end;
 
// en paramètres d entrée : tableau des complexes issus de la conversion des entiers   
// en résultat le tableau de la FFT
function FFT(cxs: taocx): taocx;
   var
      Nb, N2, n: Integer;
      pair, impair, tfd_pair, tfd_impair, tfd: taocx;
      W: TComplex;
   begin
 
   Nb := Length(cxs);
   if Nb = 1 then
      Exit(cxs);
   SetLength(pair, Nb div 2);
   SetLength(impair, Nb div 2);
   for n := 0 to Nb div 2 - 1 do
      begin
      pair[n] := cxs[2*n];
      impair[n] :=cxs[(2*n)+1];
      end;
   tfd_pair := FFT(pair);
   tfd_impair := FFT(impair);
   SetLength(tfd, Nb);
   W.re:=0;
   W.im:=-(2*Pi/Nb);
   N2 := Nb div 2;
   for n := 0 to N2 - 1 do
      begin
      tfd[n] := tfd_pair[n] + (tfd_impair[n] * PuiCx(W, n));
      tfd[n+N2] := tfd_pair[n] + (tfd_impair[n] * PuiCx(W, n + N2));
      end;
   Result := tfd;
   end;

Mais là où le bât blesse c'est que du fait de la récursivité, lorsque les instructions de fft sur les rangs pairs

Code :

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

1
2
3
4
5
6
SetLength(pair, Length(pcxs^) div 2);
   for n := 0 to Length(pcxs^) div 2 - 1 do
      begin
      pair[n] := pcxs^[2*n];
      end;
   tfd_pair := FFT(@pair, 'pair'); // le string pair est ajouté pour faciliter le traçage dans mon fichier de débogage car sur android je n'arrive pas à faire du pas à pas.

sont exécutées, elles s'appellent récursivement jusqu'à ce que la taille du tableau pair soit de 1.
Et ensuite quand l'instruction de dimensionnement du tableau impair arrive :

Code :

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

1
2
3
4
5
6
   SetLength(impair, Length(pcxs^) div 2);
   for n := 0 to Length(pcxs^) div 2 - 1 do
      begin
      impair[n] :=pcxs^[(2*n)+1];
      end;
   tfd_impair := FFT(@impair, 'impair');

la taille du tableau cxs d'origine est déjà réduite à 1 donc je débute impair avec un tableau de taille 1 !

donc je cherche à résoudre ce problème, mais je n'y arrive pas ... et je connais quasiment pas python.
Donc j'ai peut-être mal compris l'écriture python et donc mal traduit.
Mais si quelqu'un avait la connaissance des deux langages ?

Merci d'avance de votre aide.

[MPython Alaplancha]

Bonjour,
Cette fonction calcule la transformée de Fourier qui est largement documentée. Autant partir de l'algo originel que tu trouveras en cherchant sur le net. (tu y trouveras certainement aussi des codes qui l'implémentent en Delphi)

[Sve@r]

Bonjour

Mais là où le bât blesse c'est que du fait de la récursivité, lorsque les instructions de fft sur les rangs pairs sont exécutées, elles s'appellent récursivement jusqu'à ce que la taille du tableau pair soit de 1.
Et ensuite quand l'instruction de dimensionnement du tableau impair arrive... la taille du tableau cxs d'origine est déjà réduite à 1 donc je débute impair avec un tableau de taille 1 !

C'est parce que dans le code Python, le tableau d'origine est dupliqué en un tableau pair et un tableau impair. Ce sont les lignes...

Code python :

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

1
2
pair = u[0::2]
impair = u[1::2]

... qui font ça.
Donc ce n'est pas le tableau d'origine qui est traité mais des copies indépendantes.

Il te faut implémenter la même chose en Pascal (Delphi) si tu veux avoir le même résultat.

Ou alors suivre le conseil de Hominidé qui semble quand-même plus approprié et tout recoder directement à la sauce Pascal.

[navyg]

Merci pour vos contributions
J'implemente bien la copie en deux tableaux pair et impair mais ça ne fonctionne pas
Quant aux versions Pascal que j'ai pu trouver ici et là, aucune ne fonctionne vraiment.
Elles donnent toutes des résultats complètement erratiques. J'en ai essayé plusieurs différentes.
J'ai trouvé depuis cette nuit une autre version itérative que j'ai convertie depuis python qui me donne de meilleurs résultats
Merci quand même à vous.

[MPython Alaplancha]

J'ai trouvé depuis cette nuit une autre version itérative que j'ai convertie depuis python qui me donne de meilleurs résultats

Simple curiosité: pourquoi vouloir utiliser Pascal? Numpy étant une bibliothèque écrite en C, je doute qu'il y ait un avantage à utiliser Pascal. (du moins je l'imagine, car je n'utilise pas Pascal).

[navyg]

Simple curiosité: pourquoi vouloir utiliser Pascal? Numpy étant une bibliothèque écrite en C, je doute qu'il y ait un avantage à utiliser Pascal. (du moins je l'imagine, car je n'utilise pas Pascal).

Parce que je développe en delphi
Je n'y connais rien en C, Java, très peu en python (j'ai essayé, mais je n'avais pas trouvé de vrai intérêt pour python pour faire des applis de gestion en interface graphique)
Basic c'est obsolète
Je programme en pascal depuis que j'ai eu mon premier ordinateur en 1983 avant les pc : un amstrad 6128 !
Donc je suis assez habitué à ce langage ...
J'essaye de faire en delphi pour android un accordeur de guitare ... projet tout à fait perso pour m'occuper

[Sve@r]

mais je n'avais pas trouvé de vrai intérêt pour python pour faire des applis de gestion en interface graphique)

https://pyqt.developpez.com/telechar.../47/Hello-Word

Je programme en pascal depuis que j'ai eu mon premier ordinateur en 1983 avant les pc : un amstrad 6128 !
Donc je suis assez habitué à ce langage ...

Ca ok suis d'accord, c'est effectivement la meilleure des raisons. On fait avec parce que l'on aime faire avec. Rien à redire là dessus.

Je me demande toutefois, pour la puissance d'un complexe, pourquoi tu t'es embêté à passer par du polaire. Tu as créé la multiplication or un complexe élevé à la puissance n ce n'est qu'un complexe multiplié par lui-même n fois. Parce que le polaire c'est quand-même pas super précis quoi.

[navyg]

https://pyqt.developpez.com/telechar.../47/Hello-Word

...

Je me demande toutefois, pour la puissance d'un complexe, pourquoi tu t'es embêté à passer par du polaire. Tu as créé la multiplication or un complexe élevé à la puissance n ce n'est qu'un complexe multiplié par lui-même n fois. Parce que le polaire c'est quand-même pas super précis quoi.

Pour le lien Hello World, ça me répond qu'il faut être connecté ...

Pour la puissance tu as raison, je n'ai pas réfléchi ! J'ai trouvé cette formule sur internet et je l'ai traduite en pascal
Je vais faire des tests pour vérifier les différences et l'exactitude entre les deux méthodes et surtout je vérifierai la rapidité d'exécution entre les deux méthodes.

Merci pour tes remarques.

[navyg]

:
Je me demande toutefois, pour la puissance d'un complexe, pourquoi tu t'es embêté à passer par du polaire. Tu as créé la multiplication or un complexe élevé à la puissance n ce n'est qu'un complexe multiplié par lui-même n fois. Parce que le polaire c'est quand-même pas super précis quoi.

Alors j'ai testé :
avec la formule de moivre c'est environ 7 fois plus rapide
Pour le code suivant :

Code :

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

1
2
3
4
5
for k:=0 to j-1 do
   begin
   for var i:=0 to 10000 do
      v[k]:=puicx(u[k], k);
   end;

La multiplication k fois par lui-même met 3.3s

La formule de Moivre mouline pendant .... 0.5s

Mais j'ai fait des comparaisons sur les résultats : autant c'est équivalent sur les petites puissances jusqu'à 8 ou 9, voire 10, autant à partir de 11, les différences s'envolent.
Pour le peu d'opération que j'ai à faire, je vais sacrifier le temps à la précision.
Merci

[fred1599]

Hello,

@navyg,

Je ne sais pas si je suis au bon endroit, mais j'essaye de traduire une fonction récursive python en delphi pascal et je n'y arrive pas .

Ça me rappelle les développeurs Java qui voulaient se mettre au Python, Python n'est pas Java, et Python n'est pas Delphi... Vous pouvez garder vos connaissances théoriques, la pratique va demander une recherche et une adaptation spécifique au langage.
Comme tu l'as si bien dit la partie nombres complexes ou tableaux ne fonctionnent pas de la même manière en Delphi, il est donc peu cohérent de calquer Python à Delphi.

@Hominidé à proposer la solution à votre problème, c'est la meilleure manière de faire, partir d'un algo, considérer la documentation Delphi ou Pascal et développer votre code.

[marco056]

Des résultats aléatoires me font songer à des mesures pas très précises...

[navyg]

Hello,
@navyg, ..... Ça me rappelle les développeurs .....

J'y suis pourtant arrivé en convertissant une fonction itérative de python vers delphi, que j'ai trouvé très élégante, en tout cas bien plus que les autres manière de gérer les fft (et je peux vous dire que j'ai vu quelques algo différents !). Même si je ne sais pas si c'est la plus rapide.

Les nombres complexes sont identiques quel que soit le langage : une partie réelle et une partie imaginaire.
Comme ils n'existent pas en delphi j'ai créé une classe qui les traite car j'en aurai peut-être besoin un jour pour autre chose ;o)
C'est plutôt la manière de gérer les tableaux qui est très différente.

J'aime bien sortir de mon domaine pour découvrir d'autres choses et ce petit projet m'a permis d'explorer un peu python, entre autres !

Des résultats aléatoires me font songer à des mesures pas très précises...

C'est exactement ce que je me suis dit une fois que j'ai déverminé mon code.
J'ai refait des échantillons et ça va déjà beaucoup mieux, mais ce n'est pas encore ça.
Merci

[fred1599]

@navyg,

Les nombres complexes sont identiques quel que soit le langage : une partie réelle et une partie imaginaire.
Comme ils n'existent pas en delphi j'ai créé une classe qui les traite car j'en aurai peut-être besoin un jour pour autre chose ;o)
C'est plutôt la manière de gérer les tableaux qui est très différente.

Oui c'est ce que je vous ai dis, c'est une autre manière de développer, ce que vous faîtes ne correspond donc plus à ce qui a été fait en python (la création de classe aurait pu être fait aussi en python, mais il y a mieux dans ce langage)

J'aime bien sortir de mon domaine pour découvrir d'autres choses et ce petit projet m'a permis d'explorer un peu python, entre autres !

Tant mieux et ça permet de constater les différences entre chaque langage... En python on aurait peut-être pu faire cela de manière directe avec numpy

Code :

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

1
2
3
4
import numpy as np
 
array = # tableau de données
fft_result = np.fft.fft(array)

Qui puis est python, souvent, n'aime pas les fonctions récursives (performance dégradée), car elles augmentent considérablement la taille de la pile d'appels, ce qui ne se passe pas pour des langages prévus pour cela (Haskell, Scheme, ...).

[navyg]

Oui j'ai constaté que la récursivité peut-être très puissante en terme de concision du code, mais cela augmente la pile et aussi les recopies de tableaux, ce qui peut dégrader les performances.
J'ai d'ailleurs abandonné cette voie pour faire une fonction itérative, plus facile à déboguer en plus