Error in finding nth fibonacci number

Question

I was trying to find find nth fibonacci number mod 100000 where n can be up to 5000000.

Here is my code :

#define max_n 5000000

int mod = 100000;
int memo[max_n + 5];

int fib (int n)
{
      if (n == 1) 
           return 0;

      if (n == 2) 
           return 1;

      if (memo[n] > 0) 
           return memo[n];

      memo[n]=(fib(n-1) + fib(n-2))%mod;

      return memo[n];
}

But when i run the code. it gives runtime error . Please help

In main :

#include <iostream>

using namespace std;

int main()
{

int n, i;

for (i = max_n; i >= 1 ;i--)
{
    fib (i);
}

cin >> n;
cout << memo[n] << endl;

return 0;
}

What runtime error does it give you? This information is very important to solve the bug. — ChemiCalChems, Jun 27 '15 at 16:45
Just a hint: not all compilers sets the elements in array to zero, so in `main` you should add `for (i=0; i — Chan Kha Vu, Jun 27 '15 at 16:47
@ChemiCalChems For small max_n it runs fine. But when i increase it it stos abruptly — ms8, Jun 27 '15 at 16:47
@FalconUA Doing int memo[max_n+5]={0}; doesnt solve the problem..:( — ms8, Jun 27 '15 at 16:48
Maybe you hit a Stackoverflow Error. Lemme port your code to Java to see if that is the problem. — ChemiCalChems, Jun 27 '15 at 16:48
The problem is the size of your numbers. The 5000000th fibonacci number is ~7.108×10^1044937, which is well, WELL, WELL past the highest number representable in an int. — moveaway00, Jun 27 '15 at 16:49
@moveaway00 Actually i am taking mod at each step . I dont think it will pass that range. Also why it will give runtime error then. It will show some garbage value if that was the case — ms8, Jun 27 '15 at 16:50
@ms8: take a look at this post http://stackoverflow.com/questions/17029671/declare-large-array-on-stack. I think, when you declare a static array in c, it will create it in the stack... And there is a possibility that your array is too large for the stack. — Chan Kha Vu, Jun 27 '15 at 16:51
@FalconUA No its acceptable upto 10000000 in my laptop. I had checked it — ms8, Jun 27 '15 at 16:52
You're right, miss-read. And, @FalconUA, the array isn't on the stack. It's declared outside of the function. — moveaway00, Jun 27 '15 at 16:53
One suggestion, but it won't solve your runtime problem::when n==1 or n==2, you are not storing the value into memo. — Rakholiya Jenish, Jun 27 '15 at 16:56

score 2 · Answer 1 · answered Jun 27 '15 at 16:59

2

The error you are getting is stack overflow. This is caused since the stack allocated for your thread is 1MB (by default) and your program have a recursive function call with depth of 5 million.

In order to fix this problem, you can just reverse the iteration, like that:

int n,i;
for(i=1;i<=max_n;++i)
{
   fib(i);
}

Since fib cache the results, there won't be any recursive call at all, and it won't throw stack overflow exception.

answered Jun 27 '15 at 16:59

Curve25519

654
5
17

Well, there will still be a recursive call, but only ever 1. – moveaway00 Jun 27 '15 at 17:03
Works perfectly. That's the normal way anyone would do the calculation anyway. – ChemiCalChems Jun 27 '15 at 17:06

score 0 · Answer 2 · answered Jun 27 '15 at 17:01

0

You code store all the values of the Fibonacci list you get in a std::vector, and make the fib function add the last two of the values inside the std::vector and then write to it. That way, you avoid overflowing the stack with too much recursion. The only problem is, the vector would get huge.

answered Jun 27 '15 at 17:01

ChemiCalChems

612
12
31

Did not notice that. Then he could make that array a vector and get the two last values, as I have already explained. – ChemiCalChems Jun 27 '15 at 17:03

score 0 · Answer 3 · answered Jun 27 '15 at 18:01

As Tal Shalti's answer says, a simple solution is to populate your memo array from front to back.

However, if you design your function to be iterative, instead of recursive, you can eliminate the need to specially populate your list of Fibonacci numbers. Here's how I'd do it:

#include <iostream>
#include <vector>
#include <cassert>

#define CACHE_FIB

using namespace std;

const int MOD = 100000;

vector<int> MEMO{0, 1};

int fib_mod(size_t n) {
    assert(n > 0);
    n -= 1; // zero based

    if(n < MEMO.size())
        return MEMO[n];

    for(size_t i = MEMO.size() - 1; i < n; i++) {
        int next = (MEMO[MEMO.size() - 1] + MEMO[MEMO.size() - 2]) % MOD;
        MEMO.push_back(next);
    }
    return MEMO.back();
}

rcgldr · Answer 4 · 2015-06-27T21:29:52.270

A LRE (linear recurrence equation) such as fibonacci can be converted into a matrix multiply. In this case:

F(0) =  |  0  |   (fib( 0))
        |  1  |   (fib(-1))

M =     | 1 1 |   (calculates LRE             to new 1st number)
        | 1 0 |   (copies previous 1st number to new 2nd number)

F(n) = M F(n-1) = matrixpower(M, n) F(0)

You can raise a matrix to the power n by using repeated squaring, sometimes called binary exponentiation. Example code for integer:

    r = 1;             /* result */
    s = m;             /* s = squares of integer m */
    while(n){          /* while exponent != 0 */
        if(n&1)        /*   if bit of exponent set */
            r *= s;    /*     multiply by s */
        s *= s;        /*   s = s squared */
        n >>= 1;       /*   test next exponent bit */
    }

All this would be done modulo 100000. For n <= 5000000, it would take <= 23 (log2(5000000)) loops to raise a matrix to the power n. For fibonacci modulo 100000, the pattern repeats every 150000 numbers, fib(n+150000)%100000 == fib(n)%100000 == fib(n%150000)%100000. Taking advantage of this, the max value for n%150000 = 149999, and the max number of loops would be 18 (log2(149999)).

Error in finding nth fibonacci number

4 Answers4