Fibonacci Number

# python standard library
from datetime import (
    datetime,
    timedelta,
    )
import random

# third party
from joblib import Memory

def time_it(implementation, tag, input_value, expected, max_time=MAX_TIME):
    """Times the implementation

    Args: 
     implementation: callable to pass input_value to
     tag (str): identifier to add to the output
     input_value (int): the number to pass to the implementation
     expected (int): the expected value
     max_time (float): number of seconds allowed

    Raises:
	AssertionError: wrong value or took too long
    """
    assert input_value <= MAX_INPUT, "n too large: {}, max allowed: {}".format(input_value,
									       MAX_INPUT)
    start = datetime.now()
    print("Starting {}".format(tag))
    actual = implementation(input_value)
    assert actual == expected, "Actual: {} Expected: {}".format(
	    actual, expected)
    elapsed = datetime.now() - start
    print("({}) Okay Elapsed time: {}".format(tag, elapsed))
    assert elapsed <= max_time, "Time Greater than {}".format(max_time)
    return

def calculate_fibonacci_recursive(n):
    """Calculates the nth fibonacci number

    Args:
     n (int): the fibonacci number to get (e.g. 3 means third)

    Returns:
     int: nth fibonacci number
    """
    if (n <= 1):
	return n
    return (calculate_fibonacci_recursive(n - 1)
	    + calculate_fibonacci_recursive(n - 2))

time_it(calculate_fibonacci_recursive, "Recursive", 10, 55)

memory = Memory(location="memories")

@memory.cache
def reference_implementation(n):
    """Calculates the nth fibonacci number

    Args:
     n (int): the fibonacci number to get (e.g. 3 means third)

    Returns:
     int: nth fibonacci number
    """
    if (n <= 1):
	return n
    return (calculate_fibonacci_recursive(n - 1)
	    + calculate_fibonacci_recursive(n - 2))

def time_once(implementation, n):
    """Runs the implementation once

    Args:
     implementation: callable to pass input
     n: value to pass to the implementation

    Returns:
     output of implementation
    """
    start = datetime.now()
    output = implementation(n)
    print("Elapsed: {}".format(datetime.now() - start))
    return output

def run_range(n):
    """run the reference implementation n times

    Args:
     n (int): number of times to run the reference implementation
    """
    start = datetime.now()
    for input_value in range(n):
	output = reference_implementation(input_value)
    return 

for endpoint in range(0, MAX_INPUT + 1, 10):
    print("endpoint: {}".format(endpoint))
    for n in range(endpoint):
	run_range(n)

time_once(reference_implementation, 45)

class Tester:
    """Class to test the implementation

    Args: 
     implementation: callable to pass input_value to
     tag (str): identifier to add to the output
     iterations (int): number of times to run the testing
     verbose (bool): if true, emit more text
     max_time (float): number of seconds allowed
    """
    def __init__(self, implementation, tag, iterations,
		 verbose=False,
		 max_time=MAX_TIME):
	self.implementation = implementation
	self.tag = tag
	self.max_time = max_time
	self.verbose = verbose
	self.iterations = iterations
	return

    def output(self, statement):
	"""prints the statement if verbose is on"""
	if self.verbose:
	    print(statement)

    def time_it(self, input_value):
	"""Times the implementation

	.. warning:: This uses the ``reference_implementation`` to get the
	   expected value. Make sure it's implemented and the values are cached

	Args:
	 input_value (int): input for the implementation
	Raises:
	 AssertionError: wrong value or took too long
	"""
	start = datetime.now()
	self.output("Starting {}".format(self.tag))
	expected = reference_implementation(input_value)
	actual = self.implementation(input_value)
	assert actual == expected, "n: {} Actual: {} Expected: {}".format(
	    input_value, actual, expected)
	elapsed = datetime.now() - start
	self.output("({}) Okay Elapsed time: {}".format(self.tag, elapsed))
	assert elapsed <= self.max_time, "Time Greater than {}".format(self.max_time)
	return

    def __call__(self):
	"""Generates random numbers and times it"""
	start = datetime.now()
	print("***** {} *****".format(self.tag))
	for iteration in range(self.iterations):
	    n = random.randrange(MAX_INPUT + 1)
	    self.output("n: {}".format(n))
	    self.time_it(n)
	print("Total Elapsed: {}".format(datetime.now()))
	return            

def fibonacci_iterative(n):
    """Calculates the nth fibonacci number

    Args:
     n (int): the fibonacci number to get (e.g. 3 means third)

    Returns:
     int: nth fibonacci number
    """
    first = (0, 1)
    if n in first:
	return n
    previous, current = first
    for index in range(2, n + 1):
	previous, current = current, previous + current
    return current

test = Tester(fibonacci_iterative, "Iterative", 1000)
test()

f_0 = fibonacci_iterative(45)
f_1 = reference_implementation(45)
print(f_0)
print(f_1)
assert f_0 == f_1