After coming up with a formula on this Stack Overflow question, defeating recursion limits and finding a few new ways of calculating these numbers (as per this Stack Overflow question), I decided that it was time to write up the solutions and submit them for a proper review.
For those that are not familiar with Fibonacci and more generally, Multinacci numbers, here are the rules:
- The numbers correspond to the number of pairs of rabbits at year n
- Rabbits take 1 year to mature
- Rabbits reproduce after they mature, to produce 1 (or k in the case of Multinacci) pairs of rabbits
- There is 1 pair at year 1, and none at year 0
from functools import lru_cache
limit = 100
# Classic recursive
def fibnum1(n, k=1):
"""Returns the multinacci number of order k at generation n"""
if n <= 0:
return 0
if n == 1 or n == 2:
return 1
# build up the cache as needed to defeat recursion bounds
global limit
if n > limit:
for temp_n in range(limit, n, 100):
_fibnum(temp_n, k)
limit = n + 100
return _fibnum(n, k)
# Recursive with matrix multiplication
def fibnum2(n, k=1):
"""Returns the multinacci number of order k at generation n"""
if n <= 0:
return 0
if n == 1 or n == 2:
return 1
return _matrix_fib(n, k)[1]
# Iterative
def fibnum3(n, k=1):
"""Returns the multinacci number of order k at generation n"""
if n <= 0:
return 0
fibnums = [0, 1, 1]
for i in range(3, n+1):
fibnums.append(fibnums[i-1] + k * fibnums[i-2])
return fibnums[n]
# Helper for fibnum1, memoized of course
@lru_cache(maxsize=None)
def _fibnum(n, k=1):
if n <= 0:
return 0
if n == 1 or n == 2:
return 1
return _fibnum(n-1, k) + k * _fibnum(n-2, k)
# Helper for fibnum2, memoized of course
@lru_cache(maxsize=None)
def _matrix_fib(n, k):
if n == 1:
return [0, 1]
else:
f = _matrix_fib(n // 2, k)
c = k * f[0] * f[0] + f[1] * f[1]
d = f[1] * (f[1] + 2 * k * f[0])
if n % 2 == 0:
return [c, d]
else:
return [d, k * c + d]
As you can see, there are three distinct functions here for calculating these numbers: fibnum1, fibnum2, and fibnum3. They are nearly functionally identical, as all 3 are super fast (memoization for the win!) and work for relatively big numbers quite well. fibnum2 will fail eventually (dumb recursion limit...), but it is at too large of a number to be practically reached. I would like a comparative review, along with any other comments on any aspect of the code.
