Как обработать целочисленное переполнение при расчете факториала> 31

Question

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

int ft_iterative_factorial(int nb)
{
  int i;
  int n;
  int res;

  i = 1;
  n = nb;
  res = nb;
  while (i < nb)
  {
    if (nb == 1 || nb == 0)
    {
      res = 1;
      break ;
    }
    res = res * (n - 1);
    i++;
    n--;
  }
  return ((nb < 0 || nb > 31) ? 0 : res);
}

Answer 1

Для максимально допустимого факториала вы можете использовать unsigned long long для типа возврата этой функции.И ваша функция - рекурсивный стиль, время выполнения медленнее, чем нерекурсивный стиль.Я думаю, что здесь хорошее решение

unsigned long long ft_iterative_factorial(int nb)
{
    unsigned long long result = 1;

    for (int i = 2; i <= nb; i++)
    {
        result = result * (unsigned long long)i;
    }

    return result;
}

int main()
{
    cout << ft_iterative_factorial(17) << endl;
    return 0;
}

Answer 2

Ваша функция действительно сложна.

Рассмотрим скорее эту реализацию:

int ft_iterative_factorial(int nb)
{
  int res = 1;

  for (int i = 2; i <= nb; i++)
  {
    res = res * i;
  }

  return res;
}

Ваш тест return ( nb < 0 ? 0 : res); не имеет особого смысла после цикла, вы должны сделать это доцикл, и при этом if (nb == 1 || nb == 0) внутри цикла.Но в любом случае эти тесты бессмысленны в моем коде.

int, вероятно, является 32-битным типом, а 32-битного недостаточно для хранения 16!.

Либо используйте long long (обычно 64бит) вместо int (но тогда вы будете ограничены 21 или около того), или обрабатывать случаи, когда значение> 16 в противном случае.

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

Answer 3

Вы используете целые числа со знаком для вычисления, и переполнение со знаком является неопределенным поведением.Так что, какой бы код ни возвращал, он верен в соответствии со стандартом C.Обычно происходит то, что вы просто получаете младшие биты правильного результата.Который, поскольку он подписан как int, может быть отрицательным.

Если вы хотите получить приблизительный результат только для больших чисел, то почему бы не изменить свой код на использование double?Для небольших номеров, таких как 3!вы все равно получите 6, но после 17 или около того вы получите что-то вроде 4.643 + E8, что означает 4.643 * 10 ^ 8.У типа double в конечном счете закончатся экспоненты, но это продвинет вас намного дальше, чем даже unsigned long long.

Answer 4

Либо используйте long long, либо попытайтесь оптимизировать свои вычисления, если это возможно.

Наконец, альтернативой является поиск больших целочисленных библиотек.