ref: d0ffb958c7247028223c7e53253249d52a47a324
dir: /doc/api/libstd/bigint.txt/
{
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)
}
```