fibonacci number computing

fast_fibonacci.py

import functools
import itertools
import time


def timing(f):
    def wrap(*args):
        time1 = time.time()
        ret = f(*args)
        time2 = time.time()
        print('{:s} function took {:.3f} ms'.format(f.__name__, (time2-time1)*1000.0))

        return ret
    return wrap

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(itertools.islice(iterable, n, None), default)

@timing
def fib(n):
    a,b = 0, 1
    for _ in itertools.repeat(None, n): # 9044.029 ms
    #for _ in range(n): # 9109.824 ms
        a, b = b, a+b
    return a

@timing
def fib2(n):
    return nth(fib_gen(), n) # 9156.716 ms

def fib_gen():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b


@functools.lru_cache(None)
def fib3(n):
    """
    Решение основано на:
    http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF
    :param n:
    :return:
    """
    if n in (0, 1):
        return 1
    if n & 1:  # if n is odd, it's faster than checking with modulo
        return fib3((n + 1) // 2 - 1) * (2 * fib3((n + 1) // 2) - fib3((n + 1) // 2 - 1))
    a, b = fib3(n // 2 - 1), fib3(n // 2)
    return a ** 2 + b ** 2

@timing
def time_without_recursion(n):
    """
    в общем и целом, могу заметить, что и мой и твой подход имеют одинаковый результат
    но мне удалось найти функциональное решение, которое превосходит ожидания, 
    как я и отмечал - решение через использование кэша

    существует еще пару решений данной задачи, но на сколько я понимаю это самое быстрое
    """
    return fib3(n) # 56.736 ms


print(time_without_recursion(1000000))