integer-gmp-1.0.0.0: Integer library based on GMP

GHC.Integer.GMP.Internals

Description

This modules provides access to the `Integer` constructors and exposes some highly optimized GMP-operations.

Note that since `integer-gmp` does not depend on `base`, error reporting via exceptions, `error`, or `undefined` is not available. Instead, the low-level functions will crash the runtime if called with invalid arguments.

Synopsis

# The `Integer` type

data Integer Source

Invariant: `Jn#` and `Jp#` are used iff value doesn't fit in `S#`

Useful properties resulting from the invariants:

• `abs (`S#` _) <= abs (`Jp#` _)`
• `abs (`S#` _) <  abs (`Jn#` _)`

Constructors

 S# !Int# iff value in `[minBound::Int, maxBound::Int]` range Jp# !BigNat iff value in `]maxBound::Int, +inf[` range Jn# !BigNat iff value in `]-inf, minBound::Int[` range

Instances

 Eq Integer Ord Integer

Test whether all internal invariants are satisfied by `Integer` value

Returns `1#` if valid, `0#` otherwise.

This operation is mostly useful for test-suites and/or code which constructs `Integer` values directly.

## Additional `Integer` operations

`Integer` for which only n-th bit is set. Undefined behaviour for negative n values.

Count number of set bits. For negative arguments returns negative population count of negated argument.

Compute greatest common divisor.

gcdExtInteger :: Integer -> Integer -> (#Integer, Integer#) Source

Extended euclidean algorithm.

For `a` and `b`, compute their greatest common divisor `g` and the coefficient `s` satisfying `as + bt = g`.

Since: 0.5.1.0

Compute least common multiple.

Square `Integer`

"`powModInteger b e m`" computes base `b` raised to exponent `e` modulo `abs(m)`.

Negative exponents are supported if an inverse modulo `m` exists.

Warning: It's advised to avoid calling this primitive with negative exponents unless it is guaranteed the inverse exists, as failure to do so will likely cause program abortion due to a divide-by-zero fault. See also `recipModInteger`.

Future versions of `integer_gmp` may not support negative `e` values anymore.

Since: 0.5.1.0

"`recipModInteger x m`" computes the inverse of `x` modulo `m`. If the inverse exists, the return value `y` will satisfy ```0 < y < abs(m)```, otherwise the result is `0`.

Since: 0.5.1.0

# The `BigNat` type

data BigNat Source

Type representing raw arbitrary-precision Naturals

This is common type used by `Natural` and `Integer`. As this type consists of a single constructor wrapping a `ByteArray#` it can be unpacked.

Essential invariants:

• `ByteArray#` size is an exact multiple of `Word#` size
• limbs are stored in least-significant-limb-first order,
• the most-significant limb must be non-zero, except for
• `0` which is represented as a 1-limb.

Constructors

 BN# ByteArray#

Instances

 Eq BigNat Ord BigNat

type GmpLimb = Word Source

Type representing a GMP Limb

type GmpSize = Int Source

Count of `GmpLimb`s, must be positive (unless specified otherwise).

Test whether all internal invariants are satisfied by `BigNat` value

Returns `1#` if valid, `0#` otherwise.

This operation is mostly useful for test-suites and/or code which constructs `Integer` values directly.

Return number of limbs contained in `BigNat`.

CAF representing the value `0 :: BigNat`

CAF representing the value `1 :: BigNat`

Special 0-sized bigNat returned in case of arithmetic underflow

This is currently only returned by the following operations:

• `minusBigNat`
• `minusBigNatWord`

Other operations such as `quotBigNat` may return `nullBigNat` as well as a dummy/place-holder value instead of `undefined` since we can't throw exceptions. But that behaviour should not be relied upon.

NB: `isValidBigNat# nullBigNat` is false

## Conversions to/from `BigNat`

Construct `BigNat` from existing `ByteArray#` containing n `GmpLimb`s in least-significant-first order.

If possible `ByteArray#`, will be used directly (i.e. shared without cloning the `ByteArray#` into a newly allocated one)

Note: size parameter (times `sizeof(GmpLimb)`) must be less or equal to its `sizeofByteArray#`.

Construct 1-limb `BigNat` from `Word#`

Construct BigNat from 2 limbs. The first argument is the most-significant limb.

Equivalent to `word2Int# . bigNatToWord`

Same as `indexBigNat# bn 0#`

Extract n-th (0-based) limb in `BigNat`. n must be less than size as reported by `sizeofBigNat#`.

## `BigNat` arithmetic operations

Returns `nullBigNat` (see `isNullBigNat#`) in case of underflow

Returns `nullBigNat` (see `isNullBigNat#`) in case of underflow

Square `BigNat`

quotRemBigNat :: BigNat -> BigNat -> (#BigNat, BigNat#) Source

If divisor is zero, `(# nullBigNat, nullBigNat #)` is returned

Note: Result of div/0 undefined

div/0 not checked

Version of `powModInteger` operating on `BigNat`s

Since: 1.0.0.0

Version of `powModInteger` for `Word#`-sized moduli

Since: 1.0.0.0

Version of `recipModInteger` operating on `BigNat`s

Since: 1.0.0.0

## `BigNat` comparision predicates

Test if `BigNat` value is equal to zero.

Test for special 0-sized `BigNat` representing underflows.

# Miscellaneous GMP-provided operations

gcdInt :: Int# -> Int# -> Int# Source

Compute greatest common divisor.

Warning: result may become negative if (at least) one argument is `minBound`

Compute greatest common divisor.

Since: 1.0.0.0

Version of `powModInteger` operating on `Word#`s

Since: 1.0.0.0

Version of `recipModInteger` operating on `Word#`s

Since: 1.0.0.0

# Primality tests

Probalistic Miller-Rabin primality test.

"`testPrimeInteger n k`" determines whether `n` is prime and returns one of the following results:

• `2#` is returned if `n` is definitely prime,
• `1#` if `n` is a probable prime, or
• `0#` if `n` is definitely not a prime.

The `k` argument controls how many test rounds are performed for determining a probable prime. For more details, see GMP documentation for `mpz_probab_prime_p()`.

Since: 0.5.1.0

Version of `testPrimeInteger` operating on `BigNat`s

Since: 1.0.0.0

Version of `testPrimeInteger` operating on `Word#`s

Since: 1.0.0.0

Compute next prime greater than `n` probalistically.

According to the GMP documentation, the underlying function `mpz_nextprime()` "uses a probabilistic algorithm to identify primes. For practical purposes it's adequate, the chance of a composite passing will be extremely small."

Since: 0.5.1.0

Version of `nextPrimeInteger` operating on `BigNat`s

Since: 1.0.0.0

Version of `nextPrimeInteger` operating on `Word#`s

Since: 1.0.0.0

# Import/export functions

## Compute size of serialisation

Version of `sizeInBaseInteger` operating on `BigNat`

Since: 1.0.0.0

Compute number of digits (without sign) in given `base`.

This function wraps `mpz_sizeinbase()` which has some implementation pecularities to take into account:

• "`sizeInBaseInteger 0 base = 1`" (see also comment in `exportIntegerToMutableByteArray`).
• This function is only defined if `base >= 2#` and `base <= 256#` (Note: the documentation claims that only `base <= 62#` is supported, however the actual implementation supports up to base 256).
• If `base` is a power of 2, the result will be exact. In other cases (e.g. for `base = 10#`), the result may be 1 digit too large sometimes.
• "`sizeInBaseInteger i 2#`" can be used to determine the most significant bit of `i`.

Since: 0.5.1.0

Version of `sizeInBaseInteger` operating on `Word#`

Since: 1.0.0.0

## Export

Version of `exportIntegerToAddr` operating on `BigNat`s.

Dump `Integer` (without sign) to `addr` in base-256 representation.

``exportIntegerToAddr` i addr e`

See description of `exportIntegerToMutableByteArray` for more details.

Since: 1.0.0.0

Version of `exportIntegerToAddr` operating on `Word`s.

Version of `exportIntegerToMutableByteArray` operating on `BigNat`s.

Since: 1.0.0.0

Dump `Integer` (without sign) to mutable byte-array in base-256 representation.

The call

``exportIntegerToMutableByteArray` i mba offset msbf`

writes

• the `Integer` `i`
• into the `MutableByteArray#` `mba` starting at `offset`
• with most significant byte first if `msbf` is `1#` or least significant byte first if `msbf` is `0#`, and
• returns number of bytes written.

Use "`sizeInBaseInteger i 256#`" to compute the exact number of bytes written in advance for `i /= 0`. In case of `i == 0`, `exportIntegerToMutableByteArray` will write and report zero bytes written, whereas `sizeInBaseInteger` report one byte.

It's recommended to avoid calling `exportIntegerToMutableByteArray` for small integers as this function would currently convert those to big integers in msbf to call `mpz_export()`.

Since: 1.0.0.0

Version of `exportIntegerToMutableByteArray` operating on `Word`s.

Since: 1.0.0.0

## Import

Version of `importIntegerFromAddr` constructing a `BigNat`

Read `Integer` (without sign) from memory location at `addr` in base-256 representation.

``importIntegerFromAddr` addr size msbf`

See description of `importIntegerFromByteArray` for more details.

Since: 1.0.0.0

Version of `importIntegerFromByteArray` constructing a `BigNat`

Read `Integer` (without sign) from byte-array in base-256 representation.

The call

``importIntegerFromByteArray` ba offset size msbf`

• `size` bytes from the `ByteArray#` `ba` starting at `offset`
• with most significant byte first if `msbf` is `1#` or least significant byte first if `msbf` is `0#`, and
• returns a new `Integer`