Best strategy with limited ability of memoization

Question

Background

The algorithm to calculate the n-th Fibonacci number using recursion is as follows:

def Fib(n):
 if n == 0:
 return 0
 if n == 1:
 return 1
 
 return Fib(n-1) + Fib(n-2)

The time complexity is $O(\phi^{n})$, where $\phi = 1.618$. The problem with this approach is that it recalculates the same Fibonacci numbers many times.

Naturally, we can optimize the algorithm using memoization. The core idea is to store each Fibonacci number the first time it's calculated, so that the next time we count it, we can retrieve it directly.

This is the code:

memory = {}
memory[0] = 0
memory[1] = 1
def Fib(n):
 if n in memory:
 return memory[n]
 memory[n] = fib(n-1) + fib(n-2)
 return memory[n]

In the above algorithm, we have infinite memory to store the calculated number.

Question

This is a question from my teacher but i can not solve it.

I am not calculating Fibonacci numbers bottom-up. I am specifically evaluating it using the recursive definition, and I want to reduce the number of recomputations by caching values.

However, the cache can only store 2m Fibonacci results at any time and I need to compute Fib(n) where n >> 2m.

Which values Fib(k) should be stored in the cache to minimize total recomputation cost?

This is equivalent to choosing a subset S of size 2m, so that calling:

def Fib(n):
 if n in S: return stored
 return Fib(n-1) + Fib(n-2)

has minimal time complexity.

What is the optimal strategy for selecting S?

• greybeard: What are strategies to consider? How do you gauge the suitability of any given strategy?
• greybeard: Does the best strategy change using return Fib(n-2) + Fib(n-1)?

Answer 1

I don't have a clear answer, I will just write some ideas that came to my mind that may be useful.

You can think of $S$ as $m$ hubs each consists of two consecutive numbers, and these hubs should be spaced so they cover a wide range.

Hubs should consists of two consecutive numbers to guarantee that no Fibonacci number need to compute any value before that hub, i.e., if we have the hub $F(k), F(k+1)$ then, $F(k+2)=F(k+1)+F(k)$, and $F(k+3)=F(k+2)+F(k+3)$... In contrast, if we use hubs with only one number, then we will need to compute values before it, i.e., if we have the hub $F(k)$, then $F(k+1)=F(k)+F(k-1)$, which is not be a great deal.

The main effect on the complexity is the distribution of the hubs on the number line. Here let what determine the spacing is Spacing function. You may choose a linear spacing function, that but a constant space between every two hubs, so, a spacing function that put a space between every two hubs equal to $x$ is like 0ドル\rightarrow(0,1), 1\rightarrow(x,x+1), 2\rightarrow(2x,2x+1),..., m\rightarrow(mx,mx+1)$. This function have the benefit that there is a few recursive calls needed to compute any value, because the distance between any Fibonacci number and a hub < x. But this function doesn't cover a wide range, and this makes it very bad for large numbers.

You can think of other functions, e.g., you may choose a polynomial function such that 0ドル\rightarrow(0^k,1), 1\rightarrow(1^k,2), 2\rightarrow(2^k,2^k+1),..., m\rightarrow(m^k,m^k+1)$. This function covers a wide range, and it's better for large numbers, but it may makes the distance between a Fibonacci number and the nearest hub very big, so bigger recursion depth.

You may use a spacing function that based on Fibonacci numbers, for example, it skips constant number of Fibonacci numbers, e.g., a function that skips $x$ Fibonacci numbers 0ドル\rightarrow(F(0),F(0)+1), 1\rightarrow(F(x),F(x)+1), 2\rightarrow(F(2x),F(2x)+1),..., m\rightarrow(F(mx),F(mx)+1)$.

So, the strategy must choose hubs of two consecutive numbers based on some spacing function, and that function is what affect the complexity.

Good luck.