Different answers for division in Python 3

[issacnewton]

Hello

Consider the following code in Python3

n = 226553150
m = 1023473145
n*m = 231871064940156750
int(n*m/5) = 46374212988031352
n*m//5 = 46374212988031350

Now since $n*m$ is divisible by $5$, both should be give the same answer. But the first is wrong and second is correct. What is happening here ?

 

[jim mcnamara]

Limits of precision. The internal representation of real numbers (In this case integers) in base python comes from the C language - in which language most of python was written.

There were/are internal add in libraries for python to handle so-called bignum applications. In python 3.0 this is supposed to be handled automagically.

https://www.python.org/dev/peps/pep-0237/

You declare int() by forcing the system to use int as the datatype.

So what datatype did you use for n and m? Do you know?

 

[issacnewton]

n and m are supposed to be positive integers. And in Python, we don't do any declarations. This is part of the code to calculate least common multiple.

# Uses python3
import sys

def lcm_efficient(a, b):
    def euclidgcd(a,b):
        if b == 0:
            return a
        remainder = a%b
        return euclidgcd(b, remainder) 
    return a*b // euclidgcd(a,b)

if __name__ == '__main__':
    input = sys.stdin.read()
    a, b = map(int, input.split())
    print(lcm_efficient(a, b))

So when I have a=226553150 and b = 1023473145, I get this weird behavior in the return statement of lcm_efficient function.
Initially I had

int(a*b / euclidgcd(a,b)

And for this particular input of a and b, the LCM is off by 2. So I changed the code. I used the property of the LCM and GCD that
LCM(a, b) x GCD(a, b) = a x b, to calculate LCM.

 

[Ibix]

@jim mcnamara is correct. n*m/5 evaluates to a float, with attendant loss of precision. To see this, try

type(n*m)   # <class 'int'>
type(n*m/5) # <class 'float'>

 

[PeterDonis]

n and m are supposed to be positive integers.

But the / division operator in Python 3 is a float division operator, as others have pointed out. And floats, unlike Python 3 integers, have limited precision. Python 3 integers can exactly represent arbitrarily large integers (in Python 2 this was the "long" type, the "int" type was limited to 32 or 64 bit integers, depending on your platform). So you need to decide what the requirements are for your application.

This is part of the code to calculate least common multiple.

For this application you need exact results, so you want to avoid floats altogether, which means you cannot use the / division operator. Using the // operator, as your revised code does, should be fine for this application; this will always return an integer. If n is not evenly divisible by m, n // m will return the largest integer less than (n divided by m), which in general might not be what is wanted. But a * b will always be evenly divisible by gcd(a, b), so this isn't an issue for your case.

 

[issacnewton]

Thanks. It makes sense now. So I should just avoid floats here. Apart from integer division operator $//$, is there anything I could have done here ?

 

[PeterDonis]

Apart from integer division operator //////, is there anything I could have done here ?

A couple of suggestions, more for long-term usability than anything else:

(1) The euclidgcd function should be defined in global scope, not inside lcm_efficient, since euclid_gcd is useful in its own right.

(2) For large numbers, euclidgcd as you've written it can overflow the stack because it recursively calls itself. It's mathematically more elegant to write it that way, but the stack overflow can create practical problems. If you're going to make heavy use of this code with large numbers, you might want to consider rewriting euclidgcd to use a while loop instead of a recursive call.

 

[issacnewton]

Thanks Peter. You are right about euclid_gcd function. For large numbers, recursion will reach maximum depth. So iterative algorithm would be better for gcd.