Myrddin: Bigints

Summary: Bigints

pkg std = type bigint = struct ;;

        generic mkbigint    : (v : @a -> bigint#) :: numeric,integral @a
        const bigfree   : (a : bigint# -> void)
        const bigdup    : (a : bigint# -> bigint#)
        const bigassign : (d : bigint#, s : bigint# -> bigint#)
        const bigmove   : (d : bigint#, s : bigint# -> bigint#)
        const bigparse  : (s : byte[:] -> option(bigint#))
        const bigclear  : (a : bigint# -> bigint#)
        const bigbfmt   : (b : byte[:], a : bigint#, base : int -> size)
        const bigtoint  : (a : bigint#  -> @a) :: numeric,integral @a
        const bigiszero : (a : bigint# -> bool)
        const bigeq : (a : bigint#, b : bigint# -> bool)
        const bigcmp    : (a : bigint#, b : bigint# -> order)
        const bigadd    : (a : bigint#, b : bigint# -> bigint#)
        const bigsub    : (a : bigint#, b : bigint# -> bigint#)
        const bigmul    : (a : bigint#, b : bigint# -> bigint#)
        const bigdiv    : (a : bigint#, b : bigint# -> bigint#)
        const bigmod    : (a : bigint#, b : bigint# -> bigint#)
        const bigdivmod : (a : bigint#, b : bigint# -> (bigint#, bigint#))
        const bigshl    : (a : bigint#, b : bigint# -> bigint#)
        const bigshr    : (a : bigint#, b : bigint# -> bigint#)
        const bigmodpow : (b : bigint#, e : bigint#, m : bigint# -> bigint#)
        const bigpow    : (a : bigint#, b : bigint# -> bigint#)
        generic bigeqi  : (a : bigint#, b : @a -> bool)     :: numeric,integral @a
        generic bigaddi : (a : bigint#, b : @a -> bigint#)      :: integral,numeric @a
        generic bigsubi : (a : bigint#, b : @a -> bigint#)      :: integral,numeric @a
        generic bigmuli : (a : bigint#, b : @a -> bigint#)      :: integral,numeric @a
        generic bigdivi : (a : bigint#, b : @a -> bigint#)      :: integral,numeric @a
        generic bigshli : (a : bigint#, b : @a -> bigint#)      :: integral,numeric @a
        generic bigshri : (a : bigint#, b : @a -> bigint#)      :: integral,numeric @a
        const bigpowi   : (a : bigint#, b : uint64 -> bigint#)
;;

Overview

While bigint usage in most programs is relatively rare, libstd needs them internally for handling floats, and several other widely used pieces of functionality also need them.

This set of code covers the bulk of common big integer operations: Creation, input, output, and various arithmetic operations

By convention, with a few exceptions, all operations on bigintegers will modify the bigint in place, and return a pointer to the first argument of the function. This allows for easy chaining of operations.

A formatter for bigintegers is installed by default, so std.put("{}\n", mybig) will show a reasonably formatted big integer. The standard x modifier is recognized to print the value in hex.

Types

type bigint = struct
;;

This is a big integer. It stores big integers. Like it was an integer. But bigger.

Functions: Bookkeeping and IO

generic mkbigint    : (v : @a -> bigint#) :: numeric, integral @a

Mkbigint takes a regular small int, and creates a biginteger from that value. It allocates the value on the heap, returning a pointer to the bigint instance. This instance must be freed with bigfree.

const bigfree   : (a : bigint# -> void)

Cleans up the storage associated with the bigint a.

const bigdup    : (a : bigint# -> bigint#)

Bigdup creates a new biginteger, and copies the value from the original biginteger a into it. It returns a new biginteger.

const bigassign : (d : bigint#, s : bigint# -> bigint#)

Bigassign copies the value of the bigint s to d, and returns a pointer to d. No allocations or new values are created.

const bigmove   : (d : bigint#, s : bigint# -> bigint#)

Bigmove clears the value of d, and moves the value from s into it efficiently, tearing down the value of s in the process. It returns a pointer to d.

For example, if you had the a=123 and b=246, then moving a <= b, the final values would be a = 246 and b = 0.

No new values are allocated.

const bigparse  : (s : byte[:] -> option(bigint#))

Bigparse converts a string representation of an integer into a bigint, returning `Some val if the string is a valid bigint, or `None otherwise.

Decimal, hex, octal, and binary biginteger strings are recognized. Decimal is the default, and is recognized unprefixed. Hex must be prefixed with 0x, octal must be prefixed with 0o, and binary must be prefixed with 0b. As with all Myrddin integers, '_' is accepted and ignored within numerical constants.

const bigclear  : (a : bigint# -> bigint#)

Bigclear zeroes out a biginteger, returning it.

const bigtoint  : (a : bigint#  -> @a) :: numeric,integral @a

Bigtoint returns the low order digits of a bigint as an integer value. Care must be taken when using this function to ensure that values are not undesirably truncated.

Functions: Arithmetic

const bigiszero : (a : bigint# -> bool)

Bigiszero checks if a bigint is zero, and returns true if it is, or false if it is not.

const bigeq : (a : bigint#, b : bigint# -> bool)

Bigeq compares whether two integers are equal.

const bigcmp    : (a : bigint#, b : bigint# -> order)

Bigcmp compares two big integers, and returns the ordering between them. `Before if a < b, `After if a > b, and `Equal if the two values are equal.

const bigadd    : (a : bigint#, b : bigint# -> bigint#)
const bigsub    : (a : bigint#, b : bigint# -> bigint#)
const bigmul    : (a : bigint#, b : bigint# -> bigint#)
const bigdiv    : (a : bigint#, b : bigint# -> bigint#)
const bigmod    : (a : bigint#, b : bigint# -> bigint#)
const bigshl    : (a : bigint#, b : bigint# -> bigint#)
const bigshr    : (a : bigint#, b : bigint# -> bigint#)
const bigmodpow : (b : bigint#, e : bigint#, m : bigint# -> bigint#)
const bigpow    : (a : bigint#, b : bigint# -> bigint#)

All of these functions follow the convention mentioned in the summary: They apply the operation a = a OP b, where a is the first argument, and b is the second argument. They return a, without allocating a new result.

const bigdivmod : (a : bigint#, b : bigint# -> (bigint#, bigint#))

Bigdivmod is an exception to the above convention. Because it needs to return two values, it returns a tuple of newly allocated bigints.

generic bigeqi  : (a : bigint#, b : @a -> bool) :: numeric,integral @a
generic bigaddi : (a : bigint#, b : @a -> bigint#) :: integral,numeric @a
generic bigsubi : (a : bigint#, b : @a -> bigint#) :: integral,numeric @a
generic bigmuli : (a : bigint#, b : @a -> bigint#) :: integral,numeric @a
generic bigdivi : (a : bigint#, b : @a -> bigint#) :: integral,numeric @a
generic bigshli : (a : bigint#, b : @a -> bigint#) :: integral,numeric @a
generic bigshri : (a : bigint#, b : @a -> bigint#) :: integral,numeric @a
const bigpowi   : (a : bigint#, b : uint64 -> bigint#)

All of these are identical ot the bigint operations above, however instead of taking a bigint for their second operand, they take an integer. This is useful for when operations like multiplication or division by a small constant is needed.

Examples

use std
use bio

const main = {args : byte[:][:]
        var f

        a = try(std.bigparse("1234_5678_1234_6789_6666_7777_8888"))
        b = try(std.bigparse("0x75f3_fffc_1123_5ce4"))

        match std.bigcmp(a, b)
        | `std.Equal:   std.put("{} is equal to {}\n", a, b)
        | `std.Before:  std.put("{} is less than {}\n", a, b)
        | `std.After:   std.put("{} is greater than {}\n", a, b)
        ;;

        std.bigmul(a, b)
        std.bigdivi(a, 42)
        std.put("a * b / 42 = {}\n", a)

        std.bigfree(a, b)
}

Run!

Press 'Run' to see output!