Fast Dobuling to find Fibonacci number, function not working in C++

Question

I am learning this algorithm to calculate nth number in fibonacci series. This is my code,

#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007

long long int fib(long long int n)
{
    if(n < 2)
        return n;
    if(n == 2)
        return 1;
    long long int k = n/2;
    long long int a = fib(k+1);
    long long int b = fib(k);
    if(n%2 == 1)
        return (((a*a)%MOD) + ((b*b)%MOD))%MOD;
    else
        return (b*((2*a - b)%MOD))%MOD;

}

int main()
{
    //fibonacci series : 0,1,1,2,3,5,8,13..
    long long int n;
    scanf("%lld",&n);
    printf("%lld\n", fib(n));
    return 0;
}

It is working fine for smaller no.s but for larger n values, its printing -ve no.s as output.

n = 10000000
fib(n) = -509810513

I don't understand where the value is going into -ve no.s as I think I applied % operator properly for not having any data type overflow. Anyone please help me in finding the mistake.

If it's not a homework problem you should probably look at fibonacci's number closet formula, also known as Binet's fibonacci number formula. Basically, f(n) = (1/sqrt(5)) * ((1 - sqrt(5)) / 2) ^ n. You can solve the sqrt problems by using approximate values and executing round for the final result. — noisy cat, Feb 25 '15 at 18:11

score 3 · Accepted Answer · answered Feb 25 '15 at 18:04

3

With modulus,

long long int a = fib(k + 1);
long long int b = fib(k);

a >= b is not necessary true, (2 * a >= b neither).

so

return (b * ((2 * a - b) % MOD)) % MOD;

may return negative number.

answered Feb 25 '15 at 18:04

Jarod42

203,559
14
181
302

Thank you. I was struggling to find this from long time. – nomorequestions Feb 25 '15 at 18:10

rcgldr · Answer 2 · 2015-02-25T18:29:02.867

This should fix the issue with (2*a - b) < 0. It produces the correct answer for n = 10000000, which is 490189494.

#define MOD 1000000007

long long int fib(long long int n)
{
long long int a, b, k;
    if(n < 2)
        return n;
    if(n == 2)
        return 1;
    k = n/2;
    a = fib(k+1);
    b = fib(k);
    if(n%2 == 1)
        return (((a*a)%MOD) + ((b*b)%MOD))%MOD;
    else{
        k = (2*a - b)%MOD;
        if(k < 0)
            k += MOD;
        return((b*k)%MOD);
    }
}

Fast Dobuling to find Fibonacci number, function not working in C++

2 Answers2