Procedur, die sich selbst aufruft

[Berti27]

Hallo,
Bei der Beschäftigung mit der schnellen Fourier-Analyse (FFT) bin ich dabei, ein Demonstrationsprogramm aus Freepascal auf PureBasic zum Laufen zu bringen. In dem Pascal-Programm ist eine FFT-Procedur, die sich selbst aufruft, um nach und nach die Werte zu generieren.
Mein Code für diese Procedur sieht zuzeit so aus:

Code: Alles auswählen

Procedure fft(Array f(1),Array c(1),n.l); !!!Achtung!!! Variable "f" und "c" sind Arrays!
  Dim u.f(2047)
  Dim v.f(2047)
  Dim cp.f(2047)
  Dim cm.f(2047)
  
  If n=1
    c(0)=f(0)
    c(1)=f(1)
  Else
    n1=n-1
    n2=n/2
    For j=0 To n1
      w(2*j)=Cos(j*2*Pi/n)
      w(2*j+1)=-Sin(j*2*Pi/n)
    Next
    For j=0 To n2-1
      u(2*j)  =(f(2*j)+f2*j+n)/2
      u(2*j+1)=(f(2*j+1)+f(2*j+1+n))/2
      v(2*j)  =((f(2*j)-f(2*j+n))*w(2*j)-(f(2*j+1)-f(2*j+1+n))*w(2*j+1))/2
      v(2*j+1)=((f(2*j)-f(2*j+n))*w(2*j+1)+(f(2*j+1)-f(2*j+1+n))*w(2*j))/2
    Next
    fft(u,cp,n2)      ;Übergabewert richtig?
    fft(v(),cm(),n2)      ;dito
    For j=0 To n2-1 
      c(4*j)=cp(2*j)
      c(4*j+1)=cp(2*j+1)
      c(4*j+2)=cm(2*j)
      c(4*j+3)=cm(2*j+1)
    Next
  EndIf
EndProcedure

Die Zeilen "fft(u,cp,n3)" und die nächste sind die aufrufenden Ausdrücke. Der Compiler zeigt mir genau an dieser Stelle Fehler an. Leider habe ich in der vergangenen Zeit und im Handbuch nicht eindeutiges dazu gefunden (, oder ich habe momentan ein Brett vor dem Kopf).
Kann mir jemand auf die Sprünge helfen?

[STARGÅTE]

In den Prozedurparametern musst du den richtigen Typen für die Array angeben.

Du möchtest Float-Arrays übergeben, dann also:

Code: Alles auswählen

Procedure fft(Array f.f(1), Array c.f(1), n.l)

und entsprechend:

Code: Alles auswählen

fft(v(),cm(),n2)

Bitte noch beachten, dass Array in PureBasic immer als Referenz (und nicht als Kopie) übergeben werden.
Änderungen wirken sich somit immer auf beide Orte aus.

[helpy]

@Berti27:

Ich würde an Deiner Stelle "EnableExplicit" verwenden und Variablen immer deklarieren.

Welchen Datentyp haben n1, n2, j, w() und f2 ???

In einer Zeile steht folgendes:

w(2*j)=Cos(j*2*Pi/n)

Wo ist das Array oder die Funktion w() definiert?
Wo ist Pi definiert? ==> Verwende die Konstante #PI

In einer anderen Zeile steht folgendes:

u(2*j) =(f(2*j)+f2*j+n)/2

Was ist f2? Wo ist diese Variable definiert?
Oder ist "...f2*j+n..." falsch und stattdessen wolltest Du eigentlich "...f(2*j+n)..." schreiben?

[Berti27]

Herzlichen Dank zuerst einmal für Eure Antworten!
Pi habe ich erst einmal zu Beginn der Programmausführung als Variable festlelegt. Das ist bestimmt nicht besonders einfallsreich. #PI als Konstante zu nehmen ist sicher der bessere Weg. Das Array w() habe ich im Hauptprogramm als Global definiert.
Ja, und Ihr habt mich ertappt: Zwischen f und 2 fehlt eine Klammer und dann sicherlichlich noch das Gegenstück.
Inzwischen habe ich auf "Wikibooks" das Buch PureBasic gefunden und als Broschüre augedruckt. Auch dort las ich bei Prozeduren im Zusammenhang mit der Übergabe von Arrays, dass diese nur als Referenz gespeichert werden und somit innerhalb wie außerhalb der Funktion sichtbar sind.
Deshalb habe ich mir gedacht, sie gleich als Global zu definieren, zumindest die, die sowieso auch innerhalb der Prozedur benötigt werden, dann erspare ich mir möglicherweise die Übergabe und die Rückgabe.
Liege ich da richtig?

[GPI]

Auch dort las ich bei Prozeduren im Zusammenhang mit der Übergabe von Arrays, dass diese nur als Referenz gespeichert werden und somit innerhalb wie außerhalb der Funktion sichtbar sind.
Deshalb habe ich mir gedacht, sie gleich als Global zu definieren, zumindest die, die sowieso auch innerhalb der Prozedur benötigt werden, dann erspare ich mir möglicherweise die Übergabe und die Rückgabe.
Liege ich da richtig?

Es gibt keine Übergabe/Rückgabe. "Als Referenz" bedeutet, es wird nur ein "Link" übergeben. Sprich die Prozedur bekommt nur ein Pointer (=Adresse) wo die übergebene Arrsay liegt. Purebasic übernimmt nur die Handharbung in Hintergrund, so das du ganz normal auf das Array zurückgreifen kann. Und der Pointer hat die größe von einen Integer, dementsprechend geht die übergabe sehr schnell. Wenn du dann in der Prozedur irgendwas an den Array änderst, dann wird es auch in "Original" geändert. Es ist keine seperate Kopie.

Wenn die Prozedur nur das eine Array verändern soll, dann ist ein globales Array eine valide Lösung. Solltest du aber in der Prozedur verschiedene Arrays bearbeiten wollen, musst du natürlich übergeben, welche.

Noch ein Tip: Purebasic unterstüzt sehr lange Variablen-Namen. Nutz sie! Besser als jeder Kommentar. Und man kann noch in Jahren verstehen, was man da geschrieben hat.

[Berti27]

Vielen Dank für die guten Ratschläge!
Mein FFT-Problem habe ich inzwischen gelöst und ich komme ohne den rekursiven Aufruf der Procedur aus. Es wird innerhalb der Procedur so lange gerechnet, bis das Ergebnis fertig ist. Dazu war es notwendig, das Ganze noch einmal zu durchdenken. In der ELV-Dokumentation zur digitalen Signalverarbeitung habe ich dann endlich die Lösung zum zusammenbasteln gefunden.

Code: Alles auswählen

OpenConsole("Schleifenkonstruktion FFT")
EnableGraphicalConsole(1)
Global Dim z.f(1024,1)
Global Dim xIn.f(1024)            ;Real-Teil   
Global Dim yIn.f(1024)            ;Imag-Teil
Global e.l

Procedure Beispiel1(e.l)
  n.l=Pow(2,e)
  PrintN("")
  PrintN("Eingangssignal FFT nach DecimationInFrequency-Methode")
  For i=0 To n-1
    xIn(i)=Sin(3*2*i*#PI/n)+Cos(5*2*i*#PI/n)
    yIn(i)=0
    PrintN(Str(i)+" : "+ StrF(xIn(i),5)+ " + i* "+StrF(yIn(i),5))
  Next
EndProcedure

Procedure Schleife(m.i)
  Beginn= ElapsedMilliseconds()
  
;bei n=8 ist seq= 8/2=4. i muss nacheinander die Werte 0, 1, 2, 3 & 0, 1 + 4, 5 & schließlich 0 + 2 + 4 + 6 annehmen
;                                                     |__________| |___________|             |_____________|
;das entspricht den Sequenzen:                              1            2                          3
;Bei seq=4 entspricht das den Faktoren                    1*4=4       2*2=4                     4*1=4
  n=Pow(2,m)  
  Dim w.f(n,1)
 
  For i=0 To n-1                 ;Eingangswerte in das Array z(x,y) transferieren
    z(i,0)=xIn(i)                ;x(i)=xIn(i)
    z(i,1)=yIn(i)                ;y(i)=yIn(i)
  Next
  
  For j=0 To n-1                ;Drehfaktor
    w(j,0)= Cos(j*2*#PI/n)
    w(j,1)=-Sin(j*2*#PI/n)
  Next
  
  lauf=n
  seq=lauf/2
  wx=0
  wi=1
  For d=0 To m-1        ;Anzahl der Sequenzen, Auflösung, übergebene Variable m
    For i=0 To lauf-1
      j=i+seq
      tr.f=z(i,0)+z(j,0)                   ;Summe real
      ti.f=z(i,1)+z(j,1)                   ;Summe imag
      sr.f=(z(i,0)-z(j,0))                 ;Differenz real
      si.f=(z(i,1)-z(j,1))                 ;Differenz imag
      z(i,0)=tr
      z(i,1)=ti
      If wx<>0
        z(j,0)=(sr * w(wx,0)-si * w(wx,1)) ;Differenz * Drehfaktor real
        z(j,1)=(sr * w(wx,1)+si * w(wx,0)) ;Differenz * Drehfaktor imag
      Else
        z(j,0)=sr
        z(j,1)=si
      EndIf
      wx=(wx+wi)%(n/2)  
      If ((i+1)/seq)%2=1
        i=i+seq
      EndIf
      
    Next
    seq=seq/2
     wx=0
     wi=wi*2
  Next
  nv2=n/2
  nm1=n-1
  j=1
  For i=1 To nm1              ;Ausgängsbreite sortieren 0,4,2,6,1,5,3,7 wird zu 0,1,2,3,4,5,6,7
    If i<j
      tr=z(j-1,0)
      ti=z(j-1,1)
      z(j-1,0)=z(i-1,0)
      z(j-1,1)=z(i-1,1)
      z(i-1,0)=tr
      z(i-1,1)=ti
    EndIf
    k=nv2
    While k<j
      j=j-k
      k=k/2
    Wend
    j=j+k
  Next 
  Zeit=ElapsedMilliseconds()-Beginn
  For i=0 To n-1
  Next
  PrintN("")
  PrintN("Durchlaufzeit folgender FFT-Schleife: "+Str(Zeit)+" Millisekunden")

EndProcedure

Procedure Lauf()
  
  Print("Exponent e der Stützstellenzahl n=2^e, e= ")
  e$=Input(): e=Val(e$)
  Beispiel1(e)
  Schleife(e)
EndProcedure

Eingabe:
Lauf()
n=Pow(2,e)
PrintN("Ausgangssignal FFT")
For i=0 To n-1
  a$=StrD(z(i,0)/n,5)
  b$=StrD(z(i,1)/n,5)
  PrintN(Str(i)+" : "+a$ +" +i* "+b$)
Next
For i=0 To n-1
  xIn(i)=z(i,1)
  yIn(i)=z(i,0)
Next
Schleife(e)
PrintN("Ausgangssignal iFFT (Real- und Imag-Ein- und Ausgang vertauscht)")
For i=0 To n-1
  a$=StrD(z(i,1)/n,5)
  b$=StrD(z(i,0)/n,5)
  PrintN(Str(i)+" : "+a$ +" +i* "+b$)
Next

Print("Ein weiterer Durchlauf? [j]+[Enter]: ")
a$=Input()

If a$="j"
  ClearConsole()
Else
  End
EndIf

Goto Eingabe:

Sicher gibt es im Code noch Verbesserungsmöglichkeiten, aber zu ersten Ausprobieren reicht dies kleine Konsolenprogramm! Vielleicht kann jemand das ja gebrauchen.
P.S.: Wie kann ich eigentlich kennzeichnen, dass das Problem gelöst ist?