c - mpz_add() 在大型程序中导致段错误

Question

我的问题如下。我必须编写一个程序来计算斐波那契数的一个非常大的元素(它必须计算的最低元素是 pow(2,10) 成员，最大元素是 pow(2,20 ) 个成员)。为此，我使用 GMP 的 mpz_t 及其计算函数。

我为此使用尾递归算法(稍后我必须让它并行运行)。问题是它运行了一段时间，然后突然:Segmentation fault (core dumped)。

我给你看我的代码，解释一下，这样你就不必浪费时间去弄清楚它并告诉你我知道了什么。

int main(int argc, char** argv){
  char result[1000000]; char *r; r = result;
  long int n;
  mpz_t num;
  mpz_init(num);
  double start_t, end_t, total_t;
  start_t = omp_get_wtime();
  for(int i = 0; i < 11; i++){
    n = pow(2,i+10);
    fibo(num,n);
    char *d = mpz_get_str(NULL,10,num);
    strcpy(r,d);
    printf("The %ld. element of Fibonacci is: %s\n",n,result);
    fflush(stdout);
    memset(result,  0, sizeof result);
  }

  end_t = omp_get_wtime();
  total_t = end_t - start_t;

  printf("Time of running: %.6f\n",total_t);

  return 0; 
  }

main() 函数基本上创建(并初始化)变量，设置时间测量并在 for 循环中调用 fibo() 函数，获取结果并打印出来。当一切都完成后，程序会写出运行时间并退出。

void fibo(mpz_t res, long int n){
  if(n == 0){
      mpz_set_str(res,"0",10);      
      return;
  }else{
  mpz_t temp1;
  mpz_t temp2;
  mpz_init_set_si(temp1,0);
  mpz_init_set_si(temp2,1);
  fiboTail(res,n,1,temp1,temp2);
  mpz_clear(temp1);
  mpz_clear(temp2);
}

}

fibo() 有 2 个参数，第一个是 mpz_t(对于不知道的人，这是一个指针，它将属于在 main() 所以最终的值将回到那里以供进一步使用)，第二个是我们需要计算的元素的数量。如果元素编号为 0，我们简单地返回“0”，否则我们创建两个 mpz_t 变量，设置一个两个“0”，另一个设置为“1”，并将它们交给 fiboTail()以及其他一些论点。

void fiboTail(mpz_t res, long int n, long int m, mpz_t fibPrev, mpz_t fibCurrent){
    if(n == m){
      mpz_set(res,fibCurrent);
    }else{
      mpz_add(fibPrev,fibPrev,fibCurrent);
      fiboTail(res,n, m + 1, fibCurrent, fibPrev);
    }
}

所以这个基本上是核心。 m 统计我们做了多少次加法，我们在哪个元素上，n 是我们需要的元素个数，fibCurrent 和 fibPrev 分别是当前和之前的斐波那契数。

对于愚蠢的解释，我想你们中的大多数人都知道这一点，而无需我尝试解释。

所以，这个程序真的很快。问题 (Segmentation fault) 在对第 131072 个元素进行计数时发生(有时在较小的元素上，它...随机(？))。然后程序停止大约相同数量的加法/m 值(不总是在同一个，但接近那里)并出现前面提到的错误消息。我使用 gcc 进行编译(实际上使用 Makefiles)，所以我添加了 -g 开关并使用 gdb 来获取更多信息。这是我发现的:

我在 gdb 中运行程序并使用 backtrace 生成 this .

Here是使用帧 #0-5 上的 info frame 的详细堆栈信息。错误发生在调用 mpz_add 时，但我不知道为什么。

如果您需要更多信息，我可以给他们，但现在我不知道还有什么有用的。

抱歉发了这么长的帖子，感谢您提前的回答!

编辑:

因为 mpz_add 似乎在某个时刻死了，我得到了调用的信息，你可以看到它:i.imgur.com/XOpTve1.png(抱歉，无法发布超过 2 个链接 :/)

Answer 1

不确定这是否有帮助，但这里是用于查找 fibonacci(n) 的 Lucas 数列方法，它速度很快并且可用于确认您的结果(例如结果的大小可能太大)。它类似于以矩阵形式实现 fibnoacci(n) 并使用重复平方将矩阵提高到 n 次方，其中 fib(n) = M^n x fib(0)，其中 M 是 2 x 2 矩阵，而 fib()是一个 2 元素 vector 。 Lucas 序列函数需要 1 + log2(n) 次循环才能运行，因此对于 n=2^20，它将需要 21 次循环。

uint64_t fibl(uint64_t n) {
    uint64_t a, b, p, q, qq, aq;
    a = q = 1;
    b = p = 0;
    while(1) {
        if(n & 1) {
            aq = a*q;
            a = b*q + aq + a*p;
            b = b*p + aq;
        }
        n >>= 1;
        if(n == 0)
            break;
        qq = q*q;
        q = 2*p*q + qq;
        p = p*p + qq;
    }
    return b;
}