### Thread: Fibonacci number program problem

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2005
Posts
15
Rep Power
0

#### Fibonacci number program problem

anyone can help me to fix my program problem? I can't output the correct number, what's the problem on my code? Help me, thanks.

Code:
```## Program to computes the value of Fibonacci number.

.text
.globl  __start

__start:

sub	\$sp,\$sp,4	# push return address
sw	\$ra,(\$sp)
sub	\$sp,\$sp,4	# push caller's frame pointer
sw	\$fp,(\$sp)
sub	\$fp,\$sp,8	# \$fp = \$sp - space_for_variables
move	\$sp,\$fp

li	\$v0,4	# call to print string
la	\$a0,pr1
syscall

li	\$v0,5	# call to read integer
syscall
sw	\$v0,0(\$fp)	# save in \$v0
nop

lw	\$a0,0(\$fp)	# load variable into \$a0
nop
jal	fib
nop

sw	\$v0,4(\$fp)	# b = fib(a)
nop

li	\$v0,4	# call to print string
la	\$a0,pr2
syscall

lw	\$a0,4(\$fp)
li	\$v0,1	# call to print integer
syscall

add	\$sp,\$fp,8	# \$sp = \$fp + space_for_variables

lw	\$fp,(\$sp)	# pop \$fp
lw	\$ra,(\$sp)	# pop \$ra
nop

.data
pr1:	.asciiz "Enter an interger:"
pr2:	.asciiz "\nThe Fibonacci number is:"

# int Fib( int n )
# {
#   if( n <= 0 )
#      return 0
#   else if( n == 1 )
#       return 1
#   else
#     x = Fib( n-1 )
#     y = Fib( n-2 )
#     return x + y
#   endif
# }

.text
.globl  fib

fib:
sub	\$sp,\$sp,4	# push return address
sw	\$ra,(\$sp)
sub	\$sp,\$sp,4	# push caller's frame pointer
sw	\$fp,(\$sp)
sub	\$sp,\$sp,4	# push register \$s1
sw	\$s1,(\$sp)
sub	\$fp,\$sp,0	# \$fp = \$sp - space_for_variables (==0)
move	\$sp,\$fp

move	\$s1,\$a0	# save argument in \$s1
li	\$t1,0	# get a==0
bgt	\$s1,\$t1,lo1	# if (n <= 0)
nop
li	\$v0,0	# return 0
j	exit
nop

lo1:
move	\$s1,\$a0	# save argument in \$s1
li	\$t1,1	# get a==1
beq	\$s1,\$t1,lo2	# if (n == 1)
nop
bgt	\$s1,\$t1,lo3	# if (n <=1)
nop

lo2:	li	\$v0,1	# return 1
j	exit
nop
lo3:
sub 	\$a0,\$s1,1	# param = n-1
jal 	fib	# compute fib(n-1)
nop
move	\$v0,\$s1	# x = Fib( n-1 )

sub	\$a0,\$s1,2	# set param to n-2
jal 	fib	# and make recursive call
nop

exit:
add	\$sp,\$fp,0	# \$sp = \$fp + space_for_variables (==0)
lw	\$s1,(\$sp)
lw	\$fp,(\$sp)	# pop \$fp
lw	\$ra,(\$sp)	# pop \$ra
nop```
2. I have no idea what language that is, but that doesn't matter. I do know that the tree-like recursion pattern you've chosen (shown in the C-like code in the comments) is rather wasteful. It will calculate lower values multiple times, which is unnecessary. The higher n is, the more redundant calculations it gets. The Fibonacci sequences is linear, you don't need a tree-like recursion to solve it.

What's best is to count up to the desired index of the sequence, rather than working your way down and then collapsing dozens of method calls. A loop is sufficient.
3. Originally Posted by LyonHaert
I have no idea what language that is, but that doesn't matter.
Just for the record, he's writing in ASM (Assembly).
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2005
Posts
15
Rep Power
0
This is MIPS assembly language program. Dose anyone have idea to fix my code? Thanks.
5. I'm sorry that I can't be of any help with the assembly. I just hope that this is just a school assignment and (if so) that they teach you afterwards why recursion is not a good solution in the context of the Fibonacci sequence.
6. Originally Posted by LyonHaert
I'm sorry that I can't be of any help with the assembly. I just hope that this is just a school assignment and (if so) that they teach you afterwards why recursion is not a good solution in the context of the Fibonacci sequence.
I don't see how using recursion in such a situation can possibly be a bad route, unless of course you could proove this to me somehow?

Take a look at this LISP code which is a recursive version of the Fibonacci sequence.

Code:
```(defun fib (n)
"Naive recursive computation of the nth element of the Fibonacci sequence"
(check-type n (integer 0 *))
(if (< n 2) n
(+ (fib (1- n)) (fib (- n 2)))))```
Now, here is an iterative version of the sequence.

Code:
```(defun fib (n)
"do-based iterative computation of the nth element of the Fibonacci sequence"
(check-type n (integer 0 *))
(do ((i n (1- i))
(f1 0 f2)
(f2 1 (+ f1 f2)))
((= i 0) f1)))```
You'll notice that the recursive version is far more expressive and much easily read and understood if one knows atleast the basics of recursion. Neither version is faster than the other, they are for the most part equal. And if this was done in C, or some other language, the recursive version will still look nicer.

I'd like to know why recursion is not a good choice here.
7. Because it results in a lot of unnecessary recursive calls. Draw it out in a diagram, see how many times fib(1) gets called:

[code=fib(5)] 5
4 3
3 2 2 1
2 1 1 1
1[/code]
The funny thing is, whatever nth number of the sequence you want, fib(n) will end up calling fib(1) the number of times of that number in the sequence. The eighth number in the sequence is 21. That's how many times fib(1) will get called, not to mention the repeated (and therefore useless) calls to fib(2), fib(3), and so on. And even if you write the condition so that fib(1) never gets called (as in your Lisp version), you can't do the same for the other calls.

(edit: Oops, it doesn't cull fib(1) calls; I misread it.)

One's not faster than the other? Have you benchmarked the iterative versus the tree-recursive form with large values of n? I was also under the impression that the Lisp compiler can often optimize recursive functions into iterations (is it just the compiler, or does the interpreter do that to? I forget).

Mind you, I'm not saying that recursion shouldn't be used for the Fibonacci sequence. Just not this form of it. You could make a recursive function that starts at the beginning of the sequence (rather than 'starting' at the unknown value you want and working your way down, and not having an answer until every path of the tree has been travelled).

It's like painting lines on a road, but leaving the bucket of paint at the beginning instead of taking it with you. With every line, you have to keep going farther and farther away from the bucket.

The eloquence of the algorithm is more important than the readability of the code, in my opinion.
Last edited by LyonHaert; April 8th, 2006 at 02:07 PM. Reason: spelling and correction
8. No Profile Picture
Redpill
Devshed Intermediate (1500 - 1999 posts)

Join Date
Nov 2005
Posts
1,657
Rep Power
154
Recursion takes up O(n^(sqrt(5)+1/2)) time AND space. Linear progression takes up O(n) space and time.

Don't care? Let me put that into hard numbers for you:

C++ code

Main
Code:
```#include <iostream>
#include <ctime>
int main()
{
int n;
std::cout << "Enter a number: ";
std::cin >> n;

int c = clock();
int r = f(n);
c = clock() - c;
std::cout << "F(" << n << ") is " << r
<< ", computed using recursion in " << c << " clock cycles.\n";
system("pause");
}```

f()
Recursive
Code:
```int f(int n)
{
if(n == 0 || n == 1) return 1;
return f(n-1) + f(n-2);
}```
Linear
Code:
```int f(int n)
{
int a[n+1];
for(int i = 0; i <= n; ++i)
{
if(i == 0)
{
a[0] = 1;
}
else if(i == 1)
{
a[1] = 1;
}
else
{
a[i] = a[i-1] + a[i-2];
}
}
return a[n];
}```

Benchmarks
Code:
```n		30		35		40		45		50
----------
fib(n)		1346269		14930352,165580141			-112588406 (overflow)
----------
Clock cycles:
Recursive	15		515	6094		~28150		~130000
Linear		0		0		0

Linear for even n = 100000 shows "0 clock cycles". The integer range has long overflowed it's bounds.

~: I can't run this anymore -- will take minutes and hours, it seems. Recursive f(n) for n = 40 hung my computer for several seconds already. Estimate given.```

There you have it. Solid proof.

#### Comments on this post

• HRDirector agrees : good way to put the pwnsauce down CS style
9. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2004
Posts
124
Rep Power
0
In a word: pwned
10. I neglected to expound on the difference in languages:

Yegg, I understand that readability and elegance of the code are tenets of Lisp, and that good practice in these usually leads to good algorithms in Lisp, too. I also understand that recursion is used a lot in Lisp programs, but I also recall that it is often tail-recursion, and linear. However, Lisp is a high-level language. I would argue that there is no such readability for assembly, therefore the point is moot.

On the point of speed, the most important thing low-level languages are good for is speed. Therefore you want to use the fastest algorithm, even in C, even if it's less readable. And with this particular algorithm, it's not even good for Lisp.

I tried the two you gave me (fibI for iterative, fibR for recursive). fibR(20) was well under a second, but from there it just starts climbing (fibR(30) took 11-12 seconds), while fibI(100000) takes under 5 seconds.

The one advantage Lisp has in these calculations is the lack of a limit on the size of an integer. Even a 64-bit unsigned integer is only good up to the 93rd number in the Fibonacci sequence (I did some C# benchmarks, fibR(49): 739590ms, while fibI(49): 0ms). No such limitation in Lisp, it calculates fibI(1000000) just fine, even if it takes a few minutes.

Unfortunately, we've kindof hijacked this thread, and nobody seems to know assembly 'round here. But the reason I made my original comments on the recursive algorithm is that -- unless that particular algorithm is required -- ok_good might be able to make a working program with a different algorithm... if the bug is in that part of his program.

#### Comments on this post

• Yegg` agrees : DIdn't think about that earlier.
11. No Profile Picture
Redpill
Devshed Intermediate (1500 - 1999 posts)

Join Date
Nov 2005
Posts
1,657
Rep Power
154
Yeah, if I'd used bignums in the C++ benchmarks the numbers might have been a bit higher.

Even in Lisp/Haskell/nice-syntax-language, would you sort an array by checking all N! permutations of the elements just because it "looks good"? A line has to be drawn between speed and elegance. The simplest solution might not always be the best one.

Want a fib(n) with bloody damn SPEED? If you complain about the "magic numbers" thing in the code, saying how it reduces "readability" and "elegance", go ahead -- use your "superior" recursive version.
Code:
```var phi = (sqrt(5) + 1) / 2;
fib(n) = (phi^n - (1 - phi)^n) / sqrt(5);```
12. For the fibonacci problem in Haskell, it is possible to use tree recursion without the combinatorial overhead because the language processor automagically memoizes the results of repeated calls - any calls for previously calculated values are replaced with a table lookup. Of course, that technically is changing the algorithm - but it does give rather good performance without loosing expressiveness. Sure, you could memoize explicitly in other languages - SICP gives this specific example of it in Scheme (Section 3.3.3, exercise 3.27) - but it wouldn't be quite so elegant anymore...

In any case, your correct that the equation version is fastest, and in a case like this, magic numbers aren't really an issue - they values are a part of the identity, and don't really have a separate conceptual meaning. However, the fibonacci function is primarily used to demonstrate tree recursion - how it works, where and when you would use it, and why you wouldn't in most cases - and as an example of O(n^2) performance vs. the O(n) linear recursive version vs. the O(log n) iterative version (again, this is exactly what is done in sections 2.2 and 2.3 of SICP). The fibonacci sequence itself doesn't come up very often in general programming, but it is related to things which do, such as tree problem-space searches.

[EDIT: I should have read the comment more carefully. Still, the point about memoization is worth mentioning.]
Last edited by Schol-R-LEA; April 8th, 2006 at 03:13 PM.
13. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1316
This thread is now in deep hijack, but I thought I'd point out that the (phi^n - (1-phi)^n)/sqrt(5) formula is not great for computation because it requires real number operations and results in a real number, unlike the other algorithms, which can produce a result in essentially any form. If you actually want an integer result or want to know a Fibonacci number mod some integer, then that formula is not suitable for large values of n. (For small values of n, it will work, though.) A better way is the following recursive algorithm. In the interest of being vaguely on-topic at least for this forum, the following is implemented in the "Other Programming Language" Ada.

Specification:
```package Fibo_Tools is
subtype Long_Natural is Long_Integer range 0..Long_Integer'Last;
type Mod_Natural is mod 2**31;

function Fibonacci(N: Natural) return Mod_Natural;
end Fibo_Tools;```
Alternative 1 (tree recursion):
```package body Fibo_Tools is
function Fibonacci (N: Long_Natural) return Mod_Natural is
begin
if (N = 0) then return 0;
elsif (N = 1) then return 1;
else return Fibonacci(N-1) + Fibonacci(N-2);
end if;
end Fibonacci;
end Fibo_Tools;```
Alternative 2 (linear iterative):
```package body Fibo_Tools is
function Fibonacci (N: Long_Natural) return Mod_Natural is
A: Mod_Natural := 0;
B: Mod_Natural := 1;
begin
for K in 1..N loop
B := B + A;
A := B - A;
end loop;
return A;
end Fibonacci;
end Fibo_Tools;```
Alternative 3 (recursive, repeated "squaring," using the formulas F(2n-1) = F(n-1)^2 + F(n)^2, F(2n) = F(n)(F(n-1) + F(n+1)), F(2n+1) = F(n)^2 + F(n+1)^2):
```package body Fibo_Tools is
type Fib_State is array (0..2) of Mod_Natural;

procedure Fib_Rec (N: in Long_Natural; X: in out Fib_State) is
begin
if (N > 0) then
Fib_Rec(N/2, X);
X(0..2) := (X(0)**2+X(1)**2, X(1)*(X(0)+X(2)), X(1)**2+X(2)**2);
if (N mod 2 = 1) then X(0..2) := (X(1), X(2), X(1)+X(2));
end if;
end if;
end Fib_Rec;

function Fibonacci (N: Long_Natural) return Mod_Natural is
X: Fib_State := (1, 0, 1);
begin
Fib_Rec(N, X);
return X(1);
end Fibonacci;
end Fibo_Tools;```
Driver program:
```with Ada.Text_Io, Ada.Command_Line, Ada.Real_Time, Fibo_Tools;
procedure Fibo is
package Nat_IO is new Ada.Text_IO.Integer_IO(Long_Natural);
package Int_IO is new Ada.Text_IO.Integer_IO(Long_Integer);

N: Long_Natural;
F_N: Mod_Natural;
Ticks: Integer;
begin
if (Ada.Command_Line.Argument_Count < 1) then
"Usage: fibo argument");
return;
end if;

declare
Arg1 : String := Ada.Command_Line.Argument(1);
Last : Positive;
begin
Nat_IO.Get(Arg1, N, Last);
end;

F_N := Fibonacci(N);

-- (using "-", "/" of Ada.Real_Time)
Ticks := (End_Time - Start_Time)/Ada.Real_Time.Tick;

Int_IO.Put(Long_Integer(F_N), 0);
Int_IO.Put(Long_Integer(Ticks), 0);
Ada.Text_IO.Put(" clock ticks elapsed");
end Fibo;```
For comparison, compiling with alternative 1 (tree recursion) with argument 40 tends to report around 43,000,000 clock ticks, taking about 43 seconds. Compiling with alternative 2 (linear iterative) tends to report 7 clock ticks for argument 30. The highest possible input argument, 2^31-1, is feasible, but it takes time, reporting around 16,000,000 clock ticks (16 seconds). With alternative 3, every allowable input (0 up to 2^31-1) is handled instantaneously (11-12 clock ticks). In terms of big-O notation, alternative 1 is O(phi^n) time (not O(n^phi), which would be considerably better ) and O(n) space; alternative 2 is O(n) time and O(1) space (in practice O(log(n)) space, though); alternative 3 is O(log(n)) time and O(log(n)) space. Basically, each successive implementation is astronomically better than the previous one.

Due to technical difficulties (I'm still learning the language), I didn't include the round(phi^n/sqrt(5)) algorithm, but as I said, it is in a way fundamentally different from the other algorithms and is less flexible.
Last edited by Lux Perpetua; April 8th, 2006 at 05:51 PM.
14. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1316
ok_good, the best thing I can suggest if you haven't solved this yet is to get a debugger program like GDB and step through your code instruction by instruction and see where things start to go wrong.