0
#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.

Evg
  • 25,259
  • 5
  • 41
  • 83
Puneet Kukreja
  • 1
  • please include input, output and expected output in the question – 463035818_is_not_an_ai May 24 '22 at 12:47
  • 1
    i dont think this has anything to do with Digital Signature Algorithm... – 463035818_is_not_an_ai May 24 '22 at 12:48
  • Did you try debugging the code? `long long int` cannot store arbitrary large numbers and Fib(60) is pretty large. – Quimby May 24 '22 at 12:48
  • 1
    *concept wise I think my code is ok* -- Please [debug](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) your code. A computer program does exactly the step you have stated -- it doesn't know if your steps are wrong, only *you* will know this by debugging your program. – PaulMcKenzie May 24 '22 at 12:50
  • You do not need to compute the actual Fibonacci number if all you need is the last digit. – paddy May 24 '22 at 13:01
  • 2
    For each term in the series you only need to keep the last digit. ie 1, 1, 2, 3, 5, 8, (1)3, (1)1, 4, 5, 9, (1)4, etc – Richard Critten May 24 '22 at 13:06
  • You don't even need to keep them. You only need the last 2 last digits and then sum them up as you go along. – Goswin von Brederlow May 24 '22 at 16:34
  • Why are you computing the sum of the first 60 fibonacci numbers and then lookup `n % 60`? Do you have some proof that the sum of last digits repeats after 60 numbers? If so you should compute that vector once, probably as `constinit` at compile time. – Goswin von Brederlow May 24 '22 at 16:38
  • Activate that commented out cout and look at your `first`, `second` and `sum`. Notice a problem? Fixing that and the algorithm seems to work. – Goswin von Brederlow May 24 '22 at 16:42
  • @Goswin concerning proof: The last digit of `fib(n+1)` only depends on the last digits of `fib(n)` and `fib(n-1)`. There are only 100 different combinations of last digit of `fib(n)` and `fib(n-1)` and same last digits result in same last digit of `fib(n+1)`, ergo there must be a loop that is at most 100 iterations long. I suppose 60 one can find out by observing that last digits of `fib(60)` and `fib(59)` are the same as last digits of `fib(1)` and `fib(2)` – 463035818_is_not_an_ai May 24 '22 at 17:52
  • @463035818_is_not_a_number There is also the last digit of sum. So it's at most 1000 iterations. The fact that it repeats after 60 deserves a comment. – Goswin von Brederlow May 24 '22 at 18:43
  • @GoswinvonBrederlow last digit of sum? `fib(n)` only depends on `fib(n-1)` and `fib(n-2)`. `sum` is an implementation detail of OPs implementation. – 463035818_is_not_an_ai May 24 '22 at 18:44
  • @463035818_is_not_a_number `V` is caching the last digit of the sum of `fib(n)` and that is repeating every 60 steps. The fact the last digit of `fib(n)` repeats every 60 steps contributes to that fact but it could have been that the last digit of the sum only repeats every 300 steps or something. Luckily they have the same cycle of 60. – Goswin von Brederlow May 24 '22 at 19:07
  • @Goswin the cycle can be maximum 100. `last_digit_of_fib(n) = (last_digit_of_fib(n-1) + last_digit_of_fib(n-2)) % 10` and there are only 100 different states that can leed to the next last digit – 463035818_is_not_an_ai May 24 '22 at 19:12
  • @463035818_is_not_a_number But `V` is not the last digit of `fib(n)`. It's the sum of the last digits. If the sum of `fib(0) + ... + fib(59)` where 1 then the last digit of the sum would repeat only every 600 steps. – Goswin von Brederlow May 24 '22 at 19:16
  • @GoswinvonBrederlow oh sorry, finally I get your point ;). And I found a formal proof https://en.wikipedia.org/wiki/Pisano_period – 463035818_is_not_an_ai May 24 '22 at 19:18
  • @463035818_is_not_a_number Thanks for finding that. I've added it to my answer. – Goswin von Brederlow May 24 '22 at 19:21

1 Answers1

0

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.

Goswin von Brederlow
  • 11,875
  • 2
  • 24
  • 42