A problem was caused by an array that was not initialized

Question

I am trying to solve a execise, which amis to find the Last Digit of a Large Fibonacci Number, and I try to search for others' solution, and I find one here: https://www.geeksforgeeks.org/program-find-last-digit-nth-fibonnaci-number/, then I copy and paste the method 2, and I just changed the ll f[60] = {0}; to ll f[60]; but this doesn't work properly on CLion, my test code int n; std:cin>>n; `

for (int i = 0; i < n; i++) {
    std::cout << findLastDigit(i) << '\n';
}

return 0;

}` the error: SIGSEGV (Segmentation fault). Could someone give me a hint or reference or something?

Answer 1

Correct me if I'm totally off base here, but if I'm looking at this correctly, you don't need to actually calculate anything ::

• the last digit of Fibonacci sequence numbers appears to have a predictable pattern that repeats every 60th time, as such (starting with F.0 ) :

  011235831459437077415617853819099875279651673033695493257291 011235831459437077415617853819099875279651673033695493257291 011235831459437077415617853819099875279651673033695493257291 011235831459437077415617853819099875279651673033695493257291 011235831459437077415617853819099875279651673033695493257291 ….etc

So all you have to do is quickly compute the list from F.0 to F.59, then take whatever insanely large input , modulo-% 60, and simply look up this reference array.

———————————————

UPDATE 1 : upon further research, it seems there's more of a pattern to it :

last 1          : every      60
last 2          : every     300 ( 5x)
last 3          : every   1,500 ( 5x)

last 4 %  5,000 : every   7,500 ( 5x)
last 4          : every  15,000 (10x)

last 5 % 50,000 : every  75,000 ( 5x)
last 5          : every 150,000 (10x)

Answer 2

(Re-write)

Segfaults are caused when trying to read or write an illegal memory location.

Running the original code already produces an access violation on my machine.

I modified the original code at two locations. I replaced #include<bits/stdc++.h> with #include <iostream> and added one line of debug output:

// Optimized Program to find last
// digit of nth Fibonacci number
#include<iostream>
using namespace std;

typedef long long int ll;

// Finds nth fibonacci number
ll fib(ll f[], ll n)
{
    // 0th and 1st number of
    // the series are 0 and 1
    f[0] = 0;
    f[1] = 1;

    // Add the previous 2 numbers
    // in the series and store
    // last digit of result
    for (ll i = 2; i <= n; i++)
        f[i] = (f[i - 1] + f[i - 2]) % 10;

    cout << "n (valid range 0, ... ,59): " << n << endl;
    return f[n];
}

// Returns last digit of n'th Fibonacci Number
int findLastDigit(int n)
{
    ll f[60] = {0};

    // Precomputing units digit of
    // first 60 Fibonacci numbers
    fib(f, 60);

    return f[n % 60];
}

// Driver code
int main ()
{
    ll n = 1;
    cout << findLastDigit(n) << endl;
    n = 61;
    cout << findLastDigit(n) << endl;
    n = 7;
    cout << findLastDigit(n) << endl;
    n = 67;
    cout << findLastDigit(n) << endl;
    return 0;
}

Compiling and running it on my machine:

$ g++ fib_original.cpp
$ ./a.out             
n (valid range 0, ... ,59): 60
zsh: abort      ./a.out

ll f[60] has indices ranging from 0 to 59 and index 60 is out of range.

Compiling and running the same code on https://www.onlinegdb.com/

n (valid range 0, ... ,59): 60
1
n (valid range 0, ... ,59): 60
1
n (valid range 0, ... ,59): 60
3
n (valid range 0, ... ,59): 60
3

Although it is an out-of-range access that environment handles it just fine.

In order to find the reason why it is running with array initialization and crashing without on your machine needs some debugging on your machine.

My suspicion is that when the array gets initialized the memory layout changes allowing to use the one additional entry.

Please note that access outside of the array bounds is undefined behavior as explained in Accessing an array out of bounds gives no error, why?.

Answer 3

For a large number, you probably want to utilize a cache. Could you do something like this?

// Recursive solution
int fib(int n, int cache[]) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (cache[n]!= 0) {
        return cache[n];
    }
    cache[n] = fib(n - 1, cache) + fib(n - 2, cache);
    return cache[n];
}

// Iterative solution
int fib(int n) {
    int cache[n + 1];
    cache[0] = 0;
    cache[1] = 1;
    for (int i = 2; i <= n; i++) {
        cache[i] = cache[i - 1] + cache[i - 2];
    }
    return cache[n];
}