Reputation: 417
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
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
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
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
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