2

我编写了以下简单函数来执行模幂运算。但是，当指数参数大于约 261,000 时，它会出现段错误。为什么是这样？我该如何解决？

我在 64 位 Ubuntu 上使用 gcc 进行编译。

谢谢

unsigned int modex(unsigned int base, unsigned int exponent, unsigned int modulus)
{
   if(exponent == 1)
      return base;

   base = base % modulus;

   if(exponent == 0 || base == 1)
      return 1;

   return (modex(base, exponent - 1, modulus) * base) % modulus;
}
4

3 回答 3

5

@ouah 已经在评论中发布了答案，所以如果他想发布答案，我会删除它。

你有一个堆栈溢出。您递归的次数太多，并且耗尽了您的堆栈空间。C++ 不保证尾调用优化（即使最后没有对递归调用的返回值进行该操作），因此最好使用循环来实现它。

如果您想坚持使用递归路线，请尝试通过此处的说明使其真正成为尾递归，并查看编译器是否可以帮助您。

于 2013-03-06T18:56:16.133 回答
2

你正在创建一个巨大的递归链。您应该尝试通过迭代来节省内存和处理。

unsigned modex(unsigned base, unsigned exponent, unsigned modulus){

    unsigned
        result = 1;

    while(expoent--){
        result *= base;
        result %= modulus;

    }

    return result;

}

不过，您可以做得更快。

于 2013-03-06T18:57:10.313 回答
1

你的递归变得如此之深以至于它占据了整个麻袋。考虑改用 while 循环。

于 2013-03-06T18:54:30.347 回答