math - Mod function fails in python for large numbers

Question

This python code

for x in range(20, 50):
    print(x,math.factorial(x),math.pow(2,x), math.factorial(x) % math.pow(2,x)  )

calculates fine up to x=22 but the mod when x>22 is always 0.

Wolframalpha says the results for x>22 are nonzero. For example, when x=23 we get 6815744.

I guess this problem results from how python actually calculates the mod function but was wondering if anyone actually knew.

Answer 1

You are running into floating point limitations; math.pow() returns a floating point number, so both operands are coerced to floats. For x = 23, math.factorial(x) returns an integer larger than what a float can model:

>>> math.factorial(23)
25852016738884976640000
>>> float(math.factorial(23))
2.585201673888498e+22

The right-hand-side operator is a much smaller floating point number (only 7 digits), it is that difference in exponents that causes the modulus operator error out.

Use ** to stick to integers:

for x in range(20, 50):
    print(x, math.factorial(x), 2 ** x, math.factorial(x) % (2 ** x))

Integer operations are only limited to how much memory is available, and for x = 23 the correct value is calculated, continuing to work correctly all the way to x = 49:

>>> x = 23
>>> print(x, math.factorial(x), 2 ** x, math.factorial(x) % (2 ** x))
23 25852016738884976640000 8388608 6815744
>>> x = 49
>>> print(x, math.factorial(x), 2 ** x, math.factorial(x) % (2 ** x))
49 608281864034267560872252163321295376887552831379210240000000000 562949953421312 492581209243648

Note that for even for smaller floating point modulus calculations, you really should be using the math.fmod() function, for reasons explained in the documentation. It too fails for this case however, again because you are reaching beyond the limits of floating point math:

>>> print(x, math.factorial(x), math.pow(2, x), math.fmod(math.factorial(x), math.pow(2, x)))
23 25852016738884976640000 8388608.0 0.0