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

Copyright (c) 2011 Daniel Fischer MIT Daniel Fischer Provisional Non-portable (GHC extensions) None Haskell98

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 -> a Source

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) 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 -> Bool Source

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.