Когда я вычисляю большой факториал, почему я получаю отрицательное число?

Question

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

int calcFactorial(int num)
{
    int total = 1;

    if (num == 0)
    {
        return 0;
    }

    for (num; num > 0; num--)
    {
        total *= num;
    }

    return total;
}

Теперь, это прекрасно работает и прекрасно (есть, конечно, более быстрые и элегантные решения, но это работает для меня) для большинства номеров. Однако при вводе больших чисел, таких как 250, если говорить прямо, вымирает. Теперь первая пара факторных «битов» для 250 - {250, 62250, 15126750, 15438000, 3813186000} для справки.

Мой код выплевывает {250, 62250, 15126750, 15438000, -481781296 }, который явно выключен. Моим первым подозрением было, пожалуй, то, что я нарушил предел 32-битного целого числа, но учитывая, что 2 ^ 32 равно 4294967296, я так не думаю. Единственное, о чем я могу думать, это, возможно, то, что он нарушает знаковый 32-разрядный предел, но разве он не должен думать о такого рода вещах? Если проблема заключается в подписании, я могу решить эту проблему, оставив целое число без знака, но это будет только временное решение, так как следующая итерация даст 938043756000, что намного превышает предел 4294967296.

Итак, моя проблема - подписанный лимит? Если так, что я могу сделать, чтобы вычислить большие числа (хотя у меня есть класс LargeInteger, который я недавно создал, который может подойти!), Не сталкиваясь с этой проблемой снова?

Answer 1

2 ^ 32 не дает вам ограничения для целых чисел со знаком.

Целочисленное ограничение со знаком на самом деле составляет 2147483647 (если вы разрабатываете для Windows с использованием инструментов MS, другие наборы инструментов / платформы будут иметь свои собственные ограничения, которые, вероятно, аналогичны).

Вам понадобится библиотека больших чисел C ++ , как эта .

Answer 2

В дополнение к другим комментариям я хотел бы указать на две серьезные ошибки в вашем коде.

• У вас нет защиты от отрицательных чисел.
• Факториал нуля равен единице, а не нулю.

Answer 3

Да, вы достигли предела. Int в C ++, по определению, подписан. И нет, С ++ не думает никогда. Если вы скажете ему сделать что-то, он сделает это, даже если это явно неправильно.

Рассмотрите возможность использования библиотеки большого числа. Их много для C ++.

Answer 4

Если вы не укажете подписанный или неподписанный, по умолчанию подписывается. Вы можете изменить это, используя переключатель командной строки на вашем компиляторе.

Просто помните, C (или C ++) - это язык очень низкого уровня, и он точно делает то, что вы говорите ему . Если вы скажете ему сохранить это значение в подписанном int, это то, что он будет делать. Вы как программист должны выяснить, когда это проблема. Это не работа языка.

Answer 5

У вас проблема переполнения. Факториалы могут легко превышать пределы целых чисел. Вы можете изменить свою функцию, чтобы она возвращала двойные значения, но это только даст вам немного больше места. В приложениях вам часто нужно умножать факториалы на очень маленькие числа, где конечный результат будет помещаться в двойное число, а промежуточные шаги - нет. Вот статья, которая объясняет, как справиться с этой ситуацией: http://www.johndcook.com/blog/2008/04/24/how-to-calculate-binomial-probabilities/

Answer 6

Мой калькулятор Windows ( Start-Run-Calc ) сообщает мне, что

hex (3813186000) =         E34899D0
hex (-481781296) = FFFFFFFFE34899D0

Так что да, причина - подписанный лимит. Поскольку факториалы по определению могут быть только положительными и могут быть рассчитаны только для положительных чисел, аргумент и возвращаемое значение должны быть в любом случае беззнаковыми числами. (Я знаю, что все используют int i = 0 для циклов, как и я. Но оставив в стороне, мы должны всегда использовать беззнаковые переменные, если значение не может быть отрицательным, это хорошая практика IMO).

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

Ой, подождите, согласно тому, что я написал выше, вы должны сделать это без знака поплавка; -)

Answer 7

Если я хорошо помню:

unsigned short int = max 65535

без знака int = max 4294967295

без знака long = макс. 4294967295

без знака long long (Int64) = макс. 18446744073709551615

Отредактированный источник:

Int / Long Max значения

Современная переменная компилятора