Find LCM of 2 numbers without using GCD

[Albert Chan]

(07-30-2018 07:43 PM)Thomas Klemm Wrote:  I wouldn't call that "brute force". It uses \(\frac{a+b}{\gcd(a,b)}-2\) additions.
This can be huge as in your example or then rather small if \(\gcd(a, b)\) is in the same order as \(a\) and \(b\).

On the other hand only addition is used which can be a benefit depending on the instruction set.

Your formula is correct, post #3 lcm(54321, 12345) required 22,220 additions.

The code search lcm by finding positive integers k1, k2, such that min(k1) * a = min(k2) * b
It does not allow k1 or k2 to jump ahead, but to walk the number line.
I think it is safe to say this is a brute force method.

It might still be fast for certain inputs. Sometimes, brute force is all we need ...

For calculator without modulus, we can also use binary-gcd

Code:

def binary_gcd(a, b):
    while 1:
        if a < b: a, b = b, a   # b smaller
        if a == b or not b: return a
        c = b+b
        while c < a: c = c+c    # reduce a by two-thirds or more
        a = c - a if a >= 0.75*c else a - c//2

For comparison, for binary_gcd(54321, 12345), additions + subtractions = 27 + 7 = 34