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 に答える