CODEWITHSUNDEEP
c++algorithmperformancefibonacci
João Areias
João Areias

Reputation: 1448

Computing fibonacci like function in sublinear time

So, here is the problem:

Given a number n I need to calculate the amount of calls it would need to calculate the fibonacci of that number recursively and output only the last digit in a given base as a decimal. The input comes as 2 numbers being the first the number n and the second the base that the output should be in. For the output should be the case number, the first input, the second input and the result of the calculation. The program should exit when the first entry is equal to the second entry that equals 0. For example:

Input:
0 100
1 100
2 100
3 100
10 10
3467 9350
0 0

Output:
Case 1: 0 100 1
Case 2: 1 100 1
Case 3: 2 100 3
Case 4: 3 100 5
Case 5: 10 10 7
Case 6: 3467 9350 7631

I have arrived on the following formula when trying to solve this. Being c(n) the last digit of the number of calls it would take in a base b, we have that:

c(n) = (c(n-1) + c(n-2) + 1) mod b

The problem is that n can be any value from 0 to 2^63 - 1 so I really need the code to be efficient. I have tried doing in a iterative way or using dynamic programming but, although it give me the right output, it doesn't give me in a short enough time. Here is my code:

Iterative

#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<unsigned long long int> v;
    unsigned long long int x,y,co=0;
    cin >> x >> y;
    while(x||y){
        co++;
        v.push_back(1);
        v.push_back(1);
        for(int i=2;i<=x;i++) v.push_back((v[i-1]+v[i-2]+1)%y);
        cout << "Case " << co << ": " << x << " " << y << " " << v[x] << endl;
        cin >> x >> y;
        v.clear();
    }
    return 0;
}

Dynamic programming

#include <iostream>
#include <vector>

using namespace std;

vector<unsigned long long int> v;

unsigned long long c(int x, int y){
    if(v.size()-1 < x) v.push_back((c(x-1,y) + c(x-2,y) + )%y);
    return v[x];
}

int main(){
    int x,y,co=0;
    cin >> x >> y;
    while(x||y){
        co++;
        v.push_back(1);
        v.push_back(1);
        cout << "Case " << co << ": " << x << " " << y << " " << c(x,y) << endl;
        cin >> x >> y;
        v.clear();
    }
    return 0;
}

x and y are respectively n and b, v holds the values for c(n)

Upvotes: 3

Views: 167

Answers (1)

Beta
Beta

Reputation: 99094

Every c in the sequence is less than b. So there are b possibilities for the value of a c. So a pair of consecutive elements [ck, ck+1] can have b2 possible values. So if you start at the beginning and calculate c1, c2, c3... you will have to calculate at most b2 of them before the sequence begins to repeat; you will come to a [ck, ck+1] that is equal to an earlier [cj, cj+1].

Then you know the length of the cycle, call it S, and you know that cn = c((n-j)mod S)+j for all n > j. That should cut your work down quite a lot.

Upvotes: 5

Related Questions