arithmoi-0.1.0.1: Efficient basic number-theoretic functions. Primes, powers, integer logarithms.

Portability Non-portable (GHC extensions) Provisional Daniel Fischer

Math.NumberTheory.GCD

Description

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.

Synopsis

# Documentation

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

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 <= 32`, 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)Source

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

Satisfies:

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

d == gcd a b
```

and, for signed types,

``` 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 -> BoolSource

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.