Project Euler #25

di = {}  # Memoize


def fib(n):
    if n <= 2:
        return 1
    else:
        if di.get(n):
            return di[n]
        else:
            result = fib(n - 1) + fib(n - 2)
            di[n] = result
            return result

################################################
# Or you can use existing function: lru_cache ##
################################################

# from functools import lru_cache
# @lru_cache(maxsize=None)
# def fib(n):
#     if n <= 2:
#         return n
#     return fib(n - 1) + fib(n - 2)

def main():
    i = 0
    while True:
        i += 1
        if len(str(fib(i))) == 1000:
            return i


if __name__ == '__main__':
    main()


In [35]: %time main()
CPU times: user 45.9 ms, sys: 63 µs, total: 45.9 ms
Wall time: 45.1 ms
Out[35]: 4782