5

ここに初めて投稿します。この質問が受け入れられることを願っています。

小さなテストとして、反復と再帰の両方を使用して数値の階乗を計算するアプリケーションを作成しました。これは、24 より大きい数値の階乗を計算しようとする場合を除いて、うまく機能するように見えました。

たとえば、24 の階乗を計算すると、どちらの方法でも 62044840173323941 という正しい答えが得られます。

ただし、25 の階乗を計算すると、答えが異なります。再帰的方法では答えが 1.5511210043330986e+025 になり、反復方法では答えが 1.5511210043330984e+025 になります。

Wolfram Alpha によると、正解は反復法と同じはずですが、なぜ関数間の不一致が生じるのでしょうか? 同僚に尋ねたところ、彼らもその行動を説明できませんでした。

#define TEST_CASE 25

double GetFactorialRecursive(double i)
{   
    if (i == 1)
    return i;
    else
    return i * GetFactorialRecursive(i - 1);
}

double GetFactorialIterative(double i)
{
    double result = 1.0;
    for (; i > 0; --i)
        result *= i;
    return result;
}

int main ()
{
    double recres = 0, itrres = 0; 
    recres = GetFactorialRecursive(TEST_CASE);
    itrres = GetFactorialIterative(TEST_CASE);

    if (recres != itrres)
        std::cout << "Error" << "\n";
    std::cout << std::setprecision(25) << "Recursion: " << recres << ", Iteration: " << itrres << "\n";
    return 0;
}

ご検討をお願いいたします。

4

3 に答える 3

9

再帰バージョンは 5 * (4 * (3 * (2 * 1))) を計算します

反復バージョンは 1 * (2 * (3 * (4 * 5))) を計算します

演算の順序の違いにより、浮動小数点演算の丸め方が変わり、結果が異なります。

于 2013-04-08T07:15:23.517 に答える
5

タイプdoubleが正確なタイプではありません。正しい値の近似値になることを約束します。

したがって、両方の実装が正確であるとは限りません。

あなたの実装が懸念しているように、異なる答えを引き起こす可能性のある2つの要因があります。

  1. 乗算の順序が異なります。
  2. 反復バージョンは、同じ変数ですべての計算を実行します。Intel 互換アーキテクチャ (x86 および x86-64)は、浮動小数点レジスタで80 ビットの精度を使用し、その精度はレジスタがメモリに格納されるまで維持されます。
于 2013-04-08T07:20:32.900 に答える