c - 查找斐波那契数列中第 n 项的最后一位数字的问题

Question

我写了一些代码来确定第 n 个斐波那契数，使用这个问题的已接受答案中给出的不错的博客文章:Finding out nth fibonacci number for very large 'n' .我这样做是为了练习在 projecteuler 上给出的更困难的递归问题，但这并不是真正相关的。该方法依赖于将问题转换为形式为的小型线性代数问题

Fn = T^n F1

其中 F1 = (1 1)^t 和 Fn 包含第 n 个和第 (n-1) 个斐波那契数。然后可以在 O(log n) 时间内确定 T^n 项。我成功地实现了这个并且它似乎工作正常。当我执行矩阵求幂时，我使用 %10000 所以我只得到最后 4 位数字，这似乎有效(我检查了一些大的斐波那契数)。但是，我想通过增加数字 10000 来尝试获得更多的最后一位数字。但这似乎不起作用。我不再得到正确的答案。这是我的代码

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

const unsigned long M = 10000;

unsigned long int * matProd(unsigned long int * A, unsigned long int * B){
  unsigned long int * C;
  C = malloc(4*sizeof(unsigned long int));
  C[0] = ((A[0]*B[0]%M) + (A[1]*B[2]%M)) % M;
  C[1] = ((A[0]*B[1]%M) + (A[1]*B[3]%M)) % M;
  C[2] = ((A[2]*B[0]%M) + (A[3]*B[2]%M)) % M;
  C[3] = ((A[2]*B[1]%M) + (A[3]*B[3]%M)) % M;
  return C;
}

unsigned long int * matExp(unsigned long int *A, unsigned long int n){
  if (n==1){
    return A;
  }
  if (n%2==0){
    return matExp(matProd(A,A),n/2);
  }
  return matProd(A,matExp(A,n-1));
}

unsigned long int findFib(unsigned long int n){
  unsigned long int A[4] = {0, 1, 1, 1};
  unsigned long int * C;
  C = malloc(4*sizeof(unsigned long int));
  C = matExp(A,n-2);
  return (C[2]+C[3]);
}

main(){
  unsigned long int n = 300;
  printf("%ld\n",findFib(n));
}

关于正确的编码约定和可以改进的事情，可能存在几个问题。我认为更改为 long int 可能会解决问题，但这似乎并不能解决问题。所以基本上问题是将 M 增加到例如 1000000 不会给我更多的数字，而是给我胡说八道。我犯了什么错误？

附言抱歉数学格式不佳，我已经习惯了 math.stackexchange。

Answer 1

问题可能是您在 long 所在的系统上运行大小为 32 位，我相信 Windows 就是这种情况。您可以通过编译并运行 printf("%d\n", sizeof(long)) 来检查这一点应该输出 4 .

自从 M=1000000=10^6 , 两个小于 M 的数字的乘积最高可达 10^12 ，自 unsigned long 起计算矩阵条目时会出现溢出问题最多可以容纳 2^32-1或大致 4 * 10^9 .

只需使用 unsigned long long 即可解决此问题作为你的类型而不是 unsigned long .或者更好的是，uint64_t ，保证在所有平台上都是 64 位的(并且需要 #include <stdint.h> )。这应该使您的代码适用于 M最多 sqrt(2^64)~10^9 .如果您需要比这更大的值，则需要使用大整数库。