#!/usr/bin/python

from math import sqrt, pow, floor

def fibonacci(n):
	"""Computes the Nth fibonacci number.

	Uses a simple iterative approach."""

	f0 = 1
	f1 = 1
	ni = 0

	while ni < n - 1:
		t = f0 + f1
		f0 = f1
		f1 = t
		ni = ni + 1
	return f1


def recursive_fibonacci(n):
	"""Computes the Nth fibonacci number.

	Uses a simple recursive approach, and thus 
	is only really useful for small values of n."""


	if n < 0:
		return 0 
	if n == 0 or n == 1:
		return 1
	return recursive_fibonacci(n-1) + recursive_fibonacci(n-2)
	

fibo = [1, 1]
def memoizing_fibonaccin): 
	"""Computes the Nth fibonacci number.

	Uses a memoization table to record previously
	recorded values to reduce redundant computation."""

	if len(fibo) > n:
		return fibo[n] 
	t = memoizing_fibonacci(n-1) + memoizing_fibonacci(n-2)
	fibo.append(t); 
	return t


def smart_fibonacci(n):
	"""Computes the Nth fibonacci number.

	Uses the closed mathematical form to translate 
	the problem into a simple equation."""

	sqrt5 = sqrt(5)
	inv_sqrt5 = 1 / sqrt(5)
	phi = (1 + sqrt5) / 2
	phi_hat = 1 - phi 
	return int(inv_sqrt5 * (pow(phi, n+1) - pow(phi_hat, n+1)))

# Test out the functions
i = 0
while i < 30:
	print "I:", i, " ", fibonacci(i)
	print "R:", i, " ", recursive_fibonacci(i)
	print "M:", i, " ", memoizing_fibonacci(i)
	print "S:", i, " ", smart_fibonacci(i)
	print 
	i = i + 1