summaryrefslogtreecommitdiff
path: root/doc/api/libstd/bigint.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/api/libstd/bigint.txt')
-rw-r--r--doc/api/libstd/bigint.txt208
1 files changed, 208 insertions, 0 deletions
diff --git a/doc/api/libstd/bigint.txt b/doc/api/libstd/bigint.txt
new file mode 100644
index 0000000..dfcc180
--- /dev/null
+++ b/doc/api/libstd/bigint.txt
@@ -0,0 +1,208 @@
+{
+ title: Bigints
+ description: libstd: Bigints
+}
+
+Bigints
+-------
+
+ pkg std =
+ type bigint = struct
+ ;;
+
+ generic mkbigint : (v : @a::(numeric,integral) -> bigint#)
+ 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))
+ 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::(numeric,integral) -> bool)
+ generic bigaddi : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigsubi : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigmuli : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigdivi : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigshli : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigshri : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ 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::(numeric,integral) -> bigint#)
+
+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))
+
+
+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::(numeric,integral) -> bool)
+ generic bigaddi : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigsubi : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigmuli : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigdivi : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigshli : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ generic bigshri : (a : bigint#, b : @a::(integral,numeric) -> bigint#)
+ 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
+--------
+
+```{runmyr bigcmp}
+
+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: "{} is equal to {}\n", a, b)
+ | `std.Before: "{} is less than {}\n", a, b)
+ | `std.After: "{} 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)
+}
+```