ghc-bignum-1.3: GHC BigNum library

Copyright | (c) Sylvain Henry 2019 (c) Herbert Valerio Riedel 2014
License | BSD3
Maintainer | sylvain@haskus.fr
Stability | provisional
Portability | non-portable (GHC Extensions)
Safe Haskell | None
Language | Haskell2010

GHC.Num.Integer

Contents

- Useful constants
- Conversion with...
  - `Int`
  - `BigNat`
  - `Word`
  - `Natural`
  - `Int64`/`Word64`
  - Floating-point
  - `Addr#`
  - Limbs
- Predicates
- Comparison
- Arithmetic
- Bit operations
- Miscellaneous

Description

The `Integer` type.

Synopsis

- data Integer
  - = IS Int#
  - | IP ByteArray#
  - | IN ByteArray#
- integerCheck :: Integer -> Bool
- integerCheck# :: Integer -> Bool#
- integerZero :: Integer
- integerOne :: Integer
- integerFromInt# :: Int# -> Integer
- integerFromInt :: Int -> Integer
- integerToInt# :: Integer -> Int#
- integerToInt :: Integer -> Int
- integerFromBigNat# :: BigNat# -> Integer
- integerFromBigNatNeg# :: BigNat# -> Integer
- integerFromBigNatSign# :: Int# -> BigNat# -> Integer
- integerToBigNatSign# :: Integer -> (# Int#, BigNat# #)
- integerToBigNatClamp# :: Integer -> BigNat#
- integerFromWord# :: Word# -> Integer
- integerFromWord :: Word -> Integer
- integerFromWordNeg# :: Word# -> Integer
- integerFromWordSign# :: Int# -> Word# -> Integer
- integerToWord# :: Integer -> Word#
- integerToWord :: Integer -> Word
- integerFromNatural :: Natural -> Integer
- integerToNaturalClamp :: Integer -> Natural
- integerToNatural :: Integer -> Natural
- integerToNaturalThrow :: Integer -> Natural
- integerFromInt64# :: Int64# -> Integer
- integerFromWord64# :: Word64# -> Integer
- integerToInt64# :: Integer -> Int64#
- integerToWord64# :: Integer -> Word64#
- integerDecodeDouble# :: Double# -> (# Integer, Int# #)
- integerEncodeDouble# :: Integer -> Int# -> Double#
- integerEncodeDouble :: Integer -> Int -> Double
- integerEncodeFloat# :: Integer -> Int# -> Float#
- integerToAddr# :: Integer -> Addr# -> Bool# -> State# s -> (# State# s, Word# #)
- integerToAddr :: Integer -> Addr# -> Bool# -> IO Word
- integerFromAddr# :: Word# -> Addr# -> Bool# -> State# s -> (# State# s, Integer #)
- integerFromAddr :: Word# -> Addr# -> Bool# -> IO Integer
- integerFromWordList :: Bool -> [Word] -> Integer
- integerToMutableByteArray# :: Integer -> MutableByteArray# s -> Word# -> Bool# -> State# s -> (# State# s, Word# #)
- integerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Bool# -> IO Word
- integerFromByteArray# :: Word# -> ByteArray# -> Word# -> Bool# -> State# s -> (# State# s, Integer #)
- integerFromByteArray :: Word# -> ByteArray# -> Word# -> Bool# -> Integer
- integerIsNegative# :: Integer -> Bool#
- integerIsNegative :: Integer -> Bool
- integerIsZero :: Integer -> Bool
- integerIsOne :: Integer -> Bool
- integerNe :: Integer -> Integer -> Bool
- integerEq :: Integer -> Integer -> Bool
- integerLe :: Integer -> Integer -> Bool
- integerLt :: Integer -> Integer -> Bool
- integerGt :: Integer -> Integer -> Bool
- integerGe :: Integer -> Integer -> Bool
- integerEq# :: Integer -> Integer -> Bool#
- integerNe# :: Integer -> Integer -> Bool#
- integerGt# :: Integer -> Integer -> Bool#
- integerLe# :: Integer -> Integer -> Bool#
- integerLt# :: Integer -> Integer -> Bool#
- integerGe# :: Integer -> Integer -> Bool#
- integerCompare :: Integer -> Integer -> Ordering
- integerSub :: Integer -> Integer -> Integer
- integerAdd :: Integer -> Integer -> Integer
- integerMul :: Integer -> Integer -> Integer
- integerNegate :: Integer -> Integer
- integerAbs :: Integer -> Integer
- integerSignum :: Integer -> Integer
- integerSignum# :: Integer -> Int#
- integerQuotRem# :: Integer -> Integer -> (# Integer, Integer #)
- integerQuotRem :: Integer -> Integer -> (Integer, Integer)
- integerQuot :: Integer -> Integer -> Integer
- integerRem :: Integer -> Integer -> Integer
- integerDivMod# :: Integer -> Integer -> (# Integer, Integer #)
- integerDivMod :: Integer -> Integer -> (Integer, Integer)
- integerDiv :: Integer -> Integer -> Integer
- integerMod :: Integer -> Integer -> Integer
- integerGcd :: Integer -> Integer -> Integer
- integerLcm :: Integer -> Integer -> Integer
- integerSqr :: Integer -> Integer
- integerLog2# :: Integer -> Word#
- integerLog2 :: Integer -> Word
- integerLogBaseWord# :: Word# -> Integer -> Word#
- integerLogBaseWord :: Word -> Integer -> Word
- integerLogBase# :: Integer -> Integer -> Word#
- integerLogBase :: Integer -> Integer -> Word
- integerIsPowerOf2# :: Integer -> (# (# #) | Word# #)
- integerGcde# :: Integer -> Integer -> (# Integer, Integer, Integer #)
- integerGcde :: Integer -> Integer -> (Integer, Integer, Integer)
- integerRecipMod# :: Integer -> Natural -> (# Natural | () #)
- integerPowMod# :: Integer -> Integer -> Natural -> (# Natural | () #)
- integerPopCount# :: Integer -> Int#
- integerBit# :: Word# -> Integer
- integerBit :: Word -> Integer
- integerTestBit# :: Integer -> Word# -> Bool#
- integerTestBit :: Integer -> Word -> Bool
- integerShiftR# :: Integer -> Word# -> Integer
- integerShiftR :: Integer -> Word -> Integer
- integerShiftL# :: Integer -> Word# -> Integer
- integerShiftL :: Integer -> Word -> Integer
- integerOr :: Integer -> Integer -> Integer
- integerXor :: Integer -> Integer -> Integer
- integerAnd :: Integer -> Integer -> Integer
- integerComplement :: Integer -> Integer
- integerSizeInBase# :: Word# -> Integer -> Word#

# Documentation

data Integer Source #

Arbitrary precision integers. In contrast with fixed-size integral types such as `Int`, the `Integer` type represents the entire infinite range of integers.

Integers are stored in a kind of sign-magnitude form, hence do not expect two's complement form when using bit operations.

If the value is small (i.e., fits into an `Int`), the `IS` constructor is used. Otherwise `IP` and `IN` constructors are used to store a `BigNat` representing the positive or the negative value magnitude, respectively.

Invariant: `IP` and `IN` are used iff the value does not fit in `IS`.

Constructors

IS Int# | iff value in `[minBound::`Int`, maxBound::`Int`]` range
IP ByteArray# | iff value in `]maxBound::`Int`, +inf[` range
IN ByteArray# | iff value in `]-inf, minBound::`Int`[` range

#### Instances

Instances details

Eq Integer Source # |
Instance details Defined in GHC.Num.Integer Methods (==) :: Integer -> Integer -> Bool Source # (/=) :: Integer -> Integer -> Bool Source #
Ord Integer Source # |
Instance details Defined in GHC.Num.Integer Methods compare :: Integer -> Integer -> Ordering Source # (<) :: Integer -> Integer -> Bool Source # (<=) :: Integer -> Integer -> Bool Source # (>) :: Integer -> Integer -> Bool Source # (>=) :: Integer -> Integer -> Bool Source # max :: Integer -> Integer -> Integer Source # min :: Integer -> Integer -> Integer Source #

integerCheck :: Integer -> Bool Source #

Check Integer invariants

integerCheck# :: Integer -> Bool# Source #

Check Integer invariants

# Useful constants

integerZero :: Integer Source #

Integer Zero

integerOne :: Integer Source #

Integer One

# Conversion with...

## `Int`

integerFromInt# :: Int# -> Integer Source #

Create an Integer from an Int#

integerFromInt :: Int -> Integer Source #

Create an Integer from an Int

integerToInt# :: Integer -> Int# Source #

Truncates `Integer` to least-significant `Int#`

integerToInt :: Integer -> Int Source #

Truncates `Integer` to least-significant `Int#`

## `BigNat`

integerFromBigNat# :: BigNat# -> Integer Source #

Create a positive Integer from a BigNat

integerFromBigNatNeg# :: BigNat# -> Integer Source #

Create a negative Integer from a BigNat

integerFromBigNatSign# :: Int# -> BigNat# -> Integer Source #

Create an Integer from a sign-bit and a BigNat

integerToBigNatSign# :: Integer -> (# Int#, BigNat# #) Source #

Convert an Integer into a sign-bit and a BigNat

integerToBigNatClamp# :: Integer -> BigNat# Source #

Convert an Integer into a BigNat.

Return 0 for negative Integers.

## `Word`

integerFromWord# :: Word# -> Integer Source #

Convert a Word# into an Integer

integerFromWord :: Word -> Integer Source #

Convert a Word into an Integer

integerFromWordNeg# :: Word# -> Integer Source #

Create a negative Integer with the given Word magnitude

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

Create an Integer from a sign and a Word magnitude

integerToWord# :: Integer -> Word# Source #

Truncate an Integer into a Word

integerToWord :: Integer -> Word Source #

Truncate an Integer into a Word

## `Natural`

integerFromNatural :: Natural -> Integer Source #

Convert a Natural into an Integer

integerToNaturalClamp :: Integer -> Natural Source #

Convert an Integer into a Natural

Return 0 for negative Integers.

integerToNatural :: Integer -> Natural Source #

Convert an Integer into a Natural

Return absolute value

integerToNaturalThrow :: Integer -> Natural Source #

Convert an Integer into a Natural

Throw an Underflow exception if input is negative.

## `Int64`/`Word64`

integerFromInt64# :: Int64# -> Integer Source #

Convert an Int64# into an Integer

integerFromWord64# :: Word64# -> Integer Source #

Convert a Word64# into an Integer

integerToInt64# :: Integer -> Int64# Source #

Convert an Integer into an Int64#

integerToWord64# :: Integer -> Word64# Source #

Convert an Integer into a Word64#

## Floating-point

integerDecodeDouble# :: Double# -> (# Integer, Int# #) Source #

Decode a Double# into (# Integer mantissa, Int# exponent #)

integerEncodeDouble# :: Integer -> Int# -> Double# Source #

Encode (# Integer mantissa, Int# exponent #) into a Double#

integerEncodeDouble :: Integer -> Int -> Double Source #

Encode (Integer mantissa, Int exponent) into a Double

integerEncodeFloat# :: Integer -> Int# -> Float# Source #

Encode (# Integer mantissa, Int# exponent #) into a Float#

TODO: Not sure if it's worth to write `Float` optimized versions here

## `Addr#`

integerToAddr# :: Integer -> Addr# -> Bool# -> State# s -> (# State# s, Word# #) Source #

Write an `Integer` (without sign) to `addr` in base-256 representation and return the number of bytes written.

The endianness is selected with the Bool# parameter: write most significant byte first (big-endian) if `1#` or least significant byte first (little-endian) if `0#`.

integerToAddr :: Integer -> Addr# -> Bool# -> IO Word Source #

Write an `Integer` (without sign) to `addr` in base-256 representation and return the number of bytes written.

The endianness is selected with the Bool# parameter: write most significant byte first (big-endian) if `1#` or least significant byte first (little-endian) if `0#`.

integerFromAddr# :: Word# -> Addr# -> Bool# -> State# s -> (# State# s, Integer #) Source #

Read an `Integer` (without sign) in base-256 representation from an Addr#.

The size is given in bytes.

The endianness is selected with the Bool# parameter: most significant byte first (big-endian) if `1#` or least significant byte first (little-endian) if `0#`.

Null higher limbs are automatically trimed.

integerFromAddr :: Word# -> Addr# -> Bool# -> IO Integer Source #

Read an `Integer` (without sign) in base-256 representation from an Addr#.

The size is given in bytes.

The endianness is selected with the Bool# parameter: most significant byte first (big-endian) if `1#` or least significant byte first (little-endian) if `0#`.

Null higher limbs are automatically trimed.

## Limbs

integerFromWordList :: Bool -> [Word] -> Integer Source #

Convert a list of Word into an Integer

integerToMutableByteArray# :: Integer -> MutableByteArray# s -> Word# -> Bool# -> State# s -> (# State# s, Word# #) Source #

Write an `Integer` (without sign) in base-256 representation and return the number of bytes written.

The endianness is selected with the Bool# parameter: most significant byte first (big-endian) if `1#` or least significant byte first (little-endian) if `0#`.

integerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Bool# -> IO Word Source #

Write an `Integer` (without sign) in base-256 representation and return the number of bytes written.

The endianness is selected with the Bool# parameter: most significant byte first (big-endian) if `1#` or least significant byte first (little-endian) if `0#`.

integerFromByteArray# :: Word# -> ByteArray# -> Word# -> Bool# -> State# s -> (# State# s, Integer #) Source #

Read an `Integer` (without sign) in base-256 representation from a ByteArray#.

The size is given in bytes.

The endianness is selected with the Bool# parameter: most significant byte first (big-endian) if `1#` or least significant byte first (little-endian) if `0#`.

Null higher limbs are automatically trimed.

integerFromByteArray :: Word# -> ByteArray# -> Word# -> Bool# -> Integer Source #

Read an `Integer` (without sign) in base-256 representation from a ByteArray#.

The size is given in bytes.

The endianness is selected with the Bool# parameter: most significant byte first (big-endian) if `1#` or least significant byte first (little-endian) if `0#`.

Null higher limbs are automatically trimed.

# Predicates

integerIsNegative# :: Integer -> Bool# Source #

Negative predicate

integerIsNegative :: Integer -> Bool Source #

Negative predicate

integerIsZero :: Integer -> Bool Source #

Zero predicate

integerIsOne :: Integer -> Bool Source #

One predicate

# Comparison

integerNe :: Integer -> Integer -> Bool Source #

Not-equal predicate.

integerEq :: Integer -> Integer -> Bool Source #

Equal predicate.

integerLe :: Integer -> Integer -> Bool Source #

Lower-or-equal predicate.

integerLt :: Integer -> Integer -> Bool Source #

Lower predicate.

integerGt :: Integer -> Integer -> Bool Source #

Greater predicate.

integerGe :: Integer -> Integer -> Bool Source #

Greater-or-equal predicate.

integerEq# :: Integer -> Integer -> Bool# Source #

Equal predicate.

integerNe# :: Integer -> Integer -> Bool# Source #

Not-equal predicate.

integerGt# :: Integer -> Integer -> Bool# Source #

Greater predicate.

integerLe# :: Integer -> Integer -> Bool# Source #

Lower-or-equal predicate.

integerLt# :: Integer -> Integer -> Bool# Source #

Lower predicate.

integerGe# :: Integer -> Integer -> Bool# Source #

Greater-or-equal predicate.

integerCompare :: Integer -> Integer -> Ordering Source #

Compare two Integer

# Arithmetic

integerSub :: Integer -> Integer -> Integer Source #

Subtract one `Integer` from another.

integerAdd :: Integer -> Integer -> Integer Source #

Add two `Integer`s

integerMul :: Integer -> Integer -> Integer Source #

Multiply two `Integer`s

integerNegate :: Integer -> Integer Source #

Negate `Integer`.

One edge-case issue to take into account is that Int's range is not symmetric around 0. I.e. `minBound+maxBound = -1`

IP is used iff n > maxBound::Int IN is used iff n < minBound::Int

integerAbs :: Integer -> Integer Source #

Compute absolute value of an `Integer`

integerSignum :: Integer -> Integer Source #

Return `-1`, `0`, and `1` depending on whether argument is negative, zero, or positive, respectively

integerSignum# :: Integer -> Int# Source #

Return `-1#`, `0#`, and `1#` depending on whether argument is negative, zero, or positive, respectively

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

Simultaneous `integerQuot` and `integerRem`.

Divisor must be non-zero otherwise the GHC runtime will terminate with a division-by-zero fault.

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

Simultaneous `integerQuot` and `integerRem`.

Divisor must be non-zero otherwise the GHC runtime will terminate with a division-by-zero fault.

integerQuot :: Integer -> Integer -> Integer Source #

integerRem :: Integer -> Integer -> Integer Source #

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

Simultaneous `integerDiv` and `integerMod`.

Divisor must be non-zero otherwise the GHC runtime will terminate with a division-by-zero fault.

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

Simultaneous `integerDiv` and `integerMod`.

Divisor must be non-zero otherwise the GHC runtime will terminate with a division-by-zero fault.

integerDiv :: Integer -> Integer -> Integer Source #

integerMod :: Integer -> Integer -> Integer Source #

integerGcd :: Integer -> Integer -> Integer Source #

Compute greatest common divisor.

integerLcm :: Integer -> Integer -> Integer Source #

Compute least common multiple.

integerSqr :: Integer -> Integer Source #

Square a Integer

integerLog2# :: Integer -> Word# Source #

Base 2 logarithm (floor)

For numbers <= 0, return 0

integerLog2 :: Integer -> Word Source #

Base 2 logarithm (floor)

For numbers <= 0, return 0

integerLogBaseWord# :: Word# -> Integer -> Word# Source #

Logarithm (floor) for an arbitrary base

For numbers <= 0, return 0

integerLogBaseWord :: Word -> Integer -> Word Source #

Logarithm (floor) for an arbitrary base

For numbers <= 0, return 0

integerLogBase# :: Integer -> Integer -> Word# Source #

Logarithm (floor) for an arbitrary base

For numbers <= 0, return 0

integerLogBase :: Integer -> Integer -> Word Source #

Logarithm (floor) for an arbitrary base

For numbers <= 0, return 0

integerIsPowerOf2# :: Integer -> (# (# #) | Word# #) Source #

Indicate if the value is a power of two and which one

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

Get the extended GCD of two integers.

`integerGcde# a b` returns (# g,x,y #) where * ax + by = g = |gcd a b|

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

Get the extended GCD of two integers.

`integerGcde a b` returns (g,x,y) where * ax + by = g = |gcd a b|

integerRecipMod# :: Integer -> Natural -> (# Natural | () #) Source #

Computes the modular inverse.

`integerRecipMod# x m` behaves as follows:

- If m > 1 and gcd x m = 1, it returns an integer y with 0 < y < m such that x*y is congruent to 1 modulo m.
- If m > 1 and gcd x m > 1, it fails.
- If m = 1, it returns `0` for all x. The computation effectively takes place in the zero ring, which has a single element 0 with 0+0 = 0*0 = 0: the element 0 is the multiplicative identity element and is its own multiplicative inverse.
- If m = 0, it fails.

NB. Successful evaluation returns a value of the form `(# n | #)`; failure is indicated by returning `(# | () #)`.

integerPowMod# :: Integer -> Integer -> Natural -> (# Natural | () #) Source #

Computes the modular exponentiation.

`integerPowMod# b e m` behaves as follows:

- If m > 1 and e >= 0, it returns an integer y with 0 <= y < m and y congruent to b^e modulo m.
- If m > 1 and e < 0, it uses `integerRecipMod#` to try to find a modular multiplicative inverse b' (which only exists if gcd b m = 1) and then caculates (b')^(-e) modulo m (note that -e > 0); if the inverse does not exist then it fails.
- If m = 1, it returns `0` for all b and e.
- If m = 0, it fails.

NB. Successful evaluation returns a value of the form `(# n | #)`; failure is indicated by returning `(# | () #)`.

# Bit operations

integerPopCount# :: Integer -> Int# Source #

Count number of set bits. For negative arguments returns the negated population count of the absolute value.

integerBit# :: Word# -> Integer Source #

Positive `Integer` for which only n-th bit is set

integerBit :: Word -> Integer Source #

`Integer` for which only n-th bit is set

integerTestBit# :: Integer -> Word# -> Bool# Source #

Test if n-th bit is set.

Fake 2's complement for negative values (might be slow)

integerTestBit :: Integer -> Word -> Bool Source #

Test if n-th bit is set. For negative Integers it tests the n-th bit of the negated argument.

Fake 2's complement for negative values (might be slow)

integerShiftR# :: Integer -> Word# -> Integer Source #

Shift-right operation

Fake 2's complement for negative values (might be slow)

integerShiftR :: Integer -> Word -> Integer Source #

Shift-right operation

Fake 2's complement for negative values (might be slow)

integerShiftL# :: Integer -> Word# -> Integer Source #

Shift-left operation

integerShiftL :: Integer -> Word -> Integer Source #

Shift-left operation

Remember that bits are stored in sign-magnitude form, hence the behavior of negative Integers is different from negative Int's behavior.

integerOr :: Integer -> Integer -> Integer Source #

Bitwise OR operation

Fake 2's complement for negative values (might be slow)

integerXor :: Integer -> Integer -> Integer Source #

Bitwise XOR operation

Fake 2's complement for negative values (might be slow)

integerAnd :: Integer -> Integer -> Integer Source #

Bitwise AND operation

Fake 2's complement for negative values (might be slow)

integerComplement :: Integer -> Integer Source #

Binary complement of the

# Miscellaneous

integerSizeInBase# :: Word# -> Integer -> Word# Source #

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

`base` must be > 1