Convolutional Fibonacci Numbers

README.md

$$f(0)=0;; f(1)=1;; f(n) = f(n-1) + f(n-2)$$

$$f^{(m)}(n) = \sum_{i=0}^{n} f(i) * f^{(m-1)}(n-i)$$

convfib.py

"""
Convolutional Fibonacci Numbers with Caching/History
"""

class ConvFib:
  DEFAULT_CACHE = {(0,0):0, (0,1):1}
  def __init__(self):
    self.cache = self.DEFAULT_CACHE

  def _fibonacci(self, n):
    for i in range(2, n+1):
      if (0,i) not in self.cache:
        self.cache[(0,i)] = self.cache[(0,i-1)] + self.cache[(0,i-2)]
    return self.cache[(0,n)]

  def _calc_new(self, m, n):
    if m == 0:
      return self._fibonacci(n)
    else:
      return sum(self(0,i) * self(m-1, n-i) for i in range(n))

  def __call__(self, m:int, n:int):
    if (m,n) in self.cache:
      return self.cache[(m,n)]
    else:
      self.cache[(m,n)] = self._calc_new(m,n)
      return self.cache[(m,n)]

  def clear(self):
    self.cache = self.DEFAULT_CACHE

if __name__ == '__main__':
  cf = ConvFib()
  print(cf(50, 55), '=387855')