Calculating the nth fibonacci element using recursion. I have a C++ driver and am in need of a assembly language subprogram to do the calculation

I am in need of a sub program in assembly to work with this c++ driver. The driver is below

#include <iostream>

using namespace std;

extern "C" int fibonacci(int n);

int main()
{
int n, value;
cout << "Enter the desired element index (n>0): ";
cin >> n;

value = fibonacci(n);

if(value == -1)
cout << "error" << endl;
else
cout << "The " << n << "th Fibonacci number is " << value << endl;

return 0;
}

I have started the sub program. It is supposed to use recursion to calculate the nth fibonacci number when the user inputs the element desired.
The subprogram is located below (it doesn't work correctly)

.globl _fibonacci

.section .text
_fibonacci:
enter      \$0, \$0      # push EBP, EBP = ESP
push %edx
push %ecx
movl 8(%ebp), %eax

fib:
cmpl \$2, %eax # compare eax to 1
jg   fib2      # if not greater than 1 calc fib number
movl \$1, %eax
jmp end      # return with 1 in eax

fib2:

movl %eax, %ecx      # save the number entered
subl \$1, %eax      # subtract 1 from number f(n-1)
call fib            # call fib again
movl %eax, %edx # save result for f(n-1)
movl %ecx, %eax # get original number back
subl \$2, %eax      # subtract 2 from number f(n-2)
call fib            # call fib again
jmp end            # return

end:
popl %ecx
popl %edx
leave
ret

Thanks for any help
Who is Participating?

Commented:
but when you "call fib"
"movl 8(%ebp), %eax" will not be executed
0

Commented:
What do You mean saying it's not working? Did all that compile? Whether the result is wrong? Or did some other pit falls occure?
0

Commented:
You could use this simplified algo. It's in C/Java:

int fib(int n) {
int first = 0, second = 1;
// this while loop will exit when the int reaches 0
// it is equivalent to while(n != 0) { n-- .... }
while (n--)
{
int tmp = first+second;
first = second;
second = tmp;
}
return first;
}

0

Commented:
this procedure calculates the nth fibonacci element recursively

/******************/
fib proc NEAR32
PUSH EBP
MOV EBP, ESP
PUSH EBX
SUB ESP, 4
CMP DWORD PTR [EBP+8], 2
JG L1
MOV DWORD PTR [EBP-8], 1
JMP L2
L1:
MOV EAX, [EBP+8]
DEC EAX
PUSH EAX
CALL fib
MOV EBX, EAX
MOV EAX, [EBP+8]
SUB EAX, 2
PUSH EAX
CALL fib
MOV [EBP-8], EBX
L2:
MOV EAX, [EBP-8]
POP EBX
POP EBP
RET 4
fib endp
/****************/

use it like

push 6; nth element
call fib; the result will be in EAX

it has been written according to the following C version

int fib(int n) {
if(n <= 2)
return 1;
else
return fib(n-1) + fib(n-2);
}
0

Author Commented:
It is not in the same language that I am using. I can see that it is assembly but I translated it to my language and it doesn't work.  Thanks though. If you have any other suggestions please let me know.
0

Commented:
because we are in Assembly TA.
what language do you want it to be ?
0

Author Commented:
IA-32 Assembly
thanks
0

Commented:
this is a simpler version

fib proc NEAR32
PUSH EBP
MOV EBP, ESP
PUSH EBX
CMP DWORD PTR [EBP+8], 2
JG L1
MOV EBX, 1
JMP L2
L1:
MOV EAX, [EBP+8]
DEC EAX
PUSH EAX
CALL fib
MOV EBX, EAX
MOV EAX, [EBP+8]
SUB EAX, 2
PUSH EAX
CALL fib
L2:
MOV EAX, EBX
POP EBX
POP EBP
RET 4
fib endp

please convert it to IA-32 and let me see the code
0

Author Commented:
This is my best conversion that I can (on movl source, destination) for example

.globl _fibonacci

.section .text
_fibonacci:

fib:
pushl %EBP
movl %EsP, %EbP
PUSHl %EBX
SUBl \$4, %esp
CMPl \$2, 8(%ebp)
JG L1
MOVl \$1, -8(%ebp)
JMP L2
L1:
MOVl 8(%ebp), %eax
subl \$1, %EAX
PUSHl %EAX
CALL fib
MOVl %EaX, %EbX
MOVl 8(%ebp), %EAX
SUBl \$2, %EAX
PUSHl %EAX
CALL fib
MOVl %ebx, -8(%ebp)
L2:
MOVl -8(%ebp), %EAX
POPl %EBX
POPl %EBP
RET
0

Commented:
Hi 00transam,

In x86 assembler,

EBP is a stack frame base pointer register.
EAX/EBX are work registers.
ESP is the stack pointer register.

Paul
0

Author Commented:
What are you trying to tell me, because I know that. I need to know how to possibly get the code above to work.  I have translated it and ran it. I get a segmentation error which means the stack is corrupted.

Colt
0

Commented:
Ok Colt,

I dont know the specific language but I should be able to help.

Write me some code that does something very simple like:

if number > 1 then return result of call with parameter (number - 1)
otherwise return 1

Make it as simple as possible.

From there we should be able to build something that works. If that's too difficult, let me know.

Paul
0

Author Commented:
Below is a working fibonacci number generator but the one that I need to make now is one using recursion. The one below uses a loop. This may be alittle more than you wanted. Just let me know.

Thanks
Colt

.globl _asm_main
.section .data

prompt1:      .asciz "Enter the a coefficient: "
prompt2:      .asciz "Enter the b coefficient: "
prompt3:      .asciz "Enter the c coefficient: "
output1:      .asciz "The roots are "
output2:      .asciz " and "
output3:      .asciz "The double root is "
output4:      .asciz "The complex roots are ("
output5:      .asciz ", "
output6:      .asciz ") and ("
output7:      .asciz ", "
output8:      .asciz ")"
const1:            .float 2.0
const2:            .float 4.0
const3:            .float 1.0
const4:            .float 0.0
const5:            .float -1.0

.section .text
_asm_main:

enter      \$0, \$0                                    #sets up the stack
pusha                                                #saves all the registers
finit                                                #initializes the FPU stack
#the way I am representing the stack is left to right is top to bottom
movl      \$prompt1, %eax                        #promt user to enter a
call      print_str
fst            %st(3)                                    #FPU ,a, , ,a,
movl      \$prompt2, %eax                        #prompt user to enter b
call      print_str
fst            %st(2)                                    #FPU ,b, ,b,a,
movl      \$prompt3, %eax                        #prompt user to enter c
call      print_str
fstp      %st(1)                                    #FPU = , ,c,b,a,
flds      const2                                    #FPU = ,4,c,b,a,
fmul      %st(1), %st(0)                        #FPU = ,4*c,c,b,a,
fmul      %st(3), %st(0)                        #FPU = ,4*c*a,c,b,a,
fxch      %st(4)                                    #FPU = , ,c,b,a,4*c*a,
subl      \$8, %esp                              #Subtracts 8 from CPU stack
fstpl      (%esp)                                    #FPU ,c,b,a,4*c*a,
fstpl      (%esp)                                    #FPU ,b,a,4*c*a
flds      const3                                    #FPU ,1,b,a,4*c*a,
fmul      %st(1), %st(0)                        #FPU ,1*b,b,a,4*c*a,
fmul      %st(1), %st(0)                        #FPU ,b*b,b,a,4*c*a,
fsub      %st(3), %st(0)                        #FPU ,b^2-4*c*a,b,a,4*c*a,
flds      const4                                    #FPU ,0,b^2-4*c*a,b,a,4*c*a,
fcomip      %st(1), %st(0)                        #Compares( b^2 -4ac) to 0
ftst                                                #Compares( b^2 -4ac) to 0
jb            greater                                    #Jumps to greater if greater than 0
ja            lessthan                              #Jumps to lessthan if lessthan 0
jz            equal                                    #Jumps to equal if equal to 0
greater:

fsqrt                                                #Takes the square root of st(0) FPU ,sqrt(b^2-4ac),b,a,4*a*c
fsub      %st(1),      %st(0)                        #FPU ,b-sqrt(b^2-4ac),b,a,4*a*c
flds      const1                                    #Loads 2 into st(0) FPU ,2,b-sqrt(b^2-4ac),b,a,4*a*c
fmul      %st(3), %st(0)                        #FPU ,2*a,b-sqrt(b^2-4ac),b,a,4*a*c
fxch      %st(1)                                    #FPU ,b-sqrt(b^2-4ac),2*a,b,a,4*a*c
fdiv      %st(1), %st(0)                        #FPU ,b-sqrt(b^2-4ac)/(2*a),2*a,b,a,4*a*c
movl      \$output1, %eax                        #output the 1st root
call      print_str
call      print_double
movl      \$output2, %eax
call      print_str
ffreep      %st(0)                                    #FPU ,2*a,b,a,4*a*c
flds      const3                                    #FPU ,1,2*a,b,a,4*a*c
fmul      %st(2), %st(0)                        #FPU ,1*b,2*a,b,a,4*a*c
fmul      %st(2), %st(0)                        #FPU ,b*b,2*a,b,a,4*a*c
fsub      %st(4), %st(0)                        #FPU ,b^2-4ac,2*a,b,a,4*a*c
fsqrt                                                #FPU ,sqrt(b^2-4ac),2*a,b,a,4*a*c
flds      const5                                    #FPU ,-1,sqrt(b^2-4ac),2*a,b,a,4*a*c
fmul      %st(3),      %st(0)                        #FPU ,b*-1,sqrt(b^2-4ac),2*a,b,a,4*a*c
fsub      %st(1), %st(0)                        #FPU ,(b*-1)-sqrt(b^2-4ac),sqrt(b^2-4ac),2*a,b,a,4*a*c
fdiv      %st(2), %st(0)                        #FPU ,((b*-1)-sqrt(b^2-4ac))/(2*a),sqrt(b^2-4ac),2*a,b,a,4*a*c
call      print_double                        #print the 2nd root
jmp            end

lessthan:
flds      const5                                    #FPU ,-1,4ac-b^2,b,a,4ac
fmul      %st(2), %st(0)                        #FPU ,-1*b,4ac-b^2,b,a,4ac
flds      const1                                    #FPU ,2,-1*b,4ac-b^2,b,a,4ac
fmul      %st(4), %st(0)                        #FPU ,2*a,-1*b,4ac-b^2,b,a,4ac
fxch      %st(1)                                    #FPU ,-1*b,2*a,4ac-b^2,b,a,4ac
fdiv      %st(1),      %st(0)                        #FPU ,(-1*b)/(2*a),4ac-b^2,b,a,4ac
movl      \$output4, %eax                        #print the real part of the root
call      print_str
call      print_double
movl      \$output5, %eax
call      print_str
fxch      %st(6)                                    #FPU , ,2*a,4ac-b^2,b,a,4ac,-b/(2a)
ffreep      %st(0)                                    #FPU ,2*a,4ac-b^2,b,a,4ac,-b/(2a)
flds      const3                                    #FPU ,1,2*a,4ac-b^2,b,a,4ac,-b/(2a)
fmul      %st(3), %st(0)                        #FPU ,1*b,2*a,4ac-b^2,b,a,4ac,-b/(2a)
fmul      %st(3),      %st(0)                        #FPU ,b^2,2*a,4ac-b^2,b,a,4ac,-b/(2a)
fxch      %st(5)                                    #FPU ,4ac,2*a,4ac-b^2,b,a,b^2,-b/(2a)
fsub      %st(5), %st(0)                        #FPU ,4ac-b^2,2*a,4ac-b^2,b,a,b^2,-b/(2a)
fsqrt                                                #FPU ,sqrt(4ac-b^2),2*a,4ac-b^2,b,a,b^2,-b/(2a)
flds      const1                                    #FPU ,2,sqrt(4ac-b^2),2*a,4ac-b^2,b,a,b^2,-b/(2a)
fmul      %st(5), %st(0)                        #FPU ,2*a,sqrt(4ac-b^2),2*a,4ac-b^2,b,a,b^2,-b/(2a)
fxch      %st(1)                                    #FPU ,sqrt(4ac-b^2),2*a,2*a,4ac-b^2,b,a,b^2,-b/(2a)
fdiv      %st(1), %st(0)                        #FPU ,sqrt(4ac-b^2)/(2*a),2*a,2*a,4ac-b^2,b,a,b^2,-b/(2a)
call      print_double                        #print the imaginary part of the root
fxch      %st(7)                                    #FPU ,-b/(2a),2*a,2*a,4ac-b^2,b,a,b^2,sqrt(4ac-b^2)/(2*a)
movl      \$output6, %eax                        #print the real part of the second root
call      print_str
call      print_double
movl      \$output7, %eax
call      print_str
fxch      %st(7)                                    #FPU ,sqrt(4ac-b^2)/(2*a),2*a,2*a,4ac-b^2,b,a,b^2,-b/(2a)
fchs                                                #Changes the sign of %st(0)
call      print_double                        #print the imaginary part of the second root
movl      \$output8, %eax
call      print_str
jmp            end
equal:
flds      const5                                    #FPU ,-1,0,b,a,4ac
fmul      %st(2), %st(0)                        #FPU ,b*-1,0,b,a,4ac
flds      const1                                    #FPU ,2,b*-1,0,b,a,4ac
fmul      %st(4), %st(0)                        #FPU ,2*a,b*-1,0,b,a,4ac
fxch      %st(1)                                    #FPU ,b*-1,2*a,0,b,a,4ac
fdiv      %st(1),      %st(0)                        #FPU ,(b*-1)/(2*a),0,b,a,4ac
movl      \$output3, %eax                        #output the double root
call      print_str
call      print_double

end:

popa                  # restore registers
movl      \$0, %eax      # return program status in eax
leave                  # restore stack frame
ret
0

Commented:
Ok, that'll give us enough instructions to put the code together. Show me how to call a function with a parameter on the stack. Remember to show the function itself too. Just make it print the parameter for now.

Paul
0

Author Commented:
The C++ driver for summing two numbers. The subprogram gets the first number from 8(%ebp) and the second from 12(%ebp) and adds them together

#include <iostream>
using namespace std;
extern "C"
int sumtwo(int a, int b);

int main()
{
cout << sumtwo(2, 4) << "\n";
}

here is the subprogram written in the version of assembly that I need as well.

.globl _sumtwo
.section .text
_sumtwo:
enter   \$0, \$0
movl    8(%ebp), %eax

leave
ret

0

Commented:
Hi 00transam,

Excellent!

Here's C code that you want to implement:

int fib(int n) {
if(n <= 2)
return 1;
else
return fib(n-1) + fib(n-2);
}

So we need something like:

.globl _sumtwo
.section .text
_fibonacci:
enter   \$0, \$0
movl    8(%ebp), %eax # Get the parameter into eax.
# Is it < 3?
... # You do this but. Compare with 3 and jump to 'lessThan3' if it is.
... # Subtract 1
... # Call _fibonacci with that number.
... # Subtract another 1
... # Call _fibonacci with that number.
... # Add the two results together.
# go to end

lessThan3:
# return 1
... # you do this bit
leave
ret

I am concerned that you are not setting %ebp. Investigate this.

Paul
0

Author Commented:
Yep that is the C code I want to implement. But I don't know how I have tried with my subprogram above but I can't get it to work.  You have the correct form on your last message. But do you know how to implement it. I am having trouble with returning from a call.
0

Commented:
> I am concerned that you are not setting %ebp. Investigate this.
yeah

may be
enter   \$0, \$0
is equivalent to
PUSH EBP
MOV EBP, ESP
0

Author Commented:
it is
0

Commented:
Excellent! So if you will fill in some of the code Colt, we'll check it to make sure it's right.

Sorry we cant do it for you.

Paul
0

Author Commented:
Here is what I have so far. I am in the process of debugging it. I cannot get it to return below the call after one is made. It just goes in an infinte loop.

.globl _fibonacci

.section .text
_fibonacci:
enter \$0, \$0
fib:

pushl %ebx
subl \$4, %esp
cmpl \$2, 8(%ebp)
jg fib1
movl \$1, -8(%ebp)
jmp fib2
fib1:
movl 8(%ebp), %eax
subl \$1, %eax
pushl %eax
movl 4(%ebp), %esp
call fib
movl %eax, %ebx
movl 8(%ebp), %eax
subl \$2, %eax
pushl %eax
call fib
movl %ebx, -8(%ebp)

fib2:
movl -8(%ebp), %eax
popl %ebx
leave
ret
0

Commented:

movl %eax, %ecx     # save the number entered
subl \$1, %eax     # subtract 1 from number f(n-1)
call fib          # call fib again
movl %eax, %edx # save result for f(n-1)
movl %ecx, %eax # get original number back
subl \$2, %eax     # subtract 2 from number f(n-2)
call fib          # call fib again
jmp end          # return

you must push the parameter onto stack before calling fib

pushl %ecx
call fib

eax should not be used as a shared parameter between procedure invocations.
it is used to store the retrun value of proc
0

Commented:
use
ret 4
it will increase the esp by 4 so the 4 byte pushed parameter will be discarded
0

Author Commented:
That is an earlier version and I think you are right that I have to push the parameter on the stack befor calling fib. I will try that.
Thanks
Colt
0

Commented:
.globl _fibonacci

.section .text
_fibonacci:
enter \$0, \$0
fib:
cmpl \$2, 8(%ebp)
jg fib1
movl \$1, %eax
jmp fib2
fib1:
pushl %edx
movl 8(%ebp), %eax
subl \$1, %eax
pushl %eax
call fib
movl %eax, %edx
movl 8(%ebp), %eax
subl \$2, %eax
pushl %eax
call fib
popl %edx
fib2:
leave
ret 4
0

Author Commented:
I tried your code and it doesn't like the ret 4 so I put a addl \$4, %esp before the leave instruction and I get 0 for 1 and 0 for 2 and nothing for n>=3.  Your code looks great and to me it looks like it should work any idea why it doesn't.
0

Commented:
> I put a addl \$4, %esp before the leave instruction
I think you have to put this line after each call to fib

call fib
0

Author Commented:
I tried that and when I am debugging it never executes the line after the call I need to some how return after the call line.
0

Commented:
post your final code including any necessary thing
0

Author Commented:
Sorry to be such a pain. Here is my code that I am working with right now

.globl _fibonacci

.section .text
_fibonacci:
enter \$0, \$0
fib:

pushl %ebx
subl \$4, %esp
cmpl \$2, 8(%ebp)
jg fib1
movl \$1, -8(%ebp)
jmp fib2
fib1:
movl 8(%ebp), %eax
subl \$1, %eax
pushl %eax
movl 4(%ebp), %esp
call fib
movl %eax, %ebx
movl 8(%ebp), %eax
subl \$2, %eax
pushl %eax
call fib
movl %ebx, -8(%ebp)

fib2:
movl -8(%ebp), %eax
popl %ebx
leave
ret
0

Commented:
but its not the last code I've posted
0

Author Commented:
I am cant get the code to give me a one, I don't know what is wrong. Sorry I had too many windows open in Visual studio, copied the wrong code.

.globl _fibonacci

.section .text
_fibonacci:
enter \$0, \$0

fib:
cmpl \$2, 8(%ebp)
jg fib1
movl \$1, %eax
jmp fib2
fib1:
pushl %edx
movl 8(%ebp), %eax
subl \$1, %eax
pushl %eax
call fib
movl %eax, %edx
movl 8(%ebp), %eax
subl \$2, %eax
pushl %eax
call fib
popl %edx
fib2:
leave
ret
0

Commented:
call fib

only add esp, 4 after the call fib not before
0

Author Commented:
Ill try it
0

Author Commented:
still not working, I can't even get it to give me a 1 for 1 or 2. this doesn't make any sense.

the code

.globl _fibonacci

.section .text
_fibonacci:

enter \$0, \$0

movl 8(%ebp), %eax
fib:

cmpl \$2, %eax
jg fib1
movl \$1, %eax
jmp fib2
fib1:
pushl %edx
movl 8(%ebp), %eax
subl \$1, %eax
pushl %eax

call fib
movl %eax, %edx
movl 8(%ebp), %eax
subl \$2, %eax
pushl %eax

call fib
popl %edx
fib2:
leave
ret
0

Author Commented:
well i got it to give a 1 now but after n>3 still doesn't work here is the code changes Marked by #

.globl _fibonacci

.section .text
_fibonacci:

enter \$0, \$0

movl 8(%ebp), %eax
fib:

cmpl \$1, %eax   #
jg fib1
movl \$1, %eax
leave #
ret#
fib1:
pushl %edx
movl 8(%ebp), %eax
subl \$1, %eax
pushl %eax

call fib
movl %eax, %edx
movl 8(%ebp), %eax
subl \$2, %eax
pushl %eax

call fib
popl %edx
0

Commented:
we are doing something wrong since Im not familiar with this kind of assembly syntax
0

Author Commented:
Isn't this 8086 assembly / IA 32 (aren't these the same). I am using cygwin and a GNU compiler and assembler. Thats really all I have.
0

Commented:
not sure
Paul, what is your opinion ???
0

Commented:
should these two lines apear after fib:

fib:
enter \$0, \$0
movl 8(%ebp), %eax
0

Author Commented:
no enter \$0, \$0 is equivalent to pushl %ebp and movl %ebp, %esp.  these are needed to set up the program. The movl 8(%ebp), %eax retrieves the number entered by the user and moves it to the eax register. I know this much but not much more.
0

Author Commented:
I know i did change that part. I was just trying things in the code that I sent you here is what I have. It will go as far as 2 and when you enter 3 it craps.

.globl _fibonacci

.section .text
_fibonacci:

enter \$0, \$0

fib:

movl 8(%ebp), %eax
cmpl \$2, %eax
jg fib1
movl \$1, %eax
leave
ret
fib1:
pushl %edx
movl 8(%ebp), %eax
subl \$1, %eax
pushl %eax

call fib
movl %eax, %edx
movl 8(%ebp), %eax
subl \$2, %eax
pushl %eax

call fib
popl %edx
0

Commented:
Hi guys,

Sorry! Had to do some stuff. Back now.

I agree with hoomanv that the main problem is the stack frame handling. You must either pull the parameter out of the stack frame and then control the stack yourself or build a new stack frame after each recursion. You cant mix the two.

Here's what I mean:

_fibonacci:
enter \$0, \$0 # Builds a new stack frame.

fib:
movl 8(%ebp), %eax # Use the parameter from the stack frame.

...

call fib # This wont work because you are not creating a new stack frame.

_fibonacci:
enter \$0, \$0 # Builds a new stack frame.
movl 8(%ebp), %eax # Use the parameter from the stack frame.

fib:
# Cant use 8(%ebp) because we arent creating a new stack frame on each recursion.
...
call fib # This should work so long as transient registers are pushed.

I'd suggest something like:

_fibonacci:
enter \$0, \$0 # Builds a new stack frame.
movl 8(%ebp), %eax # Use the parameter from the stack frame.

fib:
push ax
push bx
push dx
...

call fib # This wont work because you are not creating a new stack frame.

# Remember to cleanup the stack.

I'll look at the rest of it but remember, you are probably more familliar with the language than I am.

Paul
0

Commented:
Hi 00transam,

Try the following code snippet - the catch is the stack manipulation when dealing with recursive function.

globl _fibonacci

.section .text
_fibonacci:

fib:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax

cmpl \$2, %eax
jg fib1

movl \$1, %eax
movl %ebp, %esp
popl %ebp

ret

fib1:

movl 8(%ebp), %eax
subl \$1, %eax
pushl %eax

call fib

pushl %edx
movl %eax, %edx

movl 8(%ebp), %eax
subl \$2, %eax
pushl %eax

call fib

popl %edx
movl %ebp, %esp
popl %ebp

ret
0

Author Commented:
Wow you do not know how greatful I am to you. I have been staring at this screen for 3 days now. You just gave me a break thank you very much.

I am so happy I don't know what to do

Thanks again
Colt
0

Commented:
though it had been nice if you split the points :(
most of the code was provided before PeterdLo's post
0

Author Commented:
well how can I help?   I didn't have an option on splitting points.
0

Author Commented:
is there any way to give you all 500 points
0

Commented:
unfortunately no
0

Commented:
:)
0

Author Commented:
Didn't want to make anyone mad. Thanks for all the help.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.