00transam
asked on
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
addl %edx, %eax # add f(n-1) to f(n-2)
jmp end # return
end:
popl %ecx
popl %edx
leave
ret
Thanks for any help
#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
addl %edx, %eax # add f(n-1) to f(n-2)
jmp end # return
end:
popl %ecx
popl %edx
leave
ret
Thanks for any help
StillUnAware
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?
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;
}
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;
}
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
ADD EBX, EAX
MOV [EBP-8], EBX
L2:
MOV EAX, [EBP-8]
ADD ESP, 4
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);
}
/******************/
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
ADD EBX, EAX
MOV [EBP-8], EBX
L2:
MOV EAX, [EBP-8]
ADD ESP, 4
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);
}
ASKER
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.
because we are in Assembly TA.
what language do you want it to be ?
what language do you want it to be ?
ASKER
IA-32 Assembly
thanks
thanks
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
ADD EBX, EAX
L2:
MOV EAX, EBX
POP EBX
POP EBP
RET 4
fib endp
please convert it to IA-32 and let me see the code
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
ADD EBX, EAX
L2:
MOV EAX, EBX
POP EBX
POP EBP
RET 4
fib endp
please convert it to IA-32 and let me see the code
ASKER
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
ADDl %EaX, %EbX
MOVl %ebx, -8(%ebp)
L2:
MOVl -8(%ebp), %EAX
ADDl $4, %ESP
POPl %EBX
POPl %EBP
RET
.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
ADDl %EaX, %EbX
MOVl %ebx, -8(%ebp)
L2:
MOVl -8(%ebp), %EAX
ADDl $4, %ESP
POPl %EBX
POPl %EBP
RET
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
In x86 assembler,
EBP is a stack frame base pointer register.
EAX/EBX are work registers.
ESP is the stack pointer register.
Paul
ASKER
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
Colt
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
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
ASKER
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
call read_double #read number FPU = ,a,
fst %st(3) #FPU ,a, , ,a,
movl $prompt2, %eax #prompt user to enter b
call print_str
call read_double #read number FPU = ,b, , ,a,
fst %st(2) #FPU ,b, ,b,a,
movl $prompt3, %eax #prompt user to enter c
call print_str
call read_double #read number FPU = ,c, ,b,a,
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
addl $8, %esp #Adds 8 to the CPU stack
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
fmul %st(3), %st(0) #FPU ,2*a,b-sqrt(b^2-4ac),b,a,4
fxch %st(1) #FPU ,b-sqrt(b^2-4ac),2*a,b,a,4
fdiv %st(1), %st(0) #FPU ,b-sqrt(b^2-4ac)/(2*a),2*a
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
flds const5 #FPU ,-1,sqrt(b^2-4ac),2*a,b,a,
fmul %st(3), %st(0) #FPU ,b*-1,sqrt(b^2-4ac),2*a,b,
fsub %st(1), %st(0) #FPU ,(b*-1)-sqrt(b^2-4ac),sqrt
fdiv %st(2), %st(0) #FPU ,((b*-1)-sqrt(b^2-4ac))/(2
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,
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/(2
ffreep %st(0) #FPU ,2*a,4ac-b^2,b,a,4ac,-b/(2
flds const3 #FPU ,1,2*a,4ac-b^2,b,a,4ac,-b/
fmul %st(3), %st(0) #FPU ,1*b,2*a,4ac-b^2,b,a,4ac,-
fmul %st(3), %st(0) #FPU ,b^2,2*a,4ac-b^2,b,a,4ac,-
fxch %st(5) #FPU ,4ac,2*a,4ac-b^2,b,a,b^2,-
fsub %st(5), %st(0) #FPU ,4ac-b^2,2*a,4ac-b^2,b,a,b
fsqrt #FPU ,sqrt(4ac-b^2),2*a,4ac-b^2
flds const1 #FPU ,2,sqrt(4ac-b^2),2*a,4ac-b
fmul %st(5), %st(0) #FPU ,2*a,sqrt(4ac-b^2),2*a,4ac
fxch %st(1) #FPU ,sqrt(4ac-b^2),2*a,2*a,4ac
fdiv %st(1), %st(0) #FPU ,sqrt(4ac-b^2)/(2*a),2*a,2
call print_double #print the imaginary part of the root
fxch %st(7) #FPU ,-b/(2a),2*a,2*a,4ac-b^2,b
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
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
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
call read_double #read number FPU = ,a,
fst %st(3) #FPU ,a, , ,a,
movl $prompt2, %eax #prompt user to enter b
call print_str
call read_double #read number FPU = ,b, , ,a,
fst %st(2) #FPU ,b, ,b,a,
movl $prompt3, %eax #prompt user to enter c
call print_str
call read_double #read number FPU = ,c, ,b,a,
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
addl $8, %esp #Adds 8 to the CPU stack
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
fmul %st(3), %st(0) #FPU ,2*a,b-sqrt(b^2-4ac),b,a,4
fxch %st(1) #FPU ,b-sqrt(b^2-4ac),2*a,b,a,4
fdiv %st(1), %st(0) #FPU ,b-sqrt(b^2-4ac)/(2*a),2*a
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
flds const5 #FPU ,-1,sqrt(b^2-4ac),2*a,b,a,
fmul %st(3), %st(0) #FPU ,b*-1,sqrt(b^2-4ac),2*a,b,
fsub %st(1), %st(0) #FPU ,(b*-1)-sqrt(b^2-4ac),sqrt
fdiv %st(2), %st(0) #FPU ,((b*-1)-sqrt(b^2-4ac))/(2
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,
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/(2
ffreep %st(0) #FPU ,2*a,4ac-b^2,b,a,4ac,-b/(2
flds const3 #FPU ,1,2*a,4ac-b^2,b,a,4ac,-b/
fmul %st(3), %st(0) #FPU ,1*b,2*a,4ac-b^2,b,a,4ac,-
fmul %st(3), %st(0) #FPU ,b^2,2*a,4ac-b^2,b,a,4ac,-
fxch %st(5) #FPU ,4ac,2*a,4ac-b^2,b,a,b^2,-
fsub %st(5), %st(0) #FPU ,4ac-b^2,2*a,4ac-b^2,b,a,b
fsqrt #FPU ,sqrt(4ac-b^2),2*a,4ac-b^2
flds const1 #FPU ,2,sqrt(4ac-b^2),2*a,4ac-b
fmul %st(5), %st(0) #FPU ,2*a,sqrt(4ac-b^2),2*a,4ac
fxch %st(1) #FPU ,sqrt(4ac-b^2),2*a,2*a,4ac
fdiv %st(1), %st(0) #FPU ,sqrt(4ac-b^2)/(2*a),2*a,2
call print_double #print the imaginary part of the root
fxch %st(7) #FPU ,-b/(2a),2*a,2*a,4ac-b^2,b
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
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
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
Paul
ASKER
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
addl 12(%ebp), %eax
leave
ret
#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
addl 12(%ebp), %eax
leave
ret
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
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
ASKER
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.
> 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
yeah
may be
enter $0, $0
is equivalent to
PUSH EBP
MOV EBP, ESP
ASKER
it is
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
Sorry we cant do it for you.
Paul
ASKER
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
addl %eax, %ebx
movl %ebx, -8(%ebp)
fib2:
movl -8(%ebp), %eax
addl $4, %esp
popl %ebx
leave
ret
.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
addl %eax, %ebx
movl %ebx, -8(%ebp)
fib2:
movl -8(%ebp), %eax
addl $4, %esp
popl %ebx
leave
ret
according to your own code
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
addl %edx, %eax # add f(n-1) to f(n-2)
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
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
addl %edx, %eax # add f(n-1) to f(n-2)
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
use
ret 4
it will increase the esp by 4 so the 4 byte pushed parameter will be discarded
ret 4
it will increase the esp by 4 so the 4 byte pushed parameter will be discarded
ASKER
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
Thanks
Colt
.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
addl %edx, %eax
popl %edx
fib2:
leave
ret 4
.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
addl %edx, %eax
popl %edx
fib2:
leave
ret 4
ASKER
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.
> 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
addl $4, %esp
I think you have to put this line after each call to fib
call fib
addl $4, %esp
ASKER
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.
post your final code including any necessary thing
ASKER
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
addl %eax, %ebx
movl %ebx, -8(%ebp)
fib2:
movl -8(%ebp), %eax
addl $4, %esp
popl %ebx
leave
ret
.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
addl %eax, %ebx
movl %ebx, -8(%ebp)
fib2:
movl -8(%ebp), %eax
addl $4, %esp
popl %ebx
leave
ret
but its not the last code I've posted
ASKER
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
addl $4, %esp
call fib
addl $4, %esp
movl %eax, %edx
movl 8(%ebp), %eax
subl $2, %eax
pushl %eax
addl $4, %esp
call fib
addl $4, %esp
addl %edx, %eax
popl %edx
fib2:
#addl $4, %esp
leave
ret
.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
addl $4, %esp
call fib
addl $4, %esp
movl %eax, %edx
movl 8(%ebp), %eax
subl $2, %eax
pushl %eax
addl $4, %esp
call fib
addl $4, %esp
addl %edx, %eax
popl %edx
fib2:
#addl $4, %esp
leave
ret
addl $4, %esp
call fib
addl $4, %esp
only add esp, 4 after the call fib not before
call fib
addl $4, %esp
only add esp, 4 after the call fib not before
ASKER
Ill try it
ASKER
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
addl $4, %esp
movl %eax, %edx
movl 8(%ebp), %eax
subl $2, %eax
pushl %eax
call fib
addl $4, %esp
addl %edx, %eax
popl %edx
fib2:
leave
ret
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
addl $4, %esp
movl %eax, %edx
movl 8(%ebp), %eax
subl $2, %eax
pushl %eax
call fib
addl $4, %esp
addl %edx, %eax
popl %edx
fib2:
leave
ret
ASKER
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
addl $4, %esp
movl %eax, %edx
movl 8(%ebp), %eax
subl $2, %eax
pushl %eax
call fib
addl $4, %esp
addl %edx, %eax
popl %edx
.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
addl $4, %esp
movl %eax, %edx
movl 8(%ebp), %eax
subl $2, %eax
pushl %eax
call fib
addl $4, %esp
addl %edx, %eax
popl %edx
we are doing something wrong since Im not familiar with this kind of assembly syntax
it'll help if you refer us to some site about this architecture
it'll help if you refer us to some site about this architecture
ASKER
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.
not sure
Paul, what is your opinion ???
Paul, what is your opinion ???
should these two lines apear after fib:
fib:
enter $0, $0
movl 8(%ebp), %eax
fib:
enter $0, $0
movl 8(%ebp), %eax
ASKER
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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
addl $4, %esp
movl %eax, %edx
movl 8(%ebp), %eax
subl $2, %eax
pushl %eax
call fib
addl $4, %esp
addl %edx, %eax
popl %edx
.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
addl $4, %esp
movl %eax, %edx
movl 8(%ebp), %eax
subl $2, %eax
pushl %eax
call fib
addl $4, %esp
addl %edx, %eax
popl %edx
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
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
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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
I am so happy I don't know what to do
Thanks again
Colt
though it had been nice if you split the points :(
most of the code was provided before PeterdLo's post
most of the code was provided before PeterdLo's post
ASKER
well how can I help? I didn't have an option on splitting points.
ASKER
is there any way to give you all 500 points
unfortunately no
:)
ASKER
Didn't want to make anyone mad. Thanks for all the help.