ms8
ms8

Reputation: 417

Error in finding nth fibonacci number

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;
}

Upvotes: 0

Views: 535

Answers (4)

rcgldr
rcgldr

Reputation: 28828

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

Upvotes: 0

moveaway00
moveaway00

Reputation: 917

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();
}

Upvotes: 0

ChemiCalChems
ChemiCalChems

Reputation: 643

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.

Upvotes: 0

Curve25519
Curve25519

Reputation: 694

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.

Upvotes: 2

Related Questions