Почему, когда я вычисляю большой факториал, я получаю отрицательное число?
https://stackoverflow.com/questions/236335
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Итак, простая процедура: вычислить факториал.Код выглядит следующим образом.
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», который я создал некоторое время назад и который может подойти!), чтобы не столкнуться с этой проблемой снова?
Решение
2 ^ 32 не дает вам ограничения для целых чисел со знаком.
Целочисленное ограничение со знаком на самом деле 2147483647 (если вы разрабатываете для Windows с использованием инструментов MS, другие наборы инструментов / платформы будут иметь свои собственные ограничения, которые, вероятно, аналогичны).
Вам понадобится библиотека больших чисел C ++, такая, как эта .
Другие советы
В дополнение к остальным комментариям хотелось бы отметить две серьёзные ошибки в вашем коде.
- У вас нет защиты от отрицательных чисел.
- Факториал нуля равен единице, а не нулю.
Да, вы достигли предела. Int в C ++, по определению, подписан. И нет, С ++ не думает никогда. Если вы скажете ему сделать что-то, он сделает это, даже если это явно неправильно.
Подумайте об использовании библиотеки большого числа. Их много для C ++.
Если вы не укажете подписанный или неподписанный, по умолчанию подписывается. Вы можете изменить это, используя переключатель командной строки на вашем компиляторе.
Просто помните, что C (или C ++) - это язык очень низкого уровня, и он выполняет именно то, что вы говорите ему делать . Если вы скажете ему сохранить это значение в подписанном int, это то, что он будет делать. Вы, , как программист, должны выяснить, когда это проблема. Это не работа языка.
Мой калькулятор Windows ( Start-Run-Calc ) сообщает мне, что
hex (3813186000) = E34899D0
hex (-481781296) = FFFFFFFFE34899D0
Так что да, причина - подписанный лимит. Поскольку факториалы по определению могут быть только положительными и могут быть рассчитаны только для положительных чисел, аргумент и возвращаемое значение должны быть в любом случае беззнаковыми числами. (Я знаю, что все используют int i = 0 in для циклов, как и я. Но оставив в стороне, мы должны всегда использовать беззнаковые переменные, если значение не может быть отрицательным, это хорошая практика IMO).
Общая проблема с факториалами заключается в том, что они могут легко генерировать очень большие числа. Вы можете использовать float, жертвуя при этом точностью, но избегая проблемы переполнения целых чисел.
Ой, подождите, согласно тому, что я написал выше, вы должны сделать это без знака поплавка; -)
У вас проблема переполнения. Факториалы могут легко превышать пределы целых чисел. Вы можете изменить свою функцию, чтобы она возвращала двойные значения, но это только даст вам немного больше места. В приложениях вам часто нужно умножать факториалы на очень маленькие числа, где конечный результат будет помещаться в двойное число, а промежуточные шаги - нет. Вот статья, которая объясняет, как справиться с этой ситуацией:
Если я хорошо помню, short без знака int = max 65535 unsigned int = max 4294967295 без знака long = максимум 4294967295 длинный без знака (Int64) = максимум 18446744073709551615 Отредактированный источник:
