#1
  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
    	add	$sp,$sp,4
    	lw	$ra,($sp)	# pop $ra
    	add	$sp,$sp,4
    	jr	$ra	# return to OS
    	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
    	add 	$v0,$v0,$s1# add fib(n-2)
    
    exit:
    	add	$sp,$fp,0	# $sp = $fp + space_for_variables (==0)
    	lw	$s1,($sp)
    	add	$sp,$sp,4
    	lw	$fp,($sp)	# pop $fp
    	add	$sp,$sp,4
    	lw	$ra,($sp)	# pop $ra
    	add	$sp,$sp,4
    	jr	$ra	# return to OS
    	nop
  2. #2
  3. Arcane Scribbler
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2005
    Location
    Indianapolis, IN
    Posts
    1,907
    Rep Power
    585
    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.
    Joel B Fant
    "An element of conflict in any discussion is a very good thing. Shows everybody's taking part, nobody left out. I like that."

    .NET Must-Haves
    Tools: Reflector
    References: Threading in .NET
  4. #3
  5. Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Dec 2004
    Location
    Meriden, Connecticut
    Posts
    1,797
    Rep Power
    154
    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).
  6. #4
  7. 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.
  8. #5
  9. Arcane Scribbler
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2005
    Location
    Indianapolis, IN
    Posts
    1,907
    Rep Power
    585
    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.
    Joel B Fant
    "An element of conflict in any discussion is a very good thing. Shows everybody's taking part, nobody left out. I like that."

    .NET Must-Haves
    Tools: Reflector
    References: Threading in .NET
  10. #6
  11. Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Dec 2004
    Location
    Meriden, Connecticut
    Posts
    1,797
    Rep Power
    154
    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.
  12. #7
  13. Arcane Scribbler
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2005
    Location
    Indianapolis, IN
    Posts
    1,907
    Rep Power
    585
    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
    Joel B Fant
    "An element of conflict in any discussion is a very good thing. Shows everybody's taking part, nobody left out. I like that."

    .NET Must-Haves
    Tools: Reflector
    References: Threading in .NET
  14. #8
  15. No Profile Picture
    Redpill
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Nov 2005
    Posts
    1,660
    Rep Power
    151
    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
    Code:
    #include <stdio.h>
    int main(int o,char**O){return o>-1?o-2||!main(-1,1+O)?!!fprintf(stderr,"%s [0-"
    "9]{81}\n",*O):main(-83,++O):o>-83?(*O)[-1-o]?81==(o=-o-1)||o[*O]<'0'||'9'<o[*O]
    ?0:main(-2-o,O):o==-82:o>-164?(*O)[-83-o]<'1'?main(o-82,O):main(--o,O):o+164?o>-
    246?(*O)[-165-o]<'1'?main(o-82,O):main(--o,O):o+246?o>-328?(*O)[o=-o-247]<='8'?(
    main(-328-o,(++o[*O],O)),main(-247-o,O)):!(o[*O]='0'):(o=-o-328)<729?(o%9/3*3-o%
    27+o/243*9+o/81%3&&(*O)[o%81]==(*O)[o%81-o%27+o%9/3*3+o/243*9+o/81%3])||(o%81-o%
    9-o/81*9&&(*O)[o%81]==(*O)[o%9+o/81*9])||(o/81-o%9&&(*O)[o%81]==(*O)[o%81-o%9+o/
    81])?0:main(-409-o,O):main(-165-o%81,O):!puts(*O):0                           ;}
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2004
    Posts
    124
    Rep Power
    0
    In a word: pwned
  18. #10
  19. Arcane Scribbler
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2005
    Location
    Indianapolis, IN
    Posts
    1,907
    Rep Power
    585
    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.
    Joel B Fant
    "An element of conflict in any discussion is a very good thing. Shows everybody's taking part, nobody left out. I like that."

    .NET Must-Haves
    Tools: Reflector
    References: Threading in .NET
  20. #11
  21. No Profile Picture
    Redpill
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Nov 2005
    Posts
    1,660
    Rep Power
    151
    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);
    Code:
    #include <stdio.h>
    int main(int o,char**O){return o>-1?o-2||!main(-1,1+O)?!!fprintf(stderr,"%s [0-"
    "9]{81}\n",*O):main(-83,++O):o>-83?(*O)[-1-o]?81==(o=-o-1)||o[*O]<'0'||'9'<o[*O]
    ?0:main(-2-o,O):o==-82:o>-164?(*O)[-83-o]<'1'?main(o-82,O):main(--o,O):o+164?o>-
    246?(*O)[-165-o]<'1'?main(o-82,O):main(--o,O):o+246?o>-328?(*O)[o=-o-247]<='8'?(
    main(-328-o,(++o[*O],O)),main(-247-o,O)):!(o[*O]='0'):(o=-o-328)<729?(o%9/3*3-o%
    27+o/243*9+o/81%3&&(*O)[o%81]==(*O)[o%81-o%27+o%9/3*3+o/243*9+o/81%3])||(o%81-o%
    9-o/81*9&&(*O)[o%81]==(*O)[o%9+o/81*9])||(o/81-o%9&&(*O)[o%81]==(*O)[o%81-o%9+o/
    81])?0:main(-409-o,O):main(-165-o%81,O):!puts(*O):0                           ;}
  22. #12
  23. Commie Mutant Traitor
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2004
    Location
    Alpharetta, GA
    Posts
    1,806
    Rep Power
    1570
    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.
    Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF
    #define KINSEY (rand() % 7) λ Scheme is the Red Pill
    Scheme in Short Understanding the C/C++ Preprocessor
    Taming Python A Highly Opinionated Review of Programming Languages for the Novice, v1.1

    FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov
  24. #13
  25. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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:
    Ada Code:
    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):
    Ada Code:
    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):
    Ada Code:
    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):
    Ada Code:
    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:
    Ada Code:
    with Ada.Text_Io, Ada.Command_Line, Ada.Real_Time, Fibo_Tools;
    use Fibo_Tools, Ada.Real_Time;
    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;
        Start_Time: Ada.Real_Time.Time;
        End_Time: Ada.Real_Time.Time;
        Ticks: Integer;
    begin
        if (Ada.Command_Line.Argument_Count < 1) then
            Ada.Text_IO.Put_Line(
                Ada.Text_IO.Standard_Error,
                "Usage: fibo argument");
            return;
        end if;
     
        declare
            Arg1 : String := Ada.Command_Line.Argument(1);
            Last : Positive;
        begin
            Nat_IO.Get(Arg1, N, Last);
        end;
     
        Start_Time := Ada.Real_Time.Clock;
        F_N := Fibonacci(N);
        End_Time := Ada.Real_Time.Clock;
     
        -- (using "-", "/" of Ada.Real_Time)
        Ticks := (End_Time - Start_Time)/Ada.Real_Time.Tick;
     
        Int_IO.Put(Long_Integer(F_N), 0);
        Ada.Text_IO.New_Line(1);
        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.
  26. #14
  27. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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.

IMN logo majestic logo threadwatch logo seochat tools logo