1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – gammatester Nov 21 '17 at 15:53
  • 1
    $\begingroup$ I see. What happens when $K$ does not divide the sum? $\endgroup$ – Carl Christian Nov 21 '17 at 20:50
  • 1
    $\begingroup$ How do you do $(142/8) = 17 \pmod {19}$? $\endgroup$ – Magdiragdag Nov 26 '17 at 18:29
  • 1
    $\begingroup$ @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$. $\endgroup$ – Magdiragdag Nov 27 '17 at 17:56
  • 1
    $\begingroup$ 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. $\endgroup$ – Carl Christian Nov 29 '17 at 0:51
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your input. I'm using memoization in my program, but it's giving me ambiguous results, when value is very high. $\endgroup$ – Sadhu Nov 21 '17 at 16:18
  • $\begingroup$ @Sadhu Where "ambiguous" results are wrong results? If the problem is integer overflow one solution is to use Python... $\endgroup$ – David C. Ullrich Nov 21 '17 at 16:31
  • 1
    $\begingroup$ 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. $\endgroup$ – PM 2Ring Nov 23 '17 at 14:14
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.