summaryrefslogtreecommitdiff
path: root/doc/api/libstd/bigint.txt
blob: dfcc1800372facba8a1f31bbc65c5a1897a357d6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
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)
}
```