Math.NumberTheory.GCD

This module exports GCD and coprimality test using the binary gcd algorithm and GCD with the extended Euclidean algorithm.

Efficiently counting the number of trailing zeros, the binary gcd algorithm can perform considerably faster than the Euclidean algorithm on average. For Int, GHC has a rewrite rule to use GMP's fast gcd, depending on hardware and/or GMP version, that can be faster or slower than the binary algorithm (on my 32-bit box, binary is faster, on my 64-bit box, GMP). For Word and the sized IntN/WordN types, there is no rewrite rule (yet) in GHC, and the binary algorithm performs consistently (so far as my tests go) much better (if this module's rewrite rules fire).

When using this module, always compile with optimisations turned on to benefit from GHC's primops and the rewrite rules.

Documentation

binaryGCD :: (Integral a, Bits a) => a -> a -> a

Calculate the greatest common divisor using the binary gcd algorithm. Depending on type and hardware, that can be considerably faster than gcd but it may also be significantly slower.

There are specialised functions for Int and Word and rewrite rules for those and IntN and WordN, N <= 64, to use the specialised variants. These types are worth benchmarking, others probably not.

It is very slow for Integer (and probably every type except the abovementioned), I recommend not using it for those.

Relies on twos complement or sign and magnitude representaion for signed types.

extendedGCD :: Integral a => a -> a -> (a, a, a)

Calculate the greatest common divisor of two numbers and coefficients for the linear combination.

For signed types satisfies:

case extendedGCD a b of
  (d, u, v) -> u*a + v*b == d
               && d == gcd a b

For unsigned and bounded types the property above holds, but since u and v must also be unsigned, the result may look weird. E. g., on 64-bit architecture

extendedGCD (2 :: Word) (3 :: Word) == (1, 2^64-1, 1)

For unsigned and unbounded types (like Natural) the result is undefined.

For signed types we also have

abs u < abs b || abs b <= 1

abs v < abs a || abs a <= 1

(except if one of a and b is minBound of a signed type).

coprime :: (Integral a, Bits a) => a -> a -> Bool

Test whether two numbers are coprime using an abbreviated binary gcd algorithm. A little bit faster than checking binaryGCD a b == 1 if one of the arguments is even, much faster if both are even.

The remarks about performance at binaryGCD apply here too, use this function only at the types with rewrite rules.

Relies on twos complement or sign and magnitude representaion for signed types.