I implemented an lcm problem using the following algorithm in python. My code is given below :

# Uses python3
import sys

def gcd_efficient(a, b):
    #current_gcd = 1
    #for d in range(2, min(a, b) + 1):
    #   if a % d == 0 and b % d == 0:
    #        if d > current_gcd:
    #            current_gcd = d

    #return current_gcd

    remainder = max(a, b) % min(a, b)
    newMax = min(a, b)
    if remainder == 0:
        return newMax

    return  gcd_efficient(newMax, remainder)


def lcm_efficient(a, b):
    #for l in range(1, a*b + 1):
    #   if l % a == 0 and l % b == 0:
    #        return l

    product = a*b
    gcd = gcd_efficient(a, b)
    lcm = product/gcd
    return int(lcm)

print(lcm_efficient(226553150, 1023473145))

Now I have used the above code to compute the lcm of large integers being as input.

However I find that for some large integers: for example, when the input is: Input: 226553150 1023473145 The output from the python console is: 46374212988031352 But the actual output should be: 46374212988031350

The actual output is differing from the given output by just 2. However, what confuses me is that why is the python interpreter giving errors in output upon executing the above code.

Can this error be nullified?

Waiting for the answers!!

upvote
  flag
Python is able to represent large numbers without loss of precision, so that should be fine. The value with the 2 at the end can't be a multiple of the two numbers, because both are multiples of five, so much is clear. Question now is whether your algorithm is wrong. If so, at what point exactly does it fail? I'm aware that this requires a bunch of debugging with large numbers, but I'm afraid there's no help to that. – Ulrich Eckhardt
upvote
  flag
I implemented the same algorithm in C++ and it works fine. So I think the algorithm is fairly correct. and if the algorithm was wrong the difference between the actual output and the output given in the console would have been considerable, but here the difference is just 2. – suraj Mandal
upvote
  flag
I believe that a wrong algorithm cannot produce an answer with such a precision as compared to the correct output produced by the correct algorithm. – suraj Mandal
upvote
  flag
Please accept that the issue is not with the precision of Python arithmetic. – BoarGules

1 Answers 11

Your problem is here:

lcm = product/gcd

It should be

lcm = product//gcd

to guarantee integer division. Your translation from C++ assumed that the / operator works identically in C++ and Python. And in Python 2 it does. But not in Python 3. In Python 3, / calls for floating point division, so the original version called for both operands to be converted to floats (losing precision in the process) followed by floating-point division. Your return statement converts the floating-point result back to int, masking the problem.

upvote
  flag
thanks for solving the issue!!! – suraj Mandal
upvote
  flag
If the answer worked for you, please accept it. – BoarGules

Not the answer you're looking for? Browse other questions tagged or ask your own question.