~/bend-docscommunity

bigint.bend checks

raw source on the hub · import 0xbf5d8bf07d7411858acb5142889fc4d7/bigint.bend as Bigint

Arbitrary-precision signed integers: add, sub, mul, divmod, pow, modpow, gcd and decimal text.

1 import
import Base

Types

type BigInt source · line 7 · raw

Data

A magnitude is a list of base-10^4 limbs in U32, least significant first, with no zero limb on top. Base 10^4 keeps every limb product and its carries below 2^32, and makes decimal show and read linear. Zero is never negative.

Definitions

def Mag.if source · line 11 · raw

@-A:Type -> @c:Bool -> @t:(@_:Unit -> A) -> @e:(@_:Unit -> A) -> A

A match cannot scrutinize a computed Bool, so each branch is a closure.

def Mag.lone source · line 18 · raw

@z:Bool -> @x:U32 -> List<&2, U32>

def Mag.cons source · line 26 · raw

@+x:U32 -> @r:List<&2, U32> -> List<&2, U32>

x + r * 10^4, dropping a zero limb on top.

def Mag.norm source · line 33 · raw

@xs:List<&2, U32> -> List<&2, U32>

def Mag.len source · line 40 · raw

@xs:List<&2, U32> -> Nat

def Mag.at source · line 43 · raw

@xs:List<&2, U32> -> @i:Nat -> U32

def Mag.top source · line 46 · raw

@xs:List<&2, U32> -> U32

def Mag.odd source · line 49 · raw

@xs:List<&2, U32> -> Bool

def Mag.inc source · line 57 · raw

@a:List<&2, U32> -> @z:Bool -> @+c:U32 -> List<&2, U32>

The limbs are 0 or 1 in z: z says the carry c is 0, so a stays as is.

def Mag.add source · line 68 · raw

@a:List<&2, U32> -> @b:List<&2, U32> -> @+c:U32 -> List<&2, U32>

def Mag.dec source · line 79 · raw

@a:List<&2, U32> -> @z:Bool -> @+w:U32 -> List<&2, U32>

a - w for the borrow w; z says w is 0. Leaves zero limbs on top.

def Mag.sub source · line 91 · raw

@a:List<&2, U32> -> @b:List<&2, U32> -> @+w:U32 -> List<&2, U32>

a - b - w for a >= b + w. Leaves zero limbs on top: callers norm.

def Mag.then source · line 101 · raw

@hi:Cmp -> @lo:Cmp -> Cmp

def Mag.cmp source · line 111 · raw

@a:List<&2, U32> -> @b:List<&2, U32> -> Cmp

Both canonical, so the longer one is larger.

def Mag.mul1 source · line 123 · raw

@a:List<&2, U32> -> @+m:U32 -> @+c:U32 -> List<&2, U32>

a * m + c for m, c below 10^4.

def Mag.scale source · line 131 · raw

@+a:List<&2, U32> -> @+m:U32 -> List<&2, U32>

def Mag.school.put source · line 134 · raw

@p:List<&2, U32> -> @r:List<&2, U32> -> List<&2, U32>

def Mag.school source · line 141 · raw

@a:List<&2, U32> -> @+b:List<&2, U32> -> List<&2, U32>

def Mag.zeros source · line 148 · raw

@n:Nat -> @xs:List<&2, U32> -> List<&2, U32>

def Mag.shift source · line 156 · raw

@xs:List<&2, U32> -> @n:Nat -> List<&2, U32>

xs * 10^(4 n).

def Mag.lo source · line 163 · raw

@xs:List<&2, U32> -> @k:Nat -> List<&2, U32>

def Mag.kara source · line 167 · raw

@+k:Nat -> @+z0:List<&2, U32> -> @+z2:List<&2, U32> -> @s:List<&2, U32> -> List<&2, U32>

z0 + (s - z0 - z2) B^k + z2 B^2k, with B = 10^(4 k).

def Mag.kmul source · line 174 · raw

@+f:Nat -> @+a:List<&2, U32> -> @+b:List<&2, U32> -> List<&2, U32>

Karatsuba while both sides have at least 32 limbs, schoolbook below. f caps the depth; 32 halvings outrun any list that fits in memory.

def Mag.mul source · line 189 · raw

@a:List<&2, U32> -> @b:List<&2, U32> -> List<&2, U32>

def Mag.dsmall source · line 194 · raw

@xs:List<&2, U32> -> @+d:U32 -> @+rem:U32 -> @acc:List<&2, U32> -> List<&2, U32>

Short division of a big-endian list by d below 10^4 with remainder rem: the quotient comes out little-endian, with zero limbs on top.

def Mag.half source · line 203 · raw

@+xs:List<&2, U32> -> List<&2, U32>

def Mag.fix source · line 208 · raw

@+f:Nat -> @+d:U32 -> @+p:List<&2, U32> -> @+r:List<&2, U32> -> @+bn:List<&2, U32> -> @+q:List<&2, U32> -> Pair(List<&2, U32>, List<&2, U32>)

Knuth's Algorithm D step D6: the estimate d is at most 2 over the true quotient digit, so f = 3 steps of p - bn always settle it.

def Mag.step source · line 220 · raw

@x:U32 -> @+bn:List<&2, U32> -> @+n:Nat -> @+n1:Nat -> @+vt:U32 -> @qr:Pair(List<&2, U32>, List<&2, U32>) -> Pair(List<&2, U32>, List<&2, U32>)

One quotient digit: bring limb x down into r, estimate from r's top two limbs over bn's top limb vt, and correct.

def Mag.long source · line 229 · raw

@xs:List<&2, U32> -> @+bn:List<&2, U32> -> @+n:Nat -> @+n1:Nat -> @+vt:U32 -> @qr:Pair(List<&2, U32>, List<&2, U32>) -> Pair(List<&2, U32>, List<&2, U32>)

Long division over the dividend's limbs, most significant first. Quotient digits are consed, so the quotient comes out little-endian.

def Mag.divmod.fin source · line 238 · raw

@+f:U32 -> @qr:Pair(List<&2, U32>, List<&2, U32>) -> Pair(List<&2, U32>, List<&2, U32>)

def Mag.divmod source · line 245 · raw

@a:List<&2, U32> -> @+b:List<&2, U32> -> Pair(List<&2, U32>, List<&2, U32>)

a / b and a % b for b above 0. Both scale by f so that b's top limb is at least 10^4 / 2 (Knuth D1), and the remainder scales back.

def Mag.snd source · line 254 · raw

@qr:Pair(List<&2, U32>, List<&2, U32>) -> List<&2, U32>

def Mag.rem source · line 258 · raw

@a:List<&2, U32> -> @b:List<&2, U32> -> List<&2, U32>

def Mag.pow source · line 262 · raw

@+f:Nat -> @+b:List<&2, U32> -> @+e:Nat -> @+acc:List<&2, U32> -> List<&2, U32>

b^e * acc by squaring; e <= f, and e halves as f counts down.

def Mag.modpow source · line 276 · raw

@+f:Nat -> @+b:List<&2, U32> -> @+e:List<&2, U32> -> @+acc:List<&2, U32> -> @+m:List<&2, U32> -> List<&2, U32>

b^e * acc mod m, with b and acc below m. f counts e's bits: 14 per limb, since 10^4 < 2^14.

def Mag.gcd source · line 290 · raw

@+f:Nat -> @+a:List<&2, U32> -> @+b:List<&2, U32> -> List<&2, U32>

Euclid. Lame: under 5 steps per decimal digit of the smaller, so f from 20 per limb of both never runs out.

def Mag.dig source · line 298 · raw

@d:U32 -> Char

def Mag.d4 source · line 301 · raw

@+x:U32 -> @acc:String -> String

def Mag.show source · line 306 · raw

@xs:List<&2, U32> -> @acc:String -> String

The top limb unpadded, every lower limb as four digits.

def Mag.digits source · line 316 · raw

@s:String -> @ok:Bool -> @acc:List<&2, U32> -> Pair(Bool, List<&2, U32>)

The digit values of s, last first, and whether every char was a digit.

def Mag.group source · line 326 · raw

@ds:List<&2, U32> -> List<&2, U32>

Digits, least significant first, four to a limb.

def BigInt.mk source · line 339 · raw

@neg:Bool -> @m:List<&2, U32> -> BigInt

def BigInt.zero source · line 346 · raw

BigInt

def BigInt.one source · line 349 · raw

BigInt

def BigInt.from_u32 source · line 352 · raw

@+x:U32 -> BigInt

def BigInt.neg source · line 356 · raw

@x:BigInt -> BigInt

def BigInt.abs source · line 361 · raw

@x:BigInt -> BigInt

def BigInt.is_zero source · line 366 · raw

@x:BigInt -> Bool

def BigInt.cmp source · line 371 · raw

@a:BigInt -> @b:BigInt -> Cmp

def BigInt.add.mixed source · line 383 · raw

@c:Cmp -> @+sa:Bool -> @x:List<&2, U32> -> @y:List<&2, U32> -> BigInt

Signs differ: the larger magnitude keeps its sign.

def BigInt.add.go source · line 393 · raw

@diff:Bool -> @sa:Bool -> @+x:List<&2, U32> -> @+y:List<&2, U32> -> BigInt

def BigInt.add source · line 401 · raw

@a:BigInt -> @b:BigInt -> BigInt

def BigInt.sub source · line 406 · raw

@a:BigInt -> @b:BigInt -> BigInt

def BigInt.mul source · line 409 · raw

@a:BigInt -> @b:BigInt -> BigInt

def BigInt.divmod.fin source · line 414 · raw

@+sa:Bool -> @sb:Bool -> @qr:Pair(List<&2, U32>, List<&2, U32>) -> Pair(BigInt, BigInt)

def BigInt.divmod source · line 420 · raw

@a:BigInt -> @b:BigInt -> Maybe<&1, Pair(BigInt, BigInt)>

Truncates toward zero: the remainder takes the dividend's sign.

def BigInt.pow source · line 427 · raw

@b:BigInt -> @+e:Nat -> BigInt

def Mag.base source · line 434 · raw

@neg:Bool -> @+r:List<&2, U32> -> @+m:List<&2, U32> -> List<&2, U32>

The base's residue in [0, m).

def BigInt.modpow.go source · line 443 · raw

@neg_e:Bool -> @sb:Bool -> @x:List<&2, U32> -> @+y:List<&2, U32> -> @+m:List<&2, U32> -> Maybe<&2, BigInt>

def BigInt.modpow source · line 453 · raw

@b:BigInt -> @e:BigInt -> @m:BigInt -> Maybe<&2, BigInt>

b^e mod |m| in [0, |m|). None for m = 0 or e < 0.

def BigInt.gcd source · line 461 · raw

@a:BigInt -> @b:BigInt -> BigInt

Never negative; gcd(0, 0) is 0.

def BigInt.show source · line 467 · raw

@x:BigInt -> String

def BigInt.read.fin source · line 476 · raw

@neg:Bool -> @r:Pair(Bool, List<&2, U32>) -> Maybe<&2, BigInt>

def BigInt.read source · line 487 · raw

@s:String -> Maybe<&2, BigInt>

An optional '-' and at least one ASCII digit; leading zeros are fine.