Предвидеть факторный переполнение

Question

Мне интересно, как я мог предвидеть, приведет ли следующая итерация к целочисленному переполнению при вычислении факториала F или нет?

Допустим, на каждой итерации у меня есть int I, а максимальное значение - MAX_INT.

Звучит как домашнее задание, я знаю. Это не. Это просто я задаю себе "глупые" вопросы.

Добавление

Я подумал, что учитывая количество битов (ширина, которую может принимать целое число в битах), я мог бы округлить число I до следующей степени двух и определить, будет ли сдвиг влево превышать биты. Но как это будет выглядеть алгоритмически?

Answer 1

Альтернативный совет:

a * b ≤ MAX_INT 

эквивалентно

a ≤ MAX_INT / b

если b> 0.

Answer 2

Факториалы - это серии умножений, а количество битов, необходимых для хранения результата умножения, является суммой битов двух мультипликатов. Таким образом, сохраняйте итоговое количество битов, использованных в вашем результате, и текущее количество бит, необходимое для хранения значения, на которое вы умножаете. Когда это число превышает количество оставшихся битов, вы собираетесь переполниться. 1001 *

Answer 3

Если вы получили m = (n-1)! и собираетесь умножить на n, вы можете защититься от переполнения, проверив, что

   m <= MAX_INT / n

Answer 4

Вы, вероятно, можете использовать Формула аппроксимации Стирлинга , которая говорит, что

ln (n!) = N * ln (n) - n + ln (2 * pi * n) / 2 + O (1 / n)

и будет достаточно точным.

На самом деле вам не нужно пытаться умножать и т. Д. Конечно, это не дает прямого ответа на то, что вы спросили, но, учитывая, что вы просто любопытны, надеюсь, это поможет.