在 C++ 中计算需要大于 16 字节数据类型的数字

Question

我正在开发一个函数来计算斐波那契数并在 C++ 中返回该数字的最低值数字。我发现在 C++ 中，最大的数据类型是 __uint128_t，它为我提供了 16 个字节可供使用。我编写了一个重载来处理流 __uint128_t。这将计算第 186 个斐波那契数，然后在 187 处溢出。我需要比 186 高得多。这是我的函数：

__uint128_t get_fibonacci_last_digit_fast (int n)
{
    __uint128_t f[n];

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i < n + 1; i++)
    {
        f[i] = f[i - 1] + f[i -2];
    }

    return f[n] % 10;
}

我知道 boost 库和其他有助于处理 C++ 中的大数据的库，但此函数用于必须提交给未安装这些库的自动评分器的作业。只有标准 C++ 库，因此我的代码在与这些库一起提交时无法编译。我正在考虑可能构建一种数据类型来处理这个问题。任何有关前进的指导和帮助将不胜感激。

Answer 1

• 如果您只需要最后一位数字，可以使用Pisano period：

#include <iostream>

int _last_digit(long long n)
{
    n %= 60;

    if (n <= 1)
        return n;

    int prev = 0;
    int curr = 1;

    for (int i = 2; i <= n; ++i)
    {
        int next = (prev + curr) % 10;
        prev = curr;
        curr = next;
    }

    return curr;
}

int main()
{
    long long n = 10000000000008989L;
    std::cout << _last_digit(n) << "\n";
}

打印

9

• 注：% 10 的皮萨诺周期为 60。