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?
 A: 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.
A: 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$.)
