如何在 C++ (g++) 中用 A,B<=10^18 计算 Fibonacci(A) mod B

Question

例如，A=10^17，B=10^17（<64 位）
通常，在上面的算法中，计算 F(2n) 和计算 F(2n+1) 的计算超出了 long long int 类型，我们不能在其中使用模块化计算。
我所说的计算它的最佳算法是斐波那契快速加倍：

F(0) = 0, F(1) = 1.
F(2n) = F(n)(2*F(n+1) – F(n)).
F(2n + 1) = F(n)² + F(n+1)².

你知道新 C++14（g++8.3.0 或 llvm-clang C++）中的一些类型可以用来避免溢出吗？
我尝试了比 long double 更好的 __float128 但没有成功。（见上面的 g++ 代码）
我听说 __int128 和 __int256 的存在没有 printf 的可能性，但我没有尝试过。
它们在 g++ 8.3.0 中是否可用，或者是否有其他快速方法来处理 128 位整数以进行您能想到的中间计算？（时间性能很重要）

#include <bits/stdc++.h>
using namespace std;

__float128 a,b,c,d;
long long mod;

void fast_fib(long long n,long long ans[]){
    if(n == 0){
        ans[0] = 0;
        ans[1] = 1;
        return;
    }
    fast_fib((n/2),ans);
    a = ans[0];             /* F(n) */
    b = ans[1];             /* F(n+1) */
    c = 2*b - a;
    if(c < 0) c += mod;
    c = (a * c);      /* F(2n) */
    while(c>=mod)c-=mod;
    d = (a*a + b*b);  /* F(2n + 1) */
    while(d>=mod)d-=mod;
    if(n%2 == 0){
        ans[0] = c;
        ans[1] = d;
    }
    else{
        ans[0] = d;
        ans[1] = c+d;
    }
}

int main(){
  int T=1000;
  long long n;
  while(T--){
    scanf("%lld %lld",&n,&mod);
    long long ans[2]={0};
    fast_fib(n,ans);
    printf("%lld\n", ans[0]);
  }
  return 0;
}

with __float128 我无法有效地实现模运算，a、b、c、d 必须存储 128 位数据。

Answer 1

计算不需要任何浮点类型。您只能使用 long long 类型。首先，您需要一个将两个 long long 数（小于 10^18）乘以模 B 的函数。这可以通过类似于 exponentiation by squaring 的方法来完成：

long long multiply(long long a, long long b, long long M) {
    long long res = 0;
    long long d = a;

    while (b > 0) {
        if (b & 1) {
            res = (res + d) % M;
        }
        b /= 2;
        d = (d + d) % M;
    }
    return res;
}

其次，您需要将模运算添加到几乎所有的算术运算中。并且您肯定需要通过向相应操作添加 % mod 来替换这些循环 while(c>=mod)c-=mod（它们可能非常慢）。

您的代码 __float_128 替换为 long long 并使用适当的模块化算法：https://ideone.com/t6R7Tf

您可以做的另一件事是使用（如评论中所述）Boost.Multiprecision 或非标准 __int128 类型（如果支持）而不是 long long 复杂的类型乘法。

此外，您可以使用稍微不同（但实际上使用相同的数学）的方法，这对我来说似乎更明显 - 斐波那契数列矩阵公式

要计算矩阵的 N 次方，您可以通过对所有运算取模 B 进行平方来使用求幂。

如何在 C++ (g++) 中用 A,B<=10^18 计算 Fibonacci(A) mod B

How can I calculate Fibonacci(A) mod B with A,B<=10^18 in C++ (g++)

c++

algorithm

math

implementation

g++