GHC.Internal.Bignum.Integer

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.

Check Integer invariants

Check Integer invariants

Integer Zero

Integer One

Negative predicate

Negative predicate

Zero predicate

One predicate

Not-equal predicate.

Equal predicate.

Lower-or-equal predicate.

Lower predicate.

Greater predicate.

Greater-or-equal predicate.

Equal predicate.

Not-equal predicate.

Greater predicate.

Lower-or-equal predicate.

Lower predicate.

Greater-or-equal predicate.

Compare two Integer

Subtract one Integer from another.

Add two Integers

Multiply two Integers

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

Compute absolute value of an Integer

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

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

Simultaneous integerQuot and integerRem.

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

Simultaneous integerQuot and integerRem.

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

Simultaneous integerDiv and integerMod.

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

Simultaneous integerDiv and integerMod.

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

Compute greatest common divisor.

Compute least common multiple.

Square a Integer

Base 2 logarithm (floor)

For numbers <= 0, return 0

Base 2 logarithm (floor)

For numbers <= 0, return 0

Logarithm (floor) for an arbitrary base

For numbers <= 0, return 0

Logarithm (floor) for an arbitrary base

For numbers <= 0, return 0

Logarithm (floor) for an arbitrary base

For numbers <= 0, return 0

Logarithm (floor) for an arbitrary base

For numbers <= 0, return 0

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

Get the extended GCD of two integers.

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

Get the extended GCD of two integers.

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

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 (# | () #).

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 (# | () #).

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

Positive Integer for which only n-th bit is set

Integer for which only n-th bit is set

Test if n-th bit is set.

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

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)

Shift-right operation

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

Shift-right operation

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

Shift-left operation

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.

Bitwise OR operation

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

Bitwise XOR operation

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

Bitwise AND operation

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

Binary complement of the

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

base must be > 1