Различные ответы при расчете факториала с использованием итерации и рекурсии

Впервые постер здесь, я надеюсь, что этот вопрос приемлем.

В качестве небольшого теста я написал приложение, которое вычисляет факториал числа, используя итерацию и рекурсию. Казалось, это работает нормально, за исключением случаев, когда вы пытаетесь вычислить факториал для чисел больше 24.

Например, при расчете факториала 24 оба метода дают правильный ответ 62044840173323941.

Однако при расчете факториала 25 ответы различаются. Рекурсивный метод дает ответ как 1.5511210043330986e + 025, в то время как итерационный метод дает ответ как 1.5511210043330984e + 025.

Согласно Вольфраму Альфе, правильный ответ должен быть таким же, как итерационный метод, так почему же расхождение между функциями? Я спросил своих коллег, и они также не могут объяснить поведение.

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

Спасибо за ваше внимание.

5

Решение

Рекурсивная версия рассчитывает 5 * (4 * (3 * (2 * 1)))

Итерационная версия рассчитывает 1 * (2 * (3 * (4 * 5)))

Разница в порядке операций меняет порядок округления арифметики с плавающей запятой, что приводит к другому результату.

9

Другие решения

Тип double является не точный тип. Это обещает быть приближенным к правильному значению.

Таким образом, обе реализации не гарантируются быть точными.

Что касается ваших реализаций, то есть два факторы, которые мог вызвать разные ответы.

  1. Вы заказываете умножение по-другому.
  2. Ваша итерационная версия выполняет всю математику в одной переменной. Intel-совместимые архитектуры (x86 и x86-64) используют 80 бит точности в их регистрах с плавающей запятой, и эта точность сохраняется до тех пор, пока регистр не будет сохранен в памяти.
5

Порядок умножений различен, что дает разные результаты из-за округления с плавающей точкой.

Если вы измените for цикл, чтобы идти от 1 в i (а не из i в 1), вы должны получить тот же результат, что и в рекурсивной версии.

2
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector