Computing fibonacci like function in sublinear time

Question

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)

In case it helps, the naive Fibonacci algorithm requires 2F_{n+1} - 1 calls to evaluate F_n. Maybe you could use that somehow? — templatetypedef, May 20 '16 at 23:32
With @templatetypedef 's observation, your problem is reduced to finding F_{n+1} mod b. There's already a ton of answers on s-o on how to do that. This seems like a reasonable one (although in java rather than C++): http://stackoverflow.com/questions/20300537/nth-fibonacci-number-in-dynamic-programming — Paul Hankin, May 21 '16 at 02:51
What's the range of "b"? There's a potentially good answer from @Beta (although I'd personally use the matrix exponentiation method in the linked question) -- but the Beta method is only good if b is guaranteed small-ish. — Paul Hankin, May 21 '16 at 02:54

Beta · Accepted Answer · 2016-05-21T23:08:25.903

5

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 [c_k, c_k+1] can have b² possible values. So if you start at the beginning and calculate c₁, c₂, c₃... you will have to calculate at most b² of them before the sequence begins to repeat; you will come to a [c_k, c_k+1] that is equal to an earlier [c_j, c_j+1].

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

edited May 21 '16 at 23:08

answered May 21 '16 at 02:00

Beta

96,650
16
149
150

This is a good answer depending on the range of b (which isn't given in the question). If b can be large, then this is no good. If b is always small then it's fine. – Paul Hankin May 21 '16 at 02:53
For the question b can be as large as 10000 so I guess it's feasible – João Areias May 21 '16 at 02:59

Computing fibonacci like function in sublinear time

1 Answers1