Copyright	(c) Herbert Valerio Riedel 2014
License	BSD3
Maintainer	[email protected]
Stability	provisional
Portability	non-portable (GHC Extensions)
Safe Haskell	None
Language	Haskell2010

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# _)

isValidInteger# :: Integer -> Int# Source

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.

Basic Integer operations

module GHC.Integer

Additional Integer operations

bitInteger :: Int# -> Integer Source

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

popCountInteger :: Integer -> Int# Source

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

gcdInteger :: Integer -> Integer -> Integer Source

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

lcmInteger :: Integer -> Integer -> Integer Source

Compute least common multiple.

sqrInteger :: Integer -> Integer Source

Square Integer

powModInteger :: Integer -> Integer -> Integer -> Integer Source

"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 :: Integer -> Integer -> Integer Source

"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

Additional conversion operations to Integer

wordToNegInteger :: Word# -> Integer Source

bigNatToInteger :: BigNat -> Integer Source

bigNatToNegInteger :: BigNat -> Integer Source

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.

type GmpLimb = Word Source

Type representing a GMP Limb

type GmpLimb# = Word# Source

type GmpSize = Int Source

Count of GmpLimbs, must be positive (unless specified otherwise).

type GmpSize# = Int# Source

isValidBigNat# :: BigNat -> Int# Source

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.

sizeofBigNat# :: BigNat -> GmpSize# Source

Return number of limbs contained in BigNat.

zeroBigNat :: BigNat Source

CAF representing the value 0 :: BigNat

oneBigNat :: BigNat Source

CAF representing the value 1 :: BigNat

nullBigNat :: BigNat Source

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

byteArrayToBigNat# :: ByteArray# -> GmpSize# -> BigNat Source

Construct BigNat from existing ByteArray# containing n GmpLimbs 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#.

wordToBigNat :: Word# -> BigNat Source

Construct 1-limb BigNat from Word#

wordToBigNat2 :: Word# -> Word# -> BigNat Source

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

bigNatToInt :: BigNat -> Int# Source

Equivalent to word2Int# . bigNatToWord

bigNatToWord :: BigNat -> Word# Source

Same as indexBigNat# bn 0#

indexBigNat# :: BigNat -> GmpSize# -> GmpLimb# Source

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

BigNat arithmetic operations

plusBigNat :: BigNat -> BigNat -> BigNat Source

plusBigNatWord :: BigNat -> GmpLimb# -> BigNat Source

minusBigNat :: BigNat -> BigNat -> BigNat Source

Returns nullBigNat (see isNullBigNat#) in case of underflow

minusBigNatWord :: BigNat -> GmpLimb# -> BigNat Source

Returns nullBigNat (see isNullBigNat#) in case of underflow

timesBigNat :: BigNat -> BigNat -> BigNat Source

timesBigNatWord :: BigNat -> GmpLimb# -> BigNat Source

sqrBigNat :: BigNat -> BigNat Source

Square BigNat

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

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

quotRemBigNatWord :: BigNat -> GmpLimb# -> (#BigNat, GmpLimb##) Source

Note: Result of div/0 undefined

quotBigNatWord :: BigNat -> GmpLimb# -> BigNat Source

quotBigNat :: BigNat -> BigNat -> BigNat Source

remBigNat :: BigNat -> BigNat -> BigNat Source

remBigNatWord :: BigNat -> GmpLimb# -> Word# Source

div/0 not checked

gcdBigNat :: BigNat -> BigNat -> BigNat Source

gcdBigNatWord :: BigNat -> Word# -> Word# Source

powModBigNat :: BigNat -> BigNat -> BigNat -> BigNat Source

Version of powModInteger operating on BigNats

Since: 1.0.0.0

powModBigNatWord :: BigNat -> BigNat -> GmpLimb# -> GmpLimb# Source

Version of powModInteger for Word#-sized moduli

Since: 1.0.0.0

recipModBigNat :: BigNat -> BigNat -> BigNat Source

Version of recipModInteger operating on BigNats

Since: 1.0.0.0

BigNat logic operations

shiftRBigNat :: BigNat -> Int# -> BigNat Source

shiftLBigNat :: BigNat -> Int# -> BigNat Source

testBitBigNat :: BigNat -> Int# -> Bool Source

andBigNat :: BigNat -> BigNat -> BigNat Source

xorBigNat :: BigNat -> BigNat -> BigNat Source

popCountBigNat :: BigNat -> Int# Source

orBigNat :: BigNat -> BigNat -> BigNat Source

bitBigNat :: Int# -> BigNat Source

Specialised version of

bitBigNat = shiftLBigNat (wordToBigNat 1##)

avoiding a few redundant allocations

BigNat comparision predicates

isZeroBigNat :: BigNat -> Bool Source

Test if BigNat value is equal to zero.

isNullBigNat# :: BigNat -> Int# Source

Test for special 0-sized BigNat representing underflows.

compareBigNatWord :: BigNat -> GmpLimb# -> Ordering Source

compareBigNat :: BigNat -> BigNat -> Ordering Source

eqBigNatWord :: BigNat -> GmpLimb# -> Bool Source

eqBigNatWord# :: BigNat -> GmpLimb# -> Int# Source

eqBigNat :: BigNat -> BigNat -> Bool Source

eqBigNat# :: BigNat -> BigNat -> Int# Source

gtBigNatWord# :: BigNat -> GmpLimb# -> Int# Source

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

gcdWord :: Word# -> Word# -> Word# Source

Compute greatest common divisor.

Since: 1.0.0.0

powModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# -> GmpLimb# Source

Version of powModInteger operating on Word#s

Since: 1.0.0.0

recipModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# Source

Version of recipModInteger operating on Word#s

Since: 1.0.0.0

Primality tests

testPrimeInteger :: Integer -> Int# -> Int# Source

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

testPrimeBigNat :: BigNat -> Int# -> Int# Source

Version of testPrimeInteger operating on BigNats

Since: 1.0.0.0

testPrimeWord# :: GmpLimb# -> Int# -> Int# Source

Version of testPrimeInteger operating on Word#s

Since: 1.0.0.0

nextPrimeInteger :: Integer -> Integer Source

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

nextPrimeBigNat :: BigNat -> BigNat Source

Version of nextPrimeInteger operating on BigNats

Since: 1.0.0.0

nextPrimeWord# :: GmpLimb# -> GmpLimb# Source

Version of nextPrimeInteger operating on Word#s

Since: 1.0.0.0

Import/export functions

Compute size of serialisation

sizeInBaseBigNat :: BigNat -> Int# -> Word# Source

Version of sizeInBaseInteger operating on BigNat

Since: 1.0.0.0

sizeInBaseInteger :: Integer -> Int# -> Word# Source

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

sizeInBaseWord# :: Word# -> Int# -> Word# Source

Version of sizeInBaseInteger operating on Word#

Since: 1.0.0.0

Export

exportBigNatToAddr :: BigNat -> Addr# -> Int# -> IO Word Source

Version of exportIntegerToAddr operating on BigNats.

exportIntegerToAddr :: Integer -> Addr# -> Int# -> IO Word Source

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

exportWordToAddr :: Word -> Addr# -> Int# -> IO Word Source

Version of exportIntegerToAddr operating on Words.

exportBigNatToMutableByteArray :: BigNat -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Source

Version of exportIntegerToMutableByteArray operating on BigNats.

Since: 1.0.0.0

exportIntegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Source

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

exportWordToMutableByteArray :: Word -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Source

Version of exportIntegerToMutableByteArray operating on Words.

Since: 1.0.0.0

Import

importBigNatFromAddr :: Addr# -> Word# -> Int# -> IO BigNat Source

Version of importIntegerFromAddr constructing a BigNat

importIntegerFromAddr :: Addr# -> Word# -> Int# -> IO Integer Source

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

importBigNatFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> BigNat Source

Version of importIntegerFromByteArray constructing a BigNat

importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer Source

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

The call

importIntegerFromByteArray ba offset size msbf

reads

• 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

Since: 1.0.0.0