schon wieder ne frage (fibonacci + rekursion)
-
hi leutz,
ich hab mit meinen zugegebenermaßen noch frischen assemberkenntnissen versucht die fibonacci-folge rekursiv zu programmieren.
(zur erinnerung, die fibonacci-folge ist folgendermaßen (rekursiv) definiert:
fib(0) = 0
fib(1) = 1
fib(2) = fib(1)+fib(0) = 1
fib(3) = fib(2)+fib(1) = 2
fib(4) = fib(3)+fib(2) = 3
fib(5) = fib(4)+fib(3) = 5
fib(6) = fib(5)+fib(4) = 8
...
fib(n) = fib(n-1)+fib(n-2)die ersten werte der folge sind:
0 1 1 2 3 5 8 13 21 34 55 ...
)das sieht bei mir erstmal so aus:
int fibo(int num) { __asm { cmp num, 1; // (num == 1) ? ja FIBREC; // num > 1: FIBREC // sonst: num == 1 || num == 0 mov eax, num; // fib(0) = 0 bzw fib(1) = 1 jmp FIBENDE; // ENDE FIBREC: dec num; push num; call fibo; // fib(num-1) dec num; push num; call fibo; // fib(num-2) // jetzt müssten die beiden obersten elemente des // stacks fib(n-1) und fib(n-2) sein pop eax; pop ecx; add eax, ecx; FIBENDE: } }ich vestehe nun nicht, warum ich nicht die korreckten werte herausbekomme?!
hab ich etwas nicht beachtet? muss ich vielleicht (wieder erwarten) den stack noch von den argumenten befreihen? oder rhytmisch auf meinen monitor hämmern?!
bis denn
Simon
-
Original erstellt von SimonBee:
oder rhytmisch auf meinen monitor hämmern?!Das bringt dich sicher nicht weiter
Original erstellt von SimonBee:
ich vestehe nun nicht, warum ich nicht die korreckten werte herausbekomme?!hab ich etwas nicht beachtet? muss ich vielleicht (wieder erwarten) den stack noch von den argumenten befreihen?
Du bekommst nicht die korrekten Werte heraus, da du die Rückgabewerte der Funktionsaufrufe nicht beachtest, bzw. überschreibst. Die Rückgabewerte werden in eax geschrieben. Mit pop eax bzw. ecx nimmst du zwar die Parameter wieder vom Stack, überschreibst damit aber auch die Rückgabewerte.
So funktioniert es:
int fib(int num) { __asm { mov eax, num cmp eax, 1 jna END dec eax push eax dec eax push eax call fib add esp, 4 ; oder auch pop ecx etc. mov num, eax call fib add esp, 4 ; oder auch pop ecx etc. add eax, num END: } }lg, phreaking
-
hi phreaking,
du bist wirklich der king! danke schön, ich hab zwar nicht ganz deine lösung, aber du hast mir den entscheidenen hint gegeben!
eine frage hab ich noch:
nach dem aufruf von
push parameter
call fibo
--> hier!!!was ist jetzt auf dem stack, der rückgabewert von fibo (der ja auch in eax ist) oder der parameter?
und dann noch eine frage: wenn ich eax pushe (in den stack) und zum löschen "add esp, 4" machen muss, kann ich davon ausgehen, dass der inhalt von eax beim pushen intern auf 4 scheiben des stacks gelegt wird und damit eine solche scheibe 8 bit breit ist (weil ja eax 32 bit breit ist)???
danke sehr du hast mir in den letzten tagen wirklich VIEL geholfen!
Simon
-
Nur mal so hier just for Fun ein Codeauszug aus meinem unfertigen Tutorial über DOS Assembler. Und zwar handelt es sich auch um eine rekursive Funktion zur Berechnung von kleinen (ich benutze nur AX als Rückgabewert) Fibonaccizahlen. Standalone ASM für den TASM:
fibo PROC NEAR push bp mov bp,sp cmp word ptr [bp+4],1 ja bigger_than_1 mov ax,1 jmp quit_proc bigger_than_1: mov bx,word ptr [bp+4] dec bx push bx call fibo push ax mov bx,word ptr [bp+4] sub bx,2 push bx call fibo pop bx add ax,bx quit_proc: pop bp ret 2 fibo ENDP
-
nach dem aufruf von
push parameter
call fibo
--> hier!!!was ist jetzt auf dem stack, der rückgabewert von fibo (der ja auch in eax ist) oder der parameter?
Auf dem Stack sind nur die Parameter (hier also parameter), der Rückgabewert der Funktion steht nur in eax
und dann noch eine frage: wenn ich eax pushe (in den stack) und zum löschen "add esp, 4" machen muss, kann ich davon ausgehen, dass der inhalt von eax beim pushen intern auf 4 scheiben des stacks gelegt wird und damit eine solche scheibe 8 bit breit ist (weil ja eax 32 bit breit ist)???
Also dass "eine Scheibe" (ein Byte) immer genau 8 Bit breit sind, davon kannst du ausgehen, und das eax auf den CPUs der derzeitigen Architektur 32 Bit breit sind (und daher vier "Scheiben" belegen), kannst du auch voraussetzen...
lg, phreaking
[ Dieser Beitrag wurde am 26.06.2002 um 21:41 Uhr von phreaking editiert. ]
-
*knuddelt ihn weiter*
-
ich habs einst so gelöst:
unsigned int fib(unsigned int num) { __asm{ xor edx,edx mov ebx,1 mov ecx,num loop1: mov eax,ebx; so hier werden die register verschoben mov ebx,edx; so hier werden die register verschoben add edx,eax; und hier wird durch addition dann die fib-folge hergestellt... dec ecx; jnz loop1; mov num,edx } return num; }