皮萨诺时期的快速计算 [英] Fast Computation of Pisano Period

问题描述

我想在不到1秒的时间内计算出数字 m 的皮萨诺周期. 这是我目前在C ++中使用的代码:

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;
}

这不会终止于大的 m .我应该怎么做才能加快计算速度?我在类型上弄错了吗?

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

我已将 tmp 的类型更改为 long long ，但仍然失败.

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

尝试了不同的值之后，该程序将终止直到 m = 9 的所有值，但对于周期为 60 的 m = 10 失败.强>. 我怀疑溢出是未终止的原因.有什么建议?

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?

推荐答案

问题是值增长很快，您可能只想存储模，因为它也可以工作:

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

修改后的代码:

#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;
}

此代码与您的代码之间唯一的算法区别是，我没有存储斐波那契数列的值，而是仅存储了除以m的余数.

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.

此外，已知pisano序列包含1个，2个或4个零，因此通过仅在t == 0时测试相等性，应该大大减少相等性测试的次数.在我的计算机上，对于较大的m，具有t == 0的版本的运行速度是不具有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.

注意::如果您的编译器不支持C ++ 14，请删除对 std::equal .

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

测试"代码:

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

输出:

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

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

这篇关于皮萨诺时期的快速计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！