Rebase.GHC.Num

Basic numeric class.

The Haskell Report defines no laws for Num. However, (+) and (*) are customarily expected to define a ring and have the following properties:

Associativity of (+)

(x + y) + z

=

x + (y + z)

Commutativity of (+)

x + y

=

y + x

fromInteger 0 is the additive identity

x + fromInteger 0

=

x

negate gives the additive inverse

x + negate x

=

fromInteger 0

Associativity of (*)

(x * y) * z

=

x * (y * z)

fromInteger 1 is the multiplicative identity

x * fromInteger 1

=

x

and

fromInteger 1 * x

=

x

Distributivity of (*) with respect to (+)

a * (b + c)

=

(a * b) + (a * c)

and

(b + c) * a

=

(b * a) + (c * a)

Coherence with toInteger

if the type also implements

GHC.Real.Integral

, then

fromInteger

is a left inverse for

toInteger

, i.e.

fromInteger (toInteger i) == i

Note that it isn't customarily expected that a type instance of both Num and Ord implement an ordered ring. Indeed, in base only Integer and Rational do.

Natural number

Invariant: numbers <= 0xffffffffffffffff use the NS constructor

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.

Shift-right operation

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

Shift-left operation

Test if n-th bit is set.

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

Positive Integer for which only n-th bit is set

Binary complement of the

Bitwise XOR operation

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

Bitwise OR operation

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

Bitwise AND operation

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

Compute least common multiple.

Compute greatest common divisor.

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

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

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

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.

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

Compute absolute value of an Integer

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

Subtract one Integer from another.

Multiply two Integers

Add two Integers

Convert an Int64# into an Integer

Convert a Word64# into an Integer

Convert a Word# into an Integer

Convert an Integer into an Int64#

Convert an Integer into a Word64#

Truncates Integer to least-significant Int#

Truncate an Integer into a Word

Convert an Integer into a Natural

Return absolute value

Convert an Integer into a Natural

Throw an Underflow exception if input is negative.

Convert an Integer into a Natural

Return 0 for negative Integers.

Convert a Natural into an Integer

Equal predicate.

Truncates Integer to least-significant Int#

Compute the number of digits of the Natural in the given base.

base must be > 1

"naturalPowMod b e m" computes base b raised to exponent e modulo m.

Logarithm for an arbitrary base

Logarithm for an arbitrary base

Base 2 logarithm

Compute least common multiple.

Compute greatest common divisor.

Return division remainder

Return division quotient

Return division quotient and remainder

Division by zero is handled by BigNat

Multiplication

Sub two naturals

Unsafe: don't check that x >= y Undefined results if it happens

Sub two naturals

Throw an Underflow exception if x < y

Sub two naturals

Add two naturals

Left shift

Right shift for Natural

PopCount for Natural

Convert the lower bits of a Natural into a Word#

Lower-or-equal predicate.

Lower predicate.

Greater-or-equal predicate.

Greater predicate.

Not-equal predicate.

Compare two Integer

Integer Zero

Zero Natural

Create a Natural from a BigNat# (respect the invariants)

Integer for which only n-th bit is set

Check Integer invariants

Check Integer invariants

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

Simultaneous integerDiv and integerMod.

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

Encode (Integer mantissa, Int exponent) into a Double

Equal predicate.

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.

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.

Create a positive Integer from a BigNat

Create a negative Integer from a BigNat

Create an Integer from a sign-bit and a BigNat

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.

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.

Create an Integer from an Int

Create an Integer from an Int#

Convert a Word into an Integer

Convert a list of Word into an Integer

Create a negative Integer with the given Word magnitude

Create an Integer from a sign and a Word magnitude

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|

Greater-or-equal predicate.

Greater predicate.

Negative predicate

Negative predicate

One predicate

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

Zero predicate

Lower-or-equal predicate.

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

Lower predicate.

Not-equal predicate.

Integer One

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

Simultaneous integerQuot and integerRem.

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

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

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.

Shift-right operation

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

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

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

base must be > 1

Square a Integer

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)

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

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

Convert an Integer into a BigNat.

Return 0 for negative Integers.

Convert an Integer into a sign-bit and a BigNat

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

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

Truncate an Integer into a Word

Check Natural invariants

Check Natural invariants

Compare two Natural

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

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

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

Equality test for Natural

Equality test for Natural

Read a Natural 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.

Read a Natural 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.

Read a Natural 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.

Create a Natural from a Word

Create a Natural from a Word#

Convert two Word# (most-significant first) into a Natural

Create a Natural from a list of Word

Greater or equal test for Natural

Greater or equal test for Natural

Greater test for Natural

Greater test for Natural

Test One Natural

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

Test Zero Natural

Lower or equal test for Natural

Lower or equal test for Natural

Base 2 logarithm

Logarithm for an arbitrary base

Logarithm for an arbitrary base

Lower test for Natural

Lower test for Natural

Inequality test for Natural

Inequality test for Natural

Negate for Natural

One Natural

PopCount for Natural

Return division quotient and remainder

Left shift

Right shift for Natural

Signum for Natural

Square a Natural

Write a Natural 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#.

Write a Natural 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#.

Convert a Natural into a BigNat#

Write a Natural 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#.

Convert the lower bits of a Natural into a Word

Convert a Natural into a Word# clamping to (maxBound :: Word).

Convert a Natural into a Word# clamping to (maxBound :: Word#).

Try downcasting Natural to Word value. Returns (##) if value doesn't fit in Word.

the same as flip (-).

Because - is treated specially in the Haskell grammar, (- e) is not a section, but an application of prefix negation. However, (subtract exp) is equivalent to the disallowed section.