Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Different answers when calculating factorial using iteration and recursion

First time poster here, I hope that this question is acceptable.

As a small test I wrote an application that calculates the factorial of a number using both iteration and recursion. This seemed to work fine except when trying to calculate the factorial for numbers greater then 24.

For example, when calculating the factorial of 24 both methods give the correct answer of 62044840173323941.

When calculating the factorial of 25 however, the answers differ. The recursive method gives the answer as 1.5511210043330986e+025 while the iterative method gives the answer as 1.5511210043330984e+025.

According to Wolfram Alpha the correct answer should be the same as the iterative method, so why the discrepancy between the functions? I asked my colleagues and they also are unable to explain the behaviour.

#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;
}

Thank you for your consideration.

like image 509
DrDeanification Avatar asked Apr 08 '13 07:04

DrDeanification


2 Answers

The recursive version calculates 5 * (4 * (3 * (2 * 1)))

The iterative version calculates 1 * (2 * (3 * (4 * 5)))

The difference in the order of operations changes how the floating point arithmetic rounds, resulting in a different result.

like image 183
Ryan Cavanaugh Avatar answered Sep 27 '22 21:09

Ryan Cavanaugh


The type double is not an exact type. It promises to be an approximation of the correct value.

So both implementations are not guaranteed to be exact.

As your implementations are concerned there are two factors that could cause different answers.

  1. you are ordering the multiplication differently.
  2. Your iterative version performs all the math in the same variable. Intel-compatible architectures (x86 and x86-64) use 80 bits of accuracy in their floating-point registers, and that accuracy is maintained until the register is stored in memory.
like image 33
Drew Dormann Avatar answered Sep 27 '22 22:09

Drew Dormann