The Old New Thing

# Calculating integer factorials in constant time, taking advantage of overflow behavior

Raymond Chen

For some reason, people on StackOverflow calculate factorials a lot. (Nevermind that it’s not necessarily the best way to evaluate a formula.) And you will see factorial functions like this:

```int factorial(int n)
{
if (n < 0) return -1; // EDOM
int result = 1;
for (int i = 2; i <= n; i++) result *= i;
return result;
}
```

But you can do better than this by taking advantage of undefined behavior.

Since signed integer overflow results in undefined behavior in C/C++, you can assume that the result of the factorial does not exceed `INT_MAX`, which is 2147483647 for 32-bit signed integers. This means that n cannot be greater than 12.

So use a lookup table.

```int factorial(int n)
{
static const int results[] = {
1,
1,
1 * 2,
1 * 2 * 3,
1 * 2 * 3 * 4,
1 * 2 * 3 * 4 * 5,
1 * 2 * 3 * 4 * 5 * 6,
1 * 2 * 3 * 4 * 5 * 6 * 7,
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8,
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12,
};
if (n < 0) return -1; // EDOM
return results[n]; // undefined behavior if n > 12
}
```

(If you have 64-bit signed integers, then the table needs to go up to 20.)

The fact that you have undefined behavior if n > 12 is hardly notable, because the original code also had undefined behavior if n > 12. You just replaced one undefined behavior with another.

If you want to simulate two’s complement overflow, for example, to preserve bug-for-bug compatibility, or because the function was defined to compute unsigned instead of signed factorial,¹ then you can do that by extending the table just a little bit more. You will need only entries up to 33! because because 34! is an exact multiple of 2³². The result of `factorial(n)` is zero for n ≥ 34, assuming 32-bit integers.

```int factorial(int n)
{
static const int results[] = {
1, // 0!
1, // 1!
2, // 2!
6, // 3!
24, // 4!
120, // 5!
720, // 6!
5040, // 7!
40320, // 8!
362880, // 9!
3628800, // 10!
39916800, // 11!
479001600, // 12!
1932053504, // 13!
1278945280, // 14!
2004310016, // 15!
2004189184, // 16!
4006445056, // 17!
3396534272, // 18!
109641728, // 19!
2192834560, // 20!
3099852800, // 21!
3772252160, // 22!
862453760, // 23!
3519021056, // 24!
2076180480, // 25!
2441084928, // 26!
1484783616, // 27!
2919235584, // 28!
3053453312, // 29!
1409286144, // 30!
738197504, // 31!
2147483648, // 32!
2147483648, // 33!
};
if (n < 0) return -1; // EDOM
if (n > 33) return 0; // overflowed to zero
return results[n];
```

I didn’t calculate all those numbers myself. I wrote a program to do it.

```class Program
{
public static void Main() {
uint result = 1;
uint n = 0;
while (result != 0) {
System.Console.WriteLine(" {0,10}, // {1}!", result, n);
result *= ++n;
}
}
}
```

Extending the above algorithm to 64-bit integers is left as an exercise.

¹ Unsigned arithmetic is defined by the C/C++ standards to be modulo 2 for some n.