Imagine you start at the corner of an X by Y grid. You can only move in two directions: right and down. How many possible paths are there for you to go from (0, 0) to (X, Y)
def gridMovingCount(x, y, cache):
if x == 0 or y == 0:
elif str(x)+":"+str(y) in cache:
cache[str(x)+":"+str(y)] = gridMovingCount(x-1, y, cache) + gridMovingCount(x, y-1, cache)
def gridMovingCountByBinomial(x, y):
return int(math.factorial(x + y) / (math.factorial(x) * math.factorial(y)))
#the same result
print(gridMovingCount(20, 20, cache)) #137846528820
print(gridMovingCountByBinomial(20, 20)) #137846528820
# gave different result
print(gridMovingCount(50, 50, cache)) #100891344545564193334812497256
print(gridMovingCountByBinomial(50, 50)) #100891344545564202071714955264
The issue here is a limitation of floating point arithmetic and the differences between python2 and python3 in regards to the division operator.
In python 2 the division operator returns the floor of the result of a division if the arguments are ints or longs (as in this case) or a reasonable approximation if the arguments are floats or complex. Python 3 on the other hand returns a reasonable approximation of the division independent of argument type.
At small enough numbers this approximation is close enough that the cast back to an integer ends up with the same result as the python 2 version. However as the result gets large enough the floating point representation is not a sufficient approximation to end up with the correct result when casting back to an int.
In python2.2 the floor division operator was introduced
// and in python3 true division replaced classic division (see origin of terminology here: https://www.python.org/dev/peps/pep-0238/)
#python2 from math import factorial print(int(factorial(23)/2)) # 12926008369442488320000 print(int(factorial(23)//2)) # 12926008369442488320000
#python3 from math import factorial print(int(factorial(23)/2)) # 12926008369442489106432 print(int(factorial(23)//2)) # 12926008369442488320000
The upshot of all this is that for your binomial function you can remove the cast to int and use the explicit floor division operator to get the correct results returned.
def gridMovingCountByBinomial(x, y): return math.factorial(x + y) // (math.factorial(x) * math.factorial(y))