Different answers for division in Python 3

In summary: What do you think is the best algorithm to calculate gcd?There is no best algorithm to calculate gcd. It depends on the application.
  • #1
996
29
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 ?
 
Technology news on Phys.org
  • #2
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
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
@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
IssacNewton said:
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.

IssacNewton said:
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
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
IssacNewton said:
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
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.
 

1. What is division in Python 3?

In Python 3, division is a mathematical operation that calculates the quotient of two numbers. It is denoted by the forward slash (/) symbol.

2. How does division in Python 3 handle integer division?

When dividing two integers in Python 3, the result will always be a float. In earlier versions of Python, integer division would result in an integer, but this was changed in Python 3.

3. What is the difference between the / and // symbols in Python 3?

The / symbol represents division in Python 3, while the // symbol represents integer division. This means that the // symbol will always return an integer, while the / symbol may return a float.

4. Can division in Python 3 result in an error?

Yes, division in Python 3 can result in an error if you try to divide by zero. This will result in a ZeroDivisionError.

5. How can I ensure that division in Python 3 returns an exact integer result?

To ensure that division in Python 3 returns an exact integer result, you can use the floor division (//) or modulus (%) operators. These will always return an integer, even if the result would normally be a float.

Suggested for: Different answers for division in Python 3

Replies
2
Views
915
Replies
1
Views
160
Replies
3
Views
1K
Replies
1
Views
1K
Replies
2
Views
1K
Replies
2
Views
2K
Replies
6
Views
1K
Back
Top