How to find fibonacci sums of huge numbers?

Question

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.

A short search discloses [Test if a number is fibonacci](https://stackoverflow.com/q/2432669/3422102) with a large number of answers addressing large numbers beyond 64-bit. — David C. Rankin, Dec 21 '20 at 08:45
Look at the maths. If one of your additions took one nanosecond (which is very optimistic) and `n` were 10^18, your program would run for almost 32 years. This suggests that there must be a faster method. (Also, your array would require eight million gigabytes. You only need to keep the last two Fibonacci numbers in order to compute the next.) — molbdnilo, Dec 21 '20 at 09:04
C++ compilers are not guaranteed to support VLA. So this `unsigned long long int seq[n];` invokes Undefined Behaviour. Please make sure that it is not the cause — Serge Ballesta, Dec 21 '20 at 09:22
Your text says modulo 7, while your code computes modulo 1000000007. Which one is the expected value? — Serge Ballesta, Dec 21 '20 at 09:26
@SergeBallesta 1000000007. It's a common number in algorithmic problems to prevent integer overflows. — DarthQuack, Dec 21 '20 at 09:48
@molbdnilo Correct, the key observation if someone actually wants to solve this is to figure out how to compute the sum without adding up all the terms (as that will take years), and THEN rewrite that formula using the linked answers. — Hans Olsson, Dec 21 '20 at 14:54

DarthQuack · Answer 1 · 2020-12-21T08:26:06.657

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.

edited Dec 21 '20 at 08:26

answered Dec 21 '20 at 08:04

DarthQuack

1,254
3
12
22

1

I have a doubt though, seq[i - 1] = (seq[i-2] + seq[i-3]) % mod. So there is already a mod on seq[i - 1] so why are 2 mods required? – perpetualprime Dec 21 '20 at 08:37
You're correct, I didn't catch that. I think adding the line `seq[i] %= mod` in your loop after the addition should do the trick, without the need for 2 extra mods. – DarthQuack Dec 21 '20 at 08:58

score 1 · Accepted Answer · edited Dec 21 '20 at 09:18

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

can you explain the maths behind it? any further articles to read or videos to watch — perpetualprime, Dec 21 '20 at 18:38

alex_noname · Answer 3 · 2020-12-21T10:34:00.857

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

None of your answers are right – perpetualprime Dec 21 '20 at 18:23 — perpetualprime, Dec 21 '20 at 18:23
How did you come to this conclusion? – alex_noname Dec 21 '20 at 18:31 — alex_noname, Dec 21 '20 at 18:31

How to find fibonacci sums of huge numbers?

3 Answers3