Last Digit of the Sum of Fibonacci Numbers. Unable to get exact answer

Question

#include<iostream>
#include<vector>
#include<cstdlib>
#include <cassert>
using namespace std;
long long int LastDigitofSumofFibonacci(int n){long long int first=0;
     long long int second=1;
     long long int fibOfn;
     long long int sum=1;
     vector<long long int> V;
     V.push_back(first);
     V.push_back(second);
     if(n==0) return first;
     else if(n==1) return second;
     else{
        for(int i=2;i<60;i++){
            fibOfn=first+second;
            first=second;
            second=fibOfn;
            sum=sum+fibOfn;
            //cout<<"i "<<i<<" fibOfn "<<fibOfn<<" fibOfnlastdigit "<<fibOfnlastdigit<<" first "<<first<<" second "<<second<<" sum "<<sum;
            //cout<<endl;
            sum=sum%10;
            V.push_back(sum);
        }
    } 
    //for(auto element:V)
        //cout<<element<<" ";
        //cout<<endl;
    //cout<<(n)%60<<endl;
    return V[(n)%60];
}
int main(){
    int n;
    cin>>n;
    long long int Base=LastDigitofSumofFibonacci(n);
    cout<<Base<<endl;
}

In this I am trying to calculate the the last digit of Fibonacci series. I know and also read from net that last digit follow pattern of 60(0-59). from that concept wise I think my code is OK. but still I am unable to get the correct answers for large digit number.

Answer 1

I cleaned up the code a bit and fixed the issue with second not being computed % 10.

Since only the last digit is relevant all variables can be just int, no need for long long int to store a single digit. It would actually save ram to use uint8_t as type for the cache, but 60 bytes or 240 bytes isn't going to make a difference here.

The result repeats every 60 steps, which is the basis for the algorithm. But why compute this every time the function gets called? So lets make a static array so the computation only happens once. Lets go one step further with constinit and compute it at compile time.

As last change I made the argument to LastDigitofSumofFibonacci unsigned int. Unless you want to extend the fibonacci series backwards into the negative and extend the algorithm. unsigned int generates better code for n % 60.

#include <iostream>
#include <array>

int LastDigitofSumofFibonacci(unsigned int n) {
    // The last digit of `fib(n)` and their sum repeats every 60 steps.
    // https://en.wikipedia.org/wiki/Pisano_period
    // Compute the first 60 values as lookup table at compile time.
    static constinit std::array<int, 60> cache = []() {
        int first = 0, second = 1;
        std::array<int, 60> a{0, 1};
        for (int i = 2; i < 60; i++) {
            int t = first + second;
            first = second;
            second = t % 10;
            a[i] = (a[i - 1] + t) % 10;
        }
        return a;
    }();
    // and now just look up the answer at run time.
    return cache[n % 60];
}
int main(){
    int n;
    std::cin >> n;
    std::cout << LastDigitofSumofFibonacci(n) << std::endl;
}

Somehow the code got a lot shorter just from eliminating some overhead here and there.