Help with Fibonacci in MIPS

[VictorK19]

I'm really new to MIPS, so I'm having a hard time reading and understanding the code. For my homework, I was asked to identify and corrects errors in the folllowing code which computes the fibonacci number with given n passed in register $a0, and return it in $v0. I was most of the time lost in the middle, while trying to to follow the flow control ... Could you help me figure out the errors? Or just simply help me with the actual correct piece of code, so I can work on that and find the errors in this one.

FIB:      addi $sp, $sp, –12
          sw $ra, 0($sp)
          sw $s1, 4($sp)
          sw $a0, 8($sp)
          slti $t0, $a0, 1
          beq $t0, $0, L1
          addi $v0, $a0, $0
          j EXIT
L1:       addi $a0, $a0, –1
          jal FIB
          addi $s1, $v0, $0
          addi $a0, $a0, –1
          jal FIB
          add $v0, $v0, $s1
EXIT:     lw $ra, 0($sp)
          lw $a0, 8($sp)
          lw $s1, 4($sp)
          addi $sp, $sp, 12
          jr $ra

[turboscrew]

I added some comments in your code, maybe you see...

FIB:
          # make stack frame
          addi $sp, $sp, –12
          sw $ra, 0($sp)    # return address
          sw $s1, 4($sp)    # temporary storage?
          sw $a0, 8($sp)    # parameter

          # Check if bottom of recursion
          slti $t0, $a0, 1
          beq $t0, $0, L1   # = bne $a0, $0, L1: if param == 0, continue, else goto L1
          addi $v0, $a0, $0 # Move param to v0
          j EXIT        

L1:
          # Call FIB(param - 1)
          addi $a0, $a0, –1
          jal FIB       # What, do you think, happens to v0 here?

      # store v0 to s1
          addi $s1, $v0, $0

          # Call FIB(param - 2)  
          addi $a0, $a0, –1
          jal FIB

          # restore v0 from s1
          add $v0, $v0, $s1

          # Delete stack frame and eturn fron call
EXIT:     lw $ra, 0($sp)    # return address
          lw $a0, 8($sp)    # parameter
          lw $s1, 4($sp)    # temporary storage?
          addi $sp, $sp, 12
          jr $ra

[rubberman]

The comments that turboscrew put in your code should help. Computing fibonacci sequences is typically done with a recursive algorithm. IE: fib(x) = fib(x-1) + fib(x-2) with x==1 being the limiting factor that causes the loop to terminate. IE, fib(1) == 1, and fib(0) == 0, so fib(2) == 1 (fib(1) + fib(0)), and fib 3 == 2 (fib(2) + fib(1)), and fib(4) == 3 (fib(3) + fib(2)), fib(5) == 5, fib(6) == 8, fib(7) == 13, etc. ad infinitum... :-)

Here is a link to the wikipedia page about fibonacci numbers: http://en.wikipedia.org/wiki/Fibonacci_number

FWIW, stack overflow is not usually an issue with computing fibonacci numbers, but the usual limiting factor is the size of integer you are using. A 32-bit number will overflow after computing fib(24) or thereabouts (I don't remember exactly - my last coding of fibonacci was almost 30 years ago). A 64-bit value will give you a few more iterations before overflowing, although there are arbitrary precision math packages, such as boost, that will overcome this limitation, at a performance price. :-)

[turboscrew]

The code reminded me about when me and my friend wrote Ackerman function for a PDP 11/70 in the school. When it was run,everyone else's work went to pretty much stand-still. The other users didn't like. :-)

[rubberman]

As an interesting side note, here is a recent TED talk about Fibonacci numbers. :-)

http://www.ted.com/talks/arthur_benjamin_the_magic_of_fibonacci_numbers.html

[turboscrew]

Thanks for sharing, rubberman. Fascinating!