Fast Computation of Pisano Period

Question

I want to compute the Pisano Period of a number m in less than 1s. This is the code I currently have in C++ :

#include <iostream>
#include <vector>

using std::vector;

bool is_equal(vector<long long> v, long k) {

  if (k == 0) return false;
  // compare first and second half of array
  for (long i = 0, j = k; i < k, j < v.size(); ++i, ++j) {
    if (v[i] != v[j]) return false;
  }

  return true;
}

long long get_pisano_period(long long m) {

  vector<long long> v;

  long long a = 0; long k = 0; long long b = 1;
  // loop until repetition is found
  while (!is_equal(v, k)) {
    v.push_back(a % m);
    long long tmp = a + b;
    a = b;
    b = tmp;
    k = v.size() / 2;  // the mid point
  }
  return k;
}

This is not terminating for large m. What should I do to speed up the computation? Have I made a mistake in the types?

EDITS:

I have changed the type of tmp to long long and it still fails.

After trying out different values, the program terminates for all values up till m = 9, but fails for m = 10 whose period is 60. I am suspecting overflow is the reason behind non termination. Any suggestions?

Answer 1

Before reading the code notice that:

1.the period always starts with "01".

2.pisano number is even.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
 int m; cin>>m;
 vector<int> v;
 cout << "sequence = ";
 v.push_back(0); cout<< v[v.size()-1]<< " ";
 v.push_back(1); cout<< v[v.size()-1]<< " ";

 while (true)
 {
    v.push_back((v[v.size()-2] + v[v.size()-1]) % m); // saving the remainder only
    cout<< v[v.size()-1]<< " ";
    // true if all elemenets between the begining and half way are the same as the elements between the halfway and the end 
    bool sequence = equal(v.begin(), v.begin() + v.size() / 2, v.begin() + v.size() / 2, v.end());
    bool even = v.size() % 2 == 0;
    if (even && sequence)
    {
        cout<< "\nPisano number = "<< v.size() / 2;
        break;
    }
  }
}

The output :

1. for m = 3:

   3 sequence = 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 Pisano number = 8

2. for m = 99:

   99 sequence = 0 1 1 2 3 5 8 13 21 34 55 89 45 35 80 16 96 13 10 23 33 56 89 46 36 82 19 2 21 23 44 67 12 79 91 71 63 35 98 34 33 67 1 68 69 38 8 46 54 1 55 56 12 68 80 49 30 79 10 89 0 89 89 79 69 49 19 68 87 56 44 1 45 46 91 38 30 68 98 67 66 34 1 35 36 71 8 79 87 67 55 23 78 2 80 82 63 46 10 56 66 23 89 13 3 16 19 35 54 89 44 34 78 13 91 5 96 2 98 1 0 1 1 2 3 5 8 13 21 34 55 89 45 35 80 16 96 13 10 23 33 56 89 46 36 82 19 2 21 23 44 67 12 79 91 71 63 35 98 34 33 67 1 68 69 38 8 46 54 1 55 56 12 68 80 49 30 79 10 89 0 89 89 79 69 49 19 68 87 56 44 1 45 46 91 38 30 68 98 67 66 34 1 35 36 71 8 79 87 67 55 23 78 2 80 82 63 46 10 56 66 23 89 13 3 16 19 35 54 89 44 34 78 13 91 5 96 2 98 1 Pisano number = 120

Answer 2

Below are two implementations of the same iterative algorithm that generates the Pisano periodic sequence for any given modulo n under the following contraints:

1<=n<=CR

Where CR stands for your computing resources. In my case, CR approximates 10,000,000,000.

The algorithm is constructed around the ideas that a Pisano sequence always starts with 0 and 1, and that this sequence of Fibonacci numbers taken modulo n can be constructed for each number by adding the previous remainders and taking into account the modulo n.

C#

public static IEnumerable<int> PisanoPeriodicSequence(int n)
{
    int current = 0, next = 1;

    yield return current;

    if (n < 2) yield break;
    next = current + (current = next);

    while (current != 0 || next != 1)
    {
        yield return current;
        next = current + next >= n ? current - n + (current = next) : current + (current = next);
    }
}

C++

std::vector<int> pisano_periodic_sequence(int n)
{
    std::vector<int> v;
    int current = 0, next = 1;

    v.push_back(current);

    if (n < 2) return v;
    current = (next += current) - current;

    while (current != 0 || next != 1)
    {
        v.push_back(current);
        current = current + next >= n ? (next += current - n) + (n - current) : (next += current) - current;
    }

    return v;
}

Answer 3

The problem is that the values grow very fast, you might want to only store the modulo since it will also work:

Modified code:

#include <algorithm>
#include <vector>

size_t get_pisano_period(long m) {
    std::vector<long> v{1, 1};
    while (true) {
        auto t = (v[v.size() - 1] + v[v.size() - 2]) % m;
        v.push_back(t);
        if (t == 0 && v.size() % 2 == 0 &&
            std::equal(v.begin(), v.begin() + v.size() / 2,
                       v.begin() + v.size() / 2, v.end())) {
            return v.size() / 2;
        }
    }
    return v.size() / 2;
}

The only algorithmic difference between this code and yours is that instead of storing the values of fibonacci sequence, I am only storing the remainder of the division by m.

Also, it is known that a pisano sequence contains either 1, 2 or 4 zeros, so by testing equality only when t == 0, you should greatly reduce the number of equality tests. On my computer, for large m, the version with t == 0 goes twice as fast as the version without.

Note: If your compiler does not support C++14, remove the last argument in the call to std::equal.

"Test" code:

int main () {
    for (auto i = 2LL; i < 100; ++i) {
        std::cout << get_pisano_period(i) << ' ';
    }
    std::cout << '\n';
}

Output:

1 8 6 20 24 16 12 24 60 10 24 28 48 40 24 36 24 18 60 16 30 48 24 100 84 72 48 14 120 30 48 40 36 80 24 76 18 56 60 40 48 88 30 120 48 32 24 112 300 72 84 108 72 20 48 72 42 58 120 60 30 48 96 140 120 136 36 48 240 70 24 148 228 200 18 80 168 78 120 216 120 168 48 180 264 56 60 44 120 112 48 120 96 180 48 196 336 120

Answer 4

a overflows in the current program. The end result of the modulus calculation will be the same if you calculate it throughout.

So by changing a = b to a = b%m we can avoid the overflow:

#include <iostream>
#include <vector>

using std::vector;

bool is_equal(const vector<long long>& v, long k) {
    auto size{v.size()};
    if(k == 0) return false;
    // compare first and second half of array
    for(long i = 0, j = k; i < k && j < v.size(); ++i, ++j) {
        if(v[i] != v[j]) return false;
    }

    return true;
}

long long get_pisano_period(long long m) {

    vector<long long> v;

    long long a = 0; long k = 0; long long b = 1;
    // loop until repetition is found
    while(!is_equal(v, k)) {
        v.push_back(a % m);
        long long tmp = a + b;
        //a = b; // this grows too large
        a = b%m; // better
        b = tmp;
        k = v.size() / 2;  // the mid point
    }
    return k;
}

int main()
{
    auto testval{get_pisano_period(10)};
    std::cout << testval << '\n';
}