CODEWITHSUNDEEP
python-2.7math
aquagremlin
aquagremlin

Reputation: 3549

Mod function fails in python for large numbers

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.

Upvotes: 4

Views: 3414

Answers (2)

Mohammed Ismaeil
Mohammed Ismaeil

Reputation: 1

Yes, You are correct for large numbers modulus gives wrong numbers especially with factorial numbers.

for example :

import math

def comb(n,r):
    res= math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
    return(float(res))
    
sum1=0
num=888

for r in range(0,num+1):
    sum1 +=comb(num,r)
    

    
print(sum1 % 1000000)

gives wrong answer 252480 but the correct answer is 789056 .

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1124788

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

Upvotes: 3

Related Questions