Copyright | (c) 2011 Daniel Fischer |
---|---|

License | MIT |

Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |

Stability | Provisional |

Portability | Non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell2010 |

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

Calculate the greatest common divisor using the binary gcd algorithm.
Depending on type and hardware, that can be considerably faster than

but it may also be significantly slower.`gcd`

There are specialised functions for

and `Int`

and rewrite rules
for those and `Word`

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

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 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.