Different answers for division in Python 3

  • Python
  • Thread starter issacnewton
  • Start date
  • #1
912
19
Hello

Consider the following code in Python3
Code:
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 ?
 

Answers and Replies

  • #2
jim mcnamara
Mentor
4,229
2,797
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:
  • Like
Likes Ibix
  • #3
912
19
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:
# 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:
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.
 
  • #4
Ibix
Science Advisor
Insights Author
2020 Award
7,396
6,481
@jim mcnamara is correct. n*m/5 evaluates to a float, with attendant loss of precision. To see this, try
Python:
type(n*m)   # <class 'int'>
type(n*m/5) # <class 'float'>
 
  • Like
Likes BvU
  • #5
PeterDonis
Mentor
Insights Author
2020 Award
32,928
11,418
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.
 
  • #6
912
19
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 ?
 
  • #7
PeterDonis
Mentor
Insights Author
2020 Award
32,928
11,418
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.
 
  • #8
912
19
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.
 

Related Threads on Different answers for division in Python 3

Replies
6
Views
4K
Replies
18
Views
4K
Replies
10
Views
1K
  • Last Post
Replies
4
Views
2K
Replies
4
Views
1K
Replies
27
Views
3K
Replies
18
Views
1K
Replies
3
Views
1K
  • Last Post
Replies
5
Views
1K
Top