使用迭代和递归计算阶乘时的不同答案

Question

这里的第一次海报,我希望这个问题是可以接受的.

作为一个小测试我写了一个应用程序,使用迭代和递归计算数字的阶乘.这似乎工作得很好,除了在尝试计算大于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;
}

谢谢您的考虑.

Answer 1

递归版计算5*(4*(3*(2*1)))

迭代版本计算1*(2*(3*(4*5)))

操作顺序的差异改变了浮点运算的舍入方式,从而导致不同的结果.

Answer 2

该类型double是不是一个确切的类型.它有望成为正确值的近似值.

因此,两种实现都不能保证准确.

就您的实施而言,有两个因素可能导致不同的答案.

1. 你以不同的方式命名乘法.
2. 您的迭代版本在同一个变量中执行所有数学运算.英特尔兼容的体系结构(x86和x86-64)在其浮点寄存器中使用80位精度,并且在寄存器存储在存储器中之前一直保持准确性.