Help with stack

[IronCanTaco]

Basically I need to do this with my code: f(n) = f(n-3) + f(n-2), n > 2, f(0) = 1, f(1)=1, f(2) = 7

It has to be done with recursion and I don't have the slightest idea on how to even start with this.

Mostly, I am struggling with how to save results that I get and use them again.


P.s. yes, it's for homework and no, you don't need to solve, I just need help.

[encryptor256]

Hi!

I didn't managed to test this code, but this is how i would do it:

x32:

Code: [Select]

function:
      push ebp
      mov ebp,esp
      %define ebp_n (ebp+8)
      push ecx
      push edx

      mov edx,dword [ebp_n]
      mov eax,dword (1)

      ; (n > 2)
      cmp edx,dword (2)
      jg .continue

      ; (n <= 1)
      cmp edx,dword (1)
      jle .quit

      ; (n = 2)
      mov eax,dword (7)
      jmp .quit
.continue:

      ; Result
      xor edx,edx

      ; f(n-3) + f(n-2)

      ; f(n-3)
      mov ecx,dword [ebp_n]
      sub ecx,qword (3)
      push ecx
      call function
      add edx,eax

      ; f(n-2)
      mov ecx,dword [ebp_n]
      sub ecx,qword (2)
      push ecx
      call function
      add edx,eax

      ; Return value
      mov eax,edx

.quit:
      pop edx
      pop ecx
      pop ebp
      ret 4

Edit: explanation

Think in higher level, C / C++:

Code: [Select]

unsigned int function(unsigned int n)
{
if(n <= 1)
return 1;
if(n == 2)
return 7;

return function(n-3) + function(n-2);
};

Edit: added x64 version

x64:

Code: [Select]

align 16
function:
      push rbp
      mov rbp,rsp
      push r12 ; save rcx
      push r13 ; sum
      lea rsp,[rsp-(8*5)]

      ; Init
      ; - save rcx
      mov r12,rcx
      ; - set return value
      mov rax,qword (1)

      ; (n > 2)
      cmp rcx,qword (2)
      jg .continue

      ; (n <= 1)
      cmp rcx,qword (1)
      jle .quit

      ; (n = 2)
      mov rax,qword (7)
      jmp .quit
.continue:

      ; Result
      ; - sum
      xor r13,r13

      ; f(n-3) + f(n-2)

      ; f(n-3)
      mov rcx,r12
      sub rcx,qword (3)
      call function
      add r13,rax

      ; f(n-2)
      mov rcx,r12
      sub rcx,qword (2)
      call function
      add r13,rax

      ; Return value
      mov rax,r13

.quit:
      ; Clear stack n quit
      lea rsp,[rsp+(8*5)]
      pop r13
      pop r12
      pop rbp
      ret

x64 version is tested and verified, returned results as expected.

Thanks for the task, it was fun to do!

Bye, Encryptor256!!!

[IronCanTaco]

Thank you for the effort.

But like I said, I want to learn how to do this by myself and copying this assignment means that I have learned nothing.
So, care to explain a little bit?

[0xFF]

Basically I need to do this with my code: f(n) = f(n-3) + f(n-2), n > 2, f(0) = 1, f(1)=1, f(2) = 7

It has to be done with recursion and I don't have the slightest idea on how to even start with this.

P.s. yes, it's for homework and no, you don't need to solve, I just need help.

I applaud the fact that you're after the knowledge, rather than the answer. I'd love to help, but I don't understand the description of the function or algorithm you're trying to describe, can you explain it again more clearly? Also, does this have to be done in ASM, or can you use a higher level language, because I'd have used C++ or C or something for a simple and quick recursion problem like this. But ASM or HLA, what you're after is function calls within function calls. Recursion's not particularly hard.

But help me understand:
f(n) = f(n-3) + f(n-2),
n > 2,
f(0) = 1,
f(1)=1,
f(2) = 7

Is this a list of condiitions to be satisfied, or function calls to make, are we searching for a function or number that satisfies these facts, what is it? f stands for function, n for number right? Or is this some other notation I'm not getting? Gotta give more background man.

[IronCanTaco]

It has to be done in NASM.
The program has to print out numbers from f(3) to f(15) while using provided formula ( f(n) = f(n-3) + f(n-2) ) to make calculation.

f(0) = 1
f(1) = 1
f(2) = 7
f(3) = f(0) + f(1) = 2
f(4) = f(1) + f(2) = 8
f(5) = f(2) + f(3) = 9
...

[0xFF]

Mmm, there's got to be a missing piece there. That function would loop forever. There must be a condition such that if f(n)!=1, f(n)=f(n-3)+f(n-2). On review you have a stray n>2 in there. You really need to lay this kind of thing out in a logical HLA function first, do you know any high level languages? If not, you really should learn one of those first. I have some good ideas for how to write this as a NASM function which I think may help you understand how to do recursion, but first you really need to lay it out in pseudocode, like:

function (int n){
if (n > 2)
  n=function(n-3)+function(n-2);
else
 n=1;
return n;
}

Is this unsigned or signed? f(n) seems to me that should equal -7 at least at first. Confusing.

I get good results with this:

Code: [Select]

#include<iostream>
using namespace std;

int function(int input){
if(input>2)
    input=function(input-3)+function(input-2);
else
    input=1;
cout << "input="<< input << endl;
return input;
}

int main(){
    int result=function(8);
    cout << "result=" << result << endl;
    return 0;
}

[Frank Kotler]

Well, these high level examples are too complicated for my simple brain. I'd rather start at the bottom and work up. Since the question asks for "help with stack", maybe we should start with the fact that the "call" instruction puts the return address on the stack (and "ret" removes it - It had better be there!). Our function is going to need a parameter, so we can push that on the stack first...

Code: [Select]

push 15
call func
; XXX

func:
; do nothing
ret

Encryptor256 showed you a slightly different example, which ended in "ret 4". The difference is in calling conventions. The "stdcall" convention expects the called function to clean up the stack (used by Windows APIs). The "cdecl" convention (usually used by C) expects the caller to clean up the stack. The parameter(s) has to be "removed" from the stack. It isn't really "removed" we just move esp above it and reuse the space. Where the "XXX" comment is, we need to "add esp, 4". If you're using "stdcall", do nothing there.

We need to return some value - that just goes in eax - and we need to access our parameter. We can do that by means of a "stack frame". First, we push the caller's ebp. In this case, the caller isn't using ebp but generally it will be. Then we load ebp with the current value of esp. From there on, leave ebp alone! We can alter esp, however. For example, eventually this monster is going to call itself - twice! We might want a temporary variable - unique to this invocation of the function - to store the first result while we call it again. We can make such a temporary variable on the stack...

Code: [Select]

push 15
call func
add esp, 4
; display result
; exit cleanly

func:
push ebp ; save caller's ebp
mov ebp, esp ; set our stack frame pointer
sub esp, 4 ; make room for a temporary variable
; at this point the stack looks like:
; our parameter
; return address
; caller's ebp <- ebp points here
; room for temp <- esp points here

mov eax, [ebp + 8] ; fetch our parameter
; do some logic here
; we'll just return the parameter we were passed
; first, we'll save it in our temporary variable
mov [ebp - 4], eax
mov eax, [ebp - 4] ; for no good reason


mov esp, ebp ; undo our stack frame - this "frees" our temporary variable
pop ebp ; restore caller's ebp
ret

As I understand the "logic", if our parameter is 0 or 1, we want to return 1. If the parameter is 2, we want to return 7. If it is 3 or more, things get complicated. We need to prepare a new parameter, "n - 3", push it, call ourself, clean up stack, save the result in our temporary variable, prepare another parameter, "n - 2" (if we've lost track of "n", we can get it back from the stack "mov eax, [ebp + 8]"), push it, call ourself, clean up stack, add the first result from the temporary variable, and return that. Whew!

If I've got it right, f(15) should be 145, right? I'll post mine (very simple minded one for 32-bit Linux), but let's see what you can come up with first...

Best,
Frank

[encryptor256]

Hi!

If I've got it right, f(15) should be 145, right?

Confirm! f(14), f(15), f(16) => 109, 145, 191

[Frank Kotler]

Thanks for the confirmation. I guess I got it right. Or we both got it wrong the same way.

Best,
Frank

[0xFF]

Low level is fine, I love the low level, it's just that I couldn't really understand the definition of the function. If it's 0,1=1, 2=7, 3+=(f-2)+(f-3) then that seems kind of whacky, but okay, I can handle that. The C++ code was just to try to elicit information on the actual definition. I wouldn't be so offensive as to suggest a non asm solution.

I loves the lowlevel, I feel your passion Frank!