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?