Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Python Different answers for division in Python 3

  1. Oct 13, 2018 at 5:03 AM #1
    Hello

    Consider the following code in Python3
    Code (Text):

    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 ?
     
  2. jcsd
  3. Oct 13, 2018 at 7:17 AM #2

    jim mcnamara

    User Avatar

    Staff: Mentor

    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?
     
    Last edited: Oct 13, 2018 at 7:27 AM
  4. Oct 13, 2018 at 11:07 AM #3
    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.
    Code (Text):

    # 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
    Code (Text):
    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.
     
  5. Oct 13, 2018 at 11:24 AM #4

    Ibix

    User Avatar
    Science Advisor

    @jim mcnamara is correct. n*m/5 evaluates to a float, with attendant loss of precision. To see this, try
    Code (Python):
    type(n*m)   # <class 'int'>
    type(n*m/5) # <class 'float'>
     
  6. Oct 13, 2018 at 9:42 PM #5

    PeterDonis

    Staff: Mentor

    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.

    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.
     
  7. Oct 13, 2018 at 10:14 PM #6
    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 ?
     
  8. Oct 13, 2018 at 10:39 PM #7

    PeterDonis

    Staff: Mentor

    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.
     
  9. Oct 13, 2018 at 10:50 PM #8
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted