# How to reduce following expression so that it less computation.

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?

• Compute $F_i=fibonacci(i), P_i=i!$ for $i=N-1, N-2$ before starting summation. In the summation loop update only $F_i = F_{i-1} + F_{i-2}, P_i = P_{i-1} \times i$ with the recursion formulas. This avoids recomputing the complete $F_i, i!$ for each summation step. – gammatester Nov 21 '17 at 15:53
• I see. What happens when $K$ does not divide the sum? – Carl Christian Nov 21 '17 at 20:50
• How do you do $(142/8) = 17 \pmod {19}$? – Magdiragdag Nov 26 '17 at 18:29
• @Sadhu I see that you modified the question to add a floor operator. Then you must compute the full result in the integers, not reducing mod $p$ at every step, and only do the mod $p$ at the end. Where did you get this problem from? Project Euler? I consider it extremely likely that in the specific context of the problem, the sum is always evenly divisible by $K$. – Magdiragdag Nov 27 '17 at 17:56
• It would be a very nice edit if you explain why this formula is relevant to you. I don't question that it is relevant to you, but you will earn goodwill by doing this. Any additional information about the relevant input parameters is crucial. In particular, you must address @Magdiragdag last comment. – Carl Christian Nov 29 '17 at 0:51

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.

• Thank you for your input. I'm using memoization in my program, but it's giving me ambiguous results, when value is very high. – Sadhu Nov 21 '17 at 16:18
• @Sadhu Where "ambiguous" results are wrong results? If the problem is integer overflow one solution is to use Python... – David C. Ullrich Nov 21 '17 at 16:31
• We've got a least recently used cache decorator in the standard library functools.lru_cache. FWIW, here's some code that tests various Fibonacci algorithms in Python. – PM 2Ring Nov 23 '17 at 14:14

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$.)