Funktion von rekursiv zu nicht rekursiv umschreiben.

[Norbie]

Hi.
Kann man die Folgende Funktion so umschreiben, dass man sie sich nicht selber aufrufen muss? Wenn ja, bitte wie?
Sie berechnet den Mod einer Exponentialzahl.

Code: Alles auswählen

Procedure.l modexp(a.l, b.l, n.l) ;a -Basis b-Exponent c - das wo der rest der Division gefunden werden soll.
        If b = 0
          ProcedureReturn 1
        EndIf
        
        t.l = modexp(a, b/2, n        
        c.l = (t * t) % n
        If b % 2 = 1;
           c = (c * a) % n
        EndIf
        ProcedureReturn c
EndProcedure
   

[Froggerprogger]

Ich habe jetzt zwar nicht den Code direkt übersetzt (ist auch schwierig, da der rekursive Aufruf mittendrin steht.)
Aber wenn Du wirklich nix weiter suchst, als eine Funktion, die eine Zahl a in die b-te Potenz erhebt und den modulo n zurückgibt, dann kannst Du auch einfach die folgende Funktion nutzen:

Code: Alles auswählen

Procedure modexp_2(a.l, b.l, n.l)
  If b=0 : ProcedureReturn 1 : EndIf
  c = a
  While b > 1
    c * a
    c % n
    b - 1
  Wend
  ProcedureReturn c % n
EndProcedure

Allerdings dürfte die hier etwas langsamer sein, da b immer nur um 1 dekrementiert wird, während es bei dir halbiert wird.
Aber sichtbare Effekte gibt das selbst bei so irren Zahlen wie 300^500 noch nicht (es sei denn, Du führst die Funktion super oft aus.)

[Norbie]

Danke. Ist nicht Schlecht, ich will aber mit Potenzen mit 10 Mio stellen arbeiten!

[Froggerprogger]

Mal ne Frage: Warum willst Du keine Rekursion nutzen ?
Da b jedesmal halbiert wird, wird die Funktion log2(n) Male sich selbst aufrufen. Da b maximal 31 Bit (positiv) haben kann, also maximal 31 Male. Da läufst Du absolut nicht in Gefahr, einen Stack-Overflow zu verursachen.

Geschwindigkeit könnte natürlich noch ein Grund sein, da iterative Lösungen meist etwas schneller sind, wobei dies umso stärker auftritt, je häufiger die Rekursion sich selbst aufruft, hier könnte also sogar noch das Gegenteil passieren.
Als einzige Möglichkeit diesen Algorithmus hier iterativ zu bauen, fällt mir ein, ein 32-stelliges Array als 'Stack' zu nutzen, so dass man dort erst die einzelnen Werte für b reinschreibt, und dann damit rechnet.
Besser wäre, wenn Du irgendwo eine Beschreibung des Algorithmus hättest. Mir ist absolut nicht klar, warum man b immer halbieren darf, und immer wenn b ungerade ist, nochmal c*a rechnen sollte. Da ist irgendein geschicktes mathematisches Verfahren hinter, das ich nicht kenne.

[Froggerprogger]

Hab 2 iterative Versionen gemacht, die beide etwas (minimal) schneller als die rekursive Funktion zu sein scheinen, allerdings liegen die Ergebnisse so dicht beisammen, dass diese Art, Geschwindigkeit zu messen, nicht sehr aussagekräftig ist, außer "es sind etwa alle gleich schnell".
Trotzdem liegt bei mir meistens iterativ mit Pointer an erster Stelle, gefolgt von iterativ mit Array, dann rekursiv.
Wenn ich allerdings den Algorithmus verstehen würde, könnte man vielleicht eine iterative Version bauen, die nicht darauf angewiesen ist, dass man zuerst nur die b's errechnet, und dann rückwärts daraus das Ergebnis, sondern man andersherum vorgehen könnte. Aber vielleicht ist das genau der Clou des Algorithmus, dann würde mir nix schnelleres mehr einfallen.
(Anm.: es genügt ein 31-stelliges Array, da der letzte Wert - immer 1 - nicht extra reingeschrieben wird)

Code: Alles auswählen

;- Prozeduren
;/ modexp rekursiv
Procedure.l modexp(a.l, b.l, n.l) ;a -Basis b-Exponent c - das wo der rest der Division gefunden werden soll. 
  If b = 0 
    ProcedureReturn 1 
  EndIf 
  
  t.l = modexp(a, b/2, n)        
  c.l = (t * t) % n 
  If b % 2 = 1; 
    c = (c * a) % n 
  EndIf 
  ProcedureReturn c 
EndProcedure 

;/ modexp iterativ mit Array
Dim modexp_3_b.l(30)
Procedure.l modexp_3(a.l, b.l, n.l)
  If b = 0
    ProcedureReturn 1 
  EndIf
  
  Protected i.l
  
  While b > 0
    modexp_3_b(i) = b
    b/2
    i+1
  Wend
  t=1
  i-1
  While i >= 0
    c = (t*t) % n
    If modexp_3_b(i)%2 = 1
      c = (c*a) % n
    EndIf
    t=c
    i-1
  Wend
  
  ProcedureReturn c
EndProcedure

;/ modexp iterativ mit Pointer
Global *modexp_4_b
*modexp_4_b = AllocateMemory(31*SizeOf(LONG))
Procedure.l modexp_4(a.l, b.l, n.l)
  If b = 0
    ProcedureReturn 1 
  EndIf
  
  Shared *modexp_4_b
  Protected *l.LONG
   
  *l = *modexp_4_b
  While b > 0
    *l\l = b
    b/2
    *l + 4
  Wend
  t=1
  *l-4
  While *l >= *modexp_4_b
    c = (t*t) % n
    If *l\l % 2 = 1
      c = (c*a) % n
    EndIf
    t=c
    *l-4
  Wend
  
  ProcedureReturn c
EndProcedure

;- Tests:
;/ Ergebnisvergleichstest
MessageRequester("","Starte Vergleichstest, ob alle 3 Funktionen dieselben Ergebnisse liefern.",0)
For i=0 To 100000
  a = Random(65535)
  b = Random(10000000)
  c = Random(65535) + 1
  z1 = modexp(a, b, c)
  z2 = modexp_3(a, b, c)
  z3 = modexp_4(a, b, c)
  If z1 <> z2 Or z2 <> z3
    MessageRequester("", "Vergleichstest gescheitert!!",0)
    End
  EndIf
Next
MessageRequester("", "Vergleichstest OK. Starte Geschwindigkeitsvergleich. (Kann einige Sekunden dauern)",0)

;/ Geschwingikeitsvergleichtest
#max = 1000000
RandomSeed(1)
time1 = ElapsedMilliseconds()
For i=0 To #max
  modexp(Random(65535), Random(10000000), Random(65535) + 1)
Next
time1 = ElapsedMilliseconds()-time1

RandomSeed(1)
time2 = ElapsedMilliseconds()
For i=0 To #max
  modexp_3(Random(65535), Random(10000000), Random(65535) + 1)
Next
time2 = ElapsedMilliseconds()-time2

RandomSeed(1)
time3 = ElapsedMilliseconds()
For i=0 To #max
  modexp_4(Random(65535), Random(10000000), Random(65535) + 1)
Next
time3 = ElapsedMilliseconds()-time3

MessageRequester("", "Fertig!"+#LFCR$+"mit Rekursion: " + Str(time1)+#LFCR$+"ohne Rekursion (Array): " + Str(time2)+#LFCR$+"ohne Rekursion (Pointer): " + Str(time3), 0)