Kesong Xie - 2 months ago 17

Python Question

Problem:

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

else:

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

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