Kesong Xie Kesong Xie - 8 months ago 44
Python Question

Python: Recursive call counting ways of walking grid yield incorrect answer when grid size is too large


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)

I have two approaches for this, first is to use a recursive algorithm enhanced by memoization, and the second one is to use binomial counting strategy

Recursive Way

def gridMovingCount(x, y, cache):
if x == 0 or y == 0:
return 1
elif str(x)+":"+str(y) in cache:
return cache[str(x)+":"+str(y)]
cache[str(x)+":"+str(y)] = gridMovingCount(x-1, y, cache) + gridMovingCount(x, y-1, cache)
return cache[str(x)+":"+str(y)]

Binomial counting

def gridMovingCountByBinomial(x, y):
return int(math.factorial(x + y) / (math.factorial(x) * math.factorial(y)))

These two ways give the same answers when x and y are relative small

#the same result
print(gridMovingCount(20, 20, cache)) #137846528820
print(gridMovingCountByBinomial(20, 20)) #137846528820

When x and y are large

# gave different result
print(gridMovingCount(50, 50, cache)) #100891344545564193334812497256
print(gridMovingCountByBinomial(50, 50)) #100891344545564202071714955264

What is the explanation for this. Stack overflow of some sort? However, it does not throw any exception. Are there any way to overcome this for recursive call?

Answer Source

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:

from math import factorial
print(int(factorial(23)/2))  # 12926008369442488320000
print(int(factorial(23)//2))  # 12926008369442488320000

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))