Why does this n choose r python code not work?

Question

These 2 variations of n choose r code got different answer although followed the correct definition

I saw that this code works,

import math
def nCr(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

But mine did not:

import math
def nCr(n,r):
    f = math.factorial
    return int(f(n) / (f(r) * f(n-r)))

Use test case nCr(80,20) will show the difference in result. Please advise why are they different in Python 3, thank you!

No error message. The right answer should be 3535316142212174320, but mine got 3535316142212174336.

Answer 1

That's because int(a / b) isn't the same as a // b.

int(a / b) evaluates a / b first, which is floating-point division. And floating-point numbers are prone to inaccuracies, roundoff errors and the like, as .1 + .2 == 0.30000000000000004. So, at some point, your code attempts to divide really big numbers, which causes roundoff errors since floating-point numbers are of fixed size, and thus cannot be infinitely precise.

a // b is integer division, which is a different thing. Python's integers can be arbitrarily huge, and their division doesn't cause roundoff errors, so you get the correct result.

Speaking about floating-point numbers being of fixed size. Take a look at this:

>>> import math
>>> f = math.factorial
>>> f(20) * f(80-20)
20244146256600469630315959326642192021057078172611285900283370710785170642770591744000000000000000000
>>> f(80) / _
3.5353161422121743e+18

The number 3.5353161422121743e+18 is represented exactly as shown here: there is no information about the digits after the last 3 in 53...43 because there's nowhere to store it. But int(3.5353161422121743e+18) must put something there! Yet it doesn't have enough information. So it puts whatever it wants to so that float(int(3.5353161422121743e+18)) == 3.5353161422121743e+18.