How to reduce following expression so that it less computation.

Question

I am using following expression in one of my programs

$$P = \left \lfloor \frac{\sum_{i=N}^M F(i) \cdot i!}{K}\right \rfloor \mod p.$$

Here $N$, $M$, $K$ and $P$ are non-negative integers, $N \leq M$ and $p$ is a prime number. Moreover, $F(i)$ returns the $i$th Fibonacci number, i.e. $$ F(i+1) = F(i) + F(i-1)$$ with $F(1) = F(0) = 1$.

It is very time consuming to evaluate this expression. What can I possibly do to reduce the runtime?

Answer 1

Possibly someone has a simplification for that sum. In case not, an off-topic on the programming. It's possible that the problem is you're using a very bad implementation of Fib. That is, if your code looks like this:

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

then there's your problem! This is hugely inefficent - calling Fib(n) leads to Fib(n) calls to Fib(), most of which are repetitions of previously calculated values. You can improve this greatly by "memoizing" the function: Store previously calculated values and look them up when needed:

Fibs = {} """Fibs is a "dict" where we record previously calculated values""" def Fib(n): """Try to look up the answer in Fibs; if that doesn't work give up and recurse, storing the answer for next time:""" try: return Fibs[n] except: if n < 2: ans = 1 else: ans = Fib(n-1) + Fib(n-2) Fibs[n] = ans return ans

The second version will be much faster than the first.

Similarly you probably want to memoize your Factorial(); there the obvious recursive version is less awful since there's only one recursive call, but it's still pretty bad.

Serious Python guys should write a "decorator" @Memoize, allowing you to write the first version and have it automatically execute like the second version.

Answer 2

Yet another way to calculate $F_n$ efficiently, in fact in time $\log n$:

First get $2\times 2$ matrix multiplication working. Now define $$X_n=\begin{bmatrix} F_{n+1}\\F_n\end{bmatrix}.$$Note that $$X_{n+1} =AX_n,$$where $$A=\begin{bmatrix}1&1\\1&0\end{bmatrix}.$$

So you just have to calculate $A^n$, which you can do efficiently using binary exponentiation. (This probably makes more sense if for some reason you need just one value of $F_n$.)