How to find fibonacci sums of huge numbers?

▲
4
▼

I'm solving a CSES problem in which I've to find the sum of first 'n' Fibonacci numbers. The code:

#pragma GCC optimize("Ofast")
#include <iostream>
 
using namespace std;
 
int main()
{
    unsigned long long int n;
    scanf("%llu", &n);
    unsigned long long int seq[n];
    seq[0] = 0;
    seq[1] = 1;
    unsigned long long int mod = 1000000000 + 7;
    for (unsigned long long int i = 2; i < n + 1; i++) {
        seq[i] = (seq[i - 1] + seq[i - 2]) % mod;
    }
    cout << seq[n];
}

The problem specifies that the value of n can get upto 10^18 and therefore I have used unsigned long long int to initialize n. The problem also instructs to give the modulo 7 answer. The code is working fine for values of n upto 4 digits but breaks when the value of n rises to the upper ceiling of 10^18.It gives a (0xC00000FD) error and does not return anything. Please help me understand the problem here and how to deal with it. Any other suggestions would also be appreciated.

c++
c++11
asked on Stack Overflow Dec 21, 2020 by perpetualprime

3 Answers

▲
2
▼

When doing modular addition, you need to apply your mod to each value you're adding.

For example, (a + b) % c = (a % c + b % c) % c.

That means in your code:

seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;

Otherwise, the addition of seq[i - 1] and seq[i - 2] will result in an overflow.

Read more about modular arithmetic here.

answered on Stack Overflow Dec 21, 2020 by a.Li • edited Dec 21, 2020 by a.Li
▲
1
▼

In this problem

F[i] -> i th Fibonacci number. MOD = 1e9 + 7. n < 1e18

F[n] % MOD = ?

F[n] = F[n-1] + F[n-2] if you calculate this with loop you get TL

that`s way you can optimize this solution

now you calculate F[n] with recursion

F[2*n] = - F[n] * F[n] + 2 * F[n] * F[n+1]

F[2*n+1] = F[n] * F[n] + F[n+1] * F[n+1]

here is my solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
void fib(ll n ,ll &a , ll &b){
    if(n == 0){
        a = 0;
        b = 1;
        return;
    }
    ll x, y;
    if(n%2==1){
        fib(n-1 ,x,y);
        a = y;
        b = (x+y)%MOD;
        return;
    }
    fib(n/2 , x , y);
    a = (x*(2*y +MOD -x)%MOD)%MOD;
    b = ((x*x)%MOD+(y*y)%MOD)%MOD;
    return;
}
int main(){
    ll N , a, b;
    cin >> N;
    fib(N , a, b);
    cout << a;
}
answered on Stack Overflow Dec 21, 2020 by Jamshid Kodirov • edited Dec 21, 2020 by user2807083
▲
0
▼

I think the problem with this code is that you are creating an array seq[n] of size n, which can lead to a SEGFAULT on Linux and STATUS_STACK_OVERFLOW (0xc00000fd) on Windows for large numbers, which refers to stack exhaustion.

Below I give an improved version of your algorithm, which uses a fixed memory size, and for modulo addition, I use the sum_by_modulo function, for avoiding overflow in (a + b) % m operation, the principle of which is described here.

#pragma GCC optimize("Ofast")
#include <iostream>
 
typedef unsigned long long int ullong;

ullong sum_by_modulo(ullong a, ullong b, ullong m){
    ullong sum;
    a %= m;
    b %= m;
    ullong c = m - a;

    if (b==c)
        sum = 0;
    if (b<c)
        sum = a + b;
    if (b > c)
        sum = b-c;
    return sum;
}

int main()
{
    ullong n;
    ullong t1 = 0, t2 = 1, nextTerm = 0;
    ullong modulo = 1000000000 + 7;    

    std::cout << "Enter the number of term: ";
    std::cin >> n;

    for (ullong i = 1; i <= n; ++i)
    {
        if(i == 1)
            continue;
        if(i == 2)
            continue;
        nextTerm = sum_by_modulo(t1, t2, modulo);
        t1 = t2;
        t2 = nextTerm;
    }
    std::cout << nextTerm << " ";
    return 0;
}
answered on Stack Overflow Dec 21, 2020 by alex_noname • edited Dec 21, 2020 by alex_noname

User contributions licensed under CC BY-SA 3.0