Fibonacci algorithms

_explain.md

For my current Computer Science class, our teacher gave us the Java algorithm fib(int n) and told us to replicate it in MIPS assembly. I thought I could do a better algorithm, and thus, I created ofib(int n) in MIPS assembly and created a Java version as well.

If my calculations are correct, the provided fib takes n*7 instructions to calculate the nth Fibonacci number (with my MIPS translation anyway: I tried my best to optimize the assembly within the algorithm), where my ofib takes n*5 instructions (and I'm pretty sure that this is the best implementation of this algorithm as I optimized it for the assembly level directly).

I would not have been able to write ofib without the insight optimizing fib gave me. As such I understand why fib was given as the example, as its algorithm is easier to follow. However, I wanted to go deeper optization.

This was done as a fun exercise. I don't know if this is the best algorithm, or even if it has any gain in a high-level world, but I had fun seeing how small/quick I could get the Fibbonacci generator to be.

In fact, I know I could get at least marginally more efficiency by treating everything as unsigned 32-bit integers. However, sticking to the prompt I'm sticking to signed. (At that point overflow would be happening a long time ago anyway.)

fibTest.asm

# The given algorithm
fib:
  slt 	$v0, $zero, $a0     # v0 = 1 if a0 > 0
  beq 	$v0, $zero, fib_r   # if a0 <= 0 return 0
  li  	$t0, 0              # t0 <- a = 0
  # already because of slt  # v0 <- b = 1 
  li  	$t1, 2              # t1 <- i = 2
fib_while:
  slt 	$t9, $a0, $t1       # if (n < i) [!(i <= n)]
  bne 	$t9, $zero, fib_r   #   break fib_while
  add 	$t2, $t0, $v0       # t2 <- c = a + b
  move	$t0, $v0            # t0 <- b
  move	$v0, $t2            # v0 <- c
  addi	$t1, 1              # t1 <- ++i
  j   	fib_while           # repeat
fib_r:
  jr  	$ra                 # return v0 [b]

# My algorithm
ofib:
  slt   $v0, $zero, $a0     # v0 = 1 if a0 > 0
  beq   $v0, $zero, ofib_r  # if a0 <= 0 return 0
  li    $t0, 0              # t0[last]=0, v0[head]=1
ofib_while:
  addi  $a0, -1             # n--
  beq   $a0, $zero, ofib_r  # break if n=0
  add   $v0, $v0, $t0       # head = head + last
  sub   $t0, $v0, $t0       # last = head - last
  j     offib_while         # repeat
ofib_r:
  jr    $ra                 # return v0 [head]

fibTest.java

class fibTest
{
	// The given algorithm
	int fib(int n)
	{
		int a = 0, b = 1, c, i;
		if( n <= 0)
			return a;
		for (i = 2; i <= n; i++)
		{
			c = a + b;
			a = b;
			b = c;
		}
		return b;
	}
	
	// My algorithm
	int ofib(int n)
	{
		if (n<=0) return 0;
		int last=0, head=1;
		for (--n; n!=0; --n) {
			head = head + last;
			last = head - last;
		}
		return head;
	}
}