Why is this so slow? (Stein algorithm implementation)

I’ve written what I believe is a fully tail-recursive implementation of the binary GCD algorithm (often called Stein’s algorithm) for finding the greatest common divisor (GCD) of two numbers.

import Bitwise

gcd : Int -> Int -> Int
gcd a b =
    {- Returns the greatest common divisor (GCD) of a and b. -}
    gcdHelper 1 (abs a) (abs b)


gcdHelper : Int -> Int -> Int -> Int
gcdHelper multiplier a b =
    {- Tail recursive implementation of Binary GCD Algorithm -}
    let
        isEven x =
            Bitwise.or x 1 > x

        double =
            Bitwise.shiftLeftBy 1

        half =
            Bitwise.shiftRightBy 1
    in
    if a == b || a == 1 || b == 0 then
        multiplier * a

    else if b == 1 || a == 0 then
        multiplier * b

    else
        case ( isEven a, isEven b ) of
            ( True, True ) ->
                gcdHelper (double multiplier) (half a) (half b)

            ( True, False ) ->
                gcdHelper multiplier (half a) b

            ( False, True ) ->
                gcdHelper multiplier a (half b)

            ( False, False ) ->
                if a > b then
                    gcdHelper multiplier (half (a - b)) b

                else
                    gcdHelper multiplier (half (b - a)) a

This seems to work great for small numbers, however when I try truly large numbers (e.g. `gcd 798734982734 4901237128736187236817268371) it seems to hang forever. Whereas asking this online GCF calculator to find the answer for the same two numbers using Stein’s algorithm (which it is presumably doing in javascript) is almost instantaneous (it completes as you type).

Have I done something wrong, made a silly mistake, or is this somehow a limitation of the way Elm uses the javascript event loop?

If I put that number in the repl it truncates it:

> 7987349827344901237128736187236817268371 
4680809175445107000 : number

The number is bigger than the largest Int that Elm can represent (which is ~ 2^53, since Ints are really 64-bit Floats in Elm and Javascript). Perhaps the bad arithmetic is even causing your algorithms to infinite loop?

There are some big integer packages for Elm, never tried them myself though. For example:

https://package.elm-lang.org/packages/cmditch/elm-bigint/latest/

1 Like

Arghh, it’s worse than that, but thank you for pointing me in the right direction! I think Elm must just be using JavaScript’s built-in bitshift operators. After you pointed this out I rapidly discovered that JavaScript converts numbers to 32 bits signed integers before any bitwise operation and then converts the result back to 64-bit JavaScript numbers. If I use numbers smaller than 2^31 then my algorithm works fine, but anything bigger hangs. I also now wonder if I gain anything at all by using the binary algorithm instead of just using Euclid’s algorithm if there is this double conversion taking place under the hood every time I use a bitwise operator… I’m going to investigate further…

Thanks!

Yes it is, so you are really only safe going up to 32-bits.

I think this has safe implementations for 64-bit:

https://package.elm-lang.org/packages/folkertdev/elm-int64/latest/Int64

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.