Anticipate factorial overflow

Question

Hi

I'm wondering how could I anticipate whether the next iteration will generate an integer overflow while calculating the factorial F or not?

Let's say that at each iteration I have an int I and the maximum value is MAX_INT.

It sounds like a homework, I know. It's not. It's just me asking myself "stupid" questions.

Addendum

I though about, given a number of BITS (the width an integer can take, in bits), I could round up the number I to the next power of two, and detect if a shift to left would exceed BITS. But how would that look like, algorithmically?

Answer 1

Factorials are a series of multiplications, and the number of bits needed to hold the result of a multiplication is the sum of the bits of the two multiplicands. So, keep a running total of how many bits are used in your result, and the current number of bits needed to hold the value you are multiplying in. When that's greater than the number of bits left, you're about to overflow.

Answer 2

Alternative hint:

a * b ≤ MAX_INT 

is equivalent to

a ≤ MAX_INT / b

if b > 0.

Answer 3

If you've so far got m = (n-1)! and you're about to multiply by n, you can guard against overflow by checking that

   m <= MAX_INT / n

Answer 4

You can probably use Stirling's Approximation formula which says that

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

and will be quite accurate.

You don't actually need to go about trying to multiply etc. Of course, this does not directly answer what you asked, but given that you are just curious, hope this helps.