Как справиться, когда факториал становится слишком большим для int в С++?
У меня есть эта рекурсивная функция для поиска факториала, но я не знаю, как изменить ее, чтобы она выдавала ошибку, когда факториал становится слишком большим для int.
Если бы моя функция была итеративной, я мог бы просто вставить оператор if, проверяя, равен ли факториал 0 или меньше каждый раз, тем самым обнаруживая, где произошло переполнение, но это не представляется возможным для рекурсивного определения.
int factorial(int x)
{
if (x < 0) error("Can't take factorial of a negative number.");
else if (x == 0) return 1;
else return x * factorial(x - 1);
}
Если, например, я вызову функцию с 50, она вернет 0. Я хотел бы выдать сообщение об ошибке в таких случаях. Может ли кто-нибудь исправить меня по этому поводу?
Просто проверьте, не слишком ли большой x. 12! это самый большой факториал, который может быть сохранен в 32-битном целочисленном, поэтому просто проверьте, больше ли x 12.
Чтобы добавить к Натану, вы можете использовать unsigned long long, а затем вы можете хранить до 20!.
Максимальный размер int известен, как и размер long. В последнем случае, вместо того, чтобы немедленно возвращать значение, сохраните его в long, проверьте, больше ли оно, чем int max, и выполните соответствующую ошибку или продолжите рекурсию.
@ jwatts1980 Это будет работать только на 64-битных машинах * Nix. Windows по-прежнему использует 32-битные длины. Также могут быть системы, в которых sizeof(int) == sizeof(long) == sizeof(long long) так что это не будет работать и в этих системах.
@NathanOliver для таких систем все типы будут иметь ширину 64 бита, поэтому в некотором смысле это будет «работать».
@ДэнМ. Как это будет «работать»? Результат никогда не будет больше, чем INT_MAX.
@NathanOliver ах, извините, неправильно прочитал комментарий, на который вы отвечали, и предположил, что вы говорили о факториалах, вписывающихся в целые числа. Если хотите, вы можете обнаружить переполнение с беззнаковыми типами, но это не имеет особого смысла.
Зачем вообще писать такую дрянную рекурсивную функцию? Есть метод, который разворачивает такие рекурсивные функции в циклы, но ваш этого не сделает.
Ответы 1
Факториальная функция — это статическая функция, вывод которой всегда будет одним и тем же при одних и тех же входных данных. Следовательно, мы можем заранее знать, переполнится ли данный вход или нет.
int32_t factorial(int32_t val) {
if (val > 12)
throw std::runtime_error("Input too large for Factorial function (val must be less than 13)");
if (val < 0)
throw std::runtime_error("Input must be non-negative");
if (val == 0)
return 1;
return factorial(val-1) * val;
}
int64_t factorial(int64_t val) {
if (val > 20)
throw std::runtime_error("Input too large for Factorial function (val must be less than 21)");
if (val < 0)
throw std::runtime_error("Input must be non-negative");
if (val == 0)
return 1;
return factorial(val-1) * val;
}
Если вместо этого вы хотите динамически обнаруживать целочисленное переполнение, вам необходимо просмотреть строгие методы обнаружения возможного переполнения.
Спасибо, я не знал, что должен просто проверить значение, прежде чем принимать факториал.
Конечно, вы можете не захотеть выполнять проверку каждого шага/цикла рекурсии, но тогда вы можете не захотеть выполнять рекурсию.
Более общая проверка включает в себя взятие MAX_INT и деление на один из множителей, а затем проверку того, меньше ли результат, чем другой множитель, но это происходит за счет деления.
@GemTaylor В такой простой функции я верю, что компилятор найдет способ оптимизировать логику.
Более быстрая проверка включает в себя первую проверку того, пересекают ли два умножаемых значения битовый порог. Количество битов в одном плюс биты в другом < целевого битового размера (31 или 63 для знака) => все хорошо; больше => все плохо; равны, то вам, возможно, придется сделать деление.
Переполнение целого числа со знаком "если факториал был равен 0 или меньше каждый раз, тем самым находя, где произошло переполнение" является неопределенным поведением (даже если бы это было не так - теоретически оно могло бы переполниться от одного положительного целого числа к другому положительному целому числу).