BigInt

Zero.

This is the value the whole representation is normalized around: a magnitude that cancels becomes the empty limb array, and an empty limb array is never negative. So there is exactly one zero, and x |> subBy x == BigInt.zero is a reliable test.

It is also the divisor that makes every division in this module return Nothing.

One.

Mostly the step: x |> add one and x |> subBy one. It is also the empty product, so powBy 0 returns it for any base.

An ordinary Int. Above 2^53 an Int is already inexact, so this converts the double you passed, not the number you meant.

Back to an Int, when it fits in one exactly, which means no larger than Math.maxSafeInteger. Anything bigger is Nothing, not a number that is almost right.

Truncate a Float toward zero. NaN and the infinities are Nothing. Everything else has an exact integer part, however large, because past a certain exponent a double is an integer.

Toward zero rather than floored, the same split as quotRemBy against divModBy:

BigInt.fromFloat -3.7 --> Just (BigInt.fromInt -3)

The result is exact, not approximate. Example:

BigInt.fromFloat 1.0e30 |> Maybe.map BigInt.toString
--> Just "1000000000000000019884624838656"

Those trailing digits are not noise. That is the integer the double has held all along, and this is the function that shows you which one you actually have. toFloat is the direction that loses it again.

To a Float, rounding once the value no longer fits.

This is the lossy half of the round trip, and above 2^53 it is lossy quietly:

BigInt.toFloat (BigInt.add big BigInt.one) == BigInt.toFloat big
-- True for big = 2^64, and nothing says the one went missing

fromFloat loses nothing going the other way, so a value survives a round trip through a String but not through a Float. If you need to store one, store the string.

Read a number written the way it would be in source: an optional sign, then 0x, 0b or 0o and its digits, or plain decimal.

An underscore between two digits is ignored, so 0xdead_beef and 1_000_000 both parse, and so does 1__000. An underscore anywhere else is not a separator, so _1, 1_ and 0x_ff are Nothing.

BigInt.fromString "0b1010" --> Just (BigInt.fromInt 10)

BigInt.fromString "-0xff" --> Just (BigInt.fromInt -255)

BigInt.fromString "12 apples" --> Nothing

Decimal, with a leading - when negative.

Read a number in a base from 2 to 36, with an optional sign and no prefix. Underscores between digits are ignored here too.

In a base from 2 to 36, with digits 0-9 then a-z, and a leading - when negative. No prefix: toStringWithBase 16 gives "ff", not "0xff".

A negative number is written with a sign rather than as two's complement, so toStringWithBase 16 (fromInt -255) is "-ff". If you want the bit pattern a machine would show for a 64-bit value, apply maskTo first; that is what it is for.

Anything outside 2 to 36 gives "".

fromString with a ceiling on how many digits the number may have, for text that comes from somewhere you do not control: fromStringWithin limit text.

The plain fromString does what it is told. A string of a million digits is a million-digit number, and parsing it costs time that grows with the square of its length. When the text is untrusted, say how big a number you are prepared to accept, and anything longer is refused before any arithmetic starts:

BigInt.fromStringWithin 20 "18446744073709551615"
    |> Result.map BigInt.toString
--> Ok "18446744073709551615"

BigInt.fromStringWithin 20 "123456789012345678901"
--> Err (BigInt.TooLong { digits = 21, limit = 20 })

BigInt.fromStringWithin 20 "twelve"
--> Err BigInt.NotANumber

The digits are counted in the base the text is written in, after the sign, the prefix, any separators and any leading zeroes, so 0x0000ff is two digits. Zero is one digit. A limit below one refuses everything. Malformed text is NotANumber whatever its length.

fromStringWithBase with the same ceiling as fromStringWithin: fromStringWithBaseWithin base limit text. The digits are counted in base, so the same limit admits a longer number in hexadecimal than in binary.

BigInt.fromStringWithBaseWithin 16 4 "dead"
    |> Result.map BigInt.toString
--> Ok "57005"

BigInt.fromStringWithBaseWithin 2 4 "11111"
--> Err (BigInt.TooLong { digits = 5, limit = 4 })

A base outside 2 to 36 is NotANumber, as it is Nothing for the plain function.

Add. There is no overflow to think about.

No By suffix, unlike subBy, because addition is commutative, so there is no subject for a pipeline to put last.

Sign and magnitude means this is only sometimes an addition: when the signs differ it is the smaller magnitude subtracted from the larger, and the answer takes the sign of whichever was larger.

Subtract the first from the second: subBy b a is a - b.

a |> BigInt.subBy one

Multiply, exactly, however big the answer gets. Commutative, so no By.

The sign is whether the two signs differed. The magnitudes go through long multiplication, a row at a time, so the cost is the product of the two lengths.

Flip the sign. The limbs are handed through untouched: no arithmetic happens here at any size, only the sign changes.

negate zero is zero: it goes through make, which never produces a negative zero, so there is only ever one.

Drop the sign. Again the limbs pass through untouched.

This one cannot fail. abs of the most negative value is the classic fixed-width bug: there is no positive Int.minValue to return, so it comes back negative. A BigInt has no most negative value, so the bug has nowhere to happen.

Raise to a power: powBy exponent base.

A negative exponent is not an error. It gives the truncated integer answer, the same as every other division in this module: two to the minus three is an eighth, truncated to zero; one to any negative power is one; and zero to a negative power, the only genuinely undefined case, is zero.

BigInt.fromInt 2 |> BigInt.powBy 10 --> BigInt.fromInt 1024

Divide, truncating toward zero, so the remainder takes the sign of the dividend: quotRemBy divisor dividend. This is C's / and %, and Gren's own // and Math.remainderBy.

-7 / 2 is -3 remainder -1 here.

Nothing when the divisor is zero, which is the only way it can fail.

The quotient alone, truncating toward zero: quotBy divisor dividend. This is Gren's //, except that it is still correct above 2^31.

BigInt.fromInt -7 |> BigInt.quotBy (BigInt.fromInt 2)
--> Just (BigInt.fromInt -3)

Nothing when the divisor is zero.

The remainder alone, taking the sign of the dividend: remainderBy divisor dividend. This is Math.remainderBy.

BigInt.fromInt -7 |> BigInt.remainderBy (BigInt.fromInt 2)
--> Just (BigInt.fromInt -1)

Nothing when the divisor is zero.

Divide, flooring, so the modulus takes the sign of the divisor: divModBy divisor dividend. This is Python's // and %, and Gren's own Math.modBy.

-7 / 2 is -4 modulus 1 here.

The two differ only when exactly one operand is negative. Which one you want depends on whether you are checking C or Python, so both are here.

The floored quotient alone: divBy divisor dividend. Python's //.

BigInt.fromInt -7 |> BigInt.divBy (BigInt.fromInt 2)
--> Just (BigInt.fromInt -4)

Nothing when the divisor is zero.

The modulus alone, taking the sign of the divisor: modBy divisor dividend. This is Math.modBy, and it is the one to reach for when the question is divisibility, because its answer is zero or has the divisor's sign and never the dividend's.

BigInt.fromInt -7 |> BigInt.modBy (BigInt.fromInt 2)
--> Just (BigInt.fromInt 1)

Nothing when the divisor is zero.

How the first compares to the second, the way Basics.compare does.

Whether this is zero, which is Array.isEmpty on the limbs and so costs nothing at any size.

x == BigInt.zero gives the same answer, because normalization guarantees a single representation. This one just reads better.

Zero is not negative.

Whether this is a multiple of two. Zero is.

This reads only the bottom bit of the bottom limb, since the limbs are little-endian; nothing else in the number is touched. Asking through a division instead (modBy (fromInt 2)) walks every limb and builds a quotient nobody wanted.

The sign does not come into it, because the representation is sign and magnitude and -7 is odd for the same reason 7 is.

Whether this is not a multiple of two.

BigInt.isOdd (BigInt.fromInt -7) --> True

The larger of the two, standing in for Basics.max.

The smaller of the two, standing in for Basics.min.

Bitwise AND.

Bitwise OR.

Bitwise XOR.

Flip every bit, which for a number with no width is exactly -x - 1.

BigInt.complement (BigInt.fromInt 5) --> BigInt.fromInt -6

Shift left, which is multiplication by a power of two and never loses anything. A negative count shifts the other way.

Shift right arithmetically: the sign is kept and the result is floored, so -1 shifted right stays -1 rather than becoming 0. That is what a machine's arithmetic shift does and what two's complement means. The truncating version is quotRemBy with a power of two.

How many bits the magnitude needs; zero for zero. The sign is not counted, because a BigInt has no width for a sign bit to live in.

BigInt.fromInt 255 |> BigInt.bitLength --> 8

How many bits of the magnitude are set. Counting a negative number's bits would mean counting an infinite run of ones, so this counts the magnitude's and says so; maskTo first if that is not what you meant.

The low width bits, as a number that is never negative, which is what reading a value as an unsigned integer of that width means.

BigInt.fromInt -1 |> BigInt.maskTo 64 |> BigInt.toString
    --> "18446744073709551615"

The low width bits read as two's complement, which is what reading a value as a signed integer of that width means.

BigInt.fromString "0xFFFFFFFFFFFFFFFF"
    |> Maybe.map (BigInt.toSigned 64)
    --> Just (BigInt.fromInt -1)

Would this survive being stored in a signed integer of this width? That is, is it within -2^(width-1) to 2^(width-1) - 1?

Would this survive being stored in an unsigned integer of this width?