src/math/generic.bend checks

raw source on the hub · import bend-collections-laws-math@1.0.0.0/src/math/generic.bend as Generic

2 imports

import Base
import ./num.bend as N

Types

type QuotRem source · line 26 · raw

@-T:Data -> Data

TQR

@-T:Data -> @quot:T -> @rem:T -> QuotRem<T>

Definitions

def ok source · line 29 · raw

@-T:Data -> @m:Maybe<&2, T> -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

def or_zero source · line 36 · raw

@-T:Data -> @+z:T -> @m:Maybe<&2, T> -> T

def fuel source · line 44 · raw

Nat

enough steps for every loop at 64 bits (Euclid < 1.5 w + 2, bit loops w)

def fits source · line 48 · raw

@-T:Data -> @over:Bool -> @+x:T -> Maybe<&2, T>

x when it fits, else None

def pick source · line 72 · raw

@-T:Data -> @c:Bool -> @+a:T -> @+b:T -> T

def st_fin source · line 165 · raw

@-T:Data -> @st:Pair(T, Bool) -> Maybe<&2, T>

Templates

template cadd source · line 55 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> Maybe<&2, T>

template cmul source · line 58 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> Maybe<&2, T>

template lt source · line 61 · raw

@-T:Data -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> Bool

template le source · line 64 · raw

@-T:Data -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> Bool

template pos source · line 67 · raw

@-T:Data -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> Bool

template min source · line 80 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> T

Python's min(a, b) keeps a unless b < a; max keeps a unless a < b.

template max source · line 83 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> T

template clamp_ok source · line 86 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> @+lo:T -> @+hi:T -> @bad:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template clamp source · line 94 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> @+lo:T -> @+hi:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

min(max(x, lo), hi); hi < lo is a Domain error

template abs source · line 97 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> T

template sign_below source · line 100 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> @below:Bool -> T

template sign_above source · line 107 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> @above:Bool -> T

template sign source · line 115 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> T

1 above zero, -1 below, x itself otherwise (0, -0.0, NaN)

template sum_go source · line 118 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @xs:List<&2, T> -> @acc:Maybe<&2, T> -> Maybe<&2, T>

template sum source · line 127 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @xs:List<&2, T> -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template prod_go source · line 130 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @xs:List<&2, T> -> @acc:Maybe<&2, T> -> Maybe<&2, T>

template prod source · line 139 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @xs:List<&2, T> -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template mul_st source · line 143 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @bit:Bool -> @+x:T -> @+xok:Bool -> @st:Pair(T, Bool) -> Pair(T, Bool)

(value, still fits) after multiplying by x when bit is set

template sq_val source · line 151 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @more:Bool -> @+b:T -> T

the base squared, only while higher exponent bits remain

template sq_ok source · line 158 · raw

@-T:Data -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @more:Bool -> @+b:T -> @+bok:Bool -> Bool

template pow_go source · line 173 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+k:Nat -> @+b:T -> @+bok:Bool -> @st:Pair(T, Bool) -> Maybe<&2, T>

square-and-multiply, low bits first; an overflowing square means the result overflows too (a later bit multiplies it in). Callers pass fuel 1 + k: every step halves k, so the loop always ends on k == 0.

template pow source · line 182 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> @+k:Nat -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template one source · line 187 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> T

template inc source · line 190 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @+x:T -> T

template dec source · line 193 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @+x:T -> T

template zst source · line 197 · raw

@-T:Data -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> Pair(T, Bool)

(x, x == 0)

template gcd_go source · line 201 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+a:T -> @st:Pair(T, Bool) -> T

Euclid's algorithm on (a, (b, b == 0))

template hst source · line 214 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> Pair(T, Bool)

template strip_go source · line 218 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @st:Pair(T, Bool) -> T

x with its factors of two removed (x != 0)

template strip source · line 227 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> T

template zsm source · line 231 · raw

@-T:Data -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+d:T -> Pair(T, Pair(Bool, Bool))

(d, d == 0, a and d small)

template bnx2 source · line 234 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> @less:Bool -> Pair(T, Pair(T, Pair(Bool, Bool)))

template bnx source · line 241 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> Pair(T, Pair(T, Pair(Bool, Bool)))

template bloop source · line 246 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @st:Pair(T, Pair(T, Pair(Bool, Bool))) -> T

(a odd, (d, d == 0, small)): once a and d fit the instance's small type (Small), their gcd is taken there (GcdSmall: U64 runs Euclid on U32)

template bl_start source · line 257 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> T

template dbl source · line 260 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @c:Nat -> @+x:T -> T

template ev2 source · line 267 · raw

@-T:Data -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> Bool

template tw source · line 270 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fl:Nat -> @+a:T -> @+b:T -> @+c:Nat -> @both:Bool -> T

template bg_b source · line 279 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> @bz:Bool -> T

template bg_a source · line 286 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> @az:Bool -> T

template gcd_rb source · line 293 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> @bz:Bool -> T

template gcd_bin source · line 302 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> T

one Euclid step first (so a tiny b costs one division, not a bit per subtraction), then the binary loop

template gcd_pick source · line 305 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> @fast:Bool -> T

template gcd source · line 313 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> T

Euclid when division is native, the binary gcd otherwise

template lcm_ok source · line 316 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> @zero:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template lcm source · line 323 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template gcd_all_go source · line 326 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @xs:List<&2, T> -> @+acc:T -> T

template gcd_all source · line 333 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @xs:List<&2, T> -> T

template lcm_all_go source · line 336 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @xs:List<&2, T> -> @acc:Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T> -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template lcm_all source · line 345 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @xs:List<&2, T> -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template bit_length_go source · line 349 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+k:Nat -> @st:Pair(T, Bool) -> Nat

the number of halvings to reach zero

template bit_length source · line 358 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> Nat

template isqrt source · line 363 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> T

the instance's integer square root (a hardware estimate and an exact integer correction for U32 and U64)

template root_le_fin source · line 369 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @p:Maybe<&2, T> -> Bool

r^k <= n, with an overflowing power counted as > n

template root_le source · line 376 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:Nat -> @+r:T -> Bool

template imid source · line 380 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @+lo:T -> @+hi:T -> T

lo + (hi - lo) / 2, never above hi

template search_go source · line 385 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fu:Nat -> @+n:T -> @+k:Nat -> @+lo:T -> @+hi:T -> @+m:T -> @+more:Bool -> @+hit:Bool -> T

the last r in [lo, hi) with r^k <= n, given it holds at lo and fails at hi: bisection while hi - lo > 1

template search source · line 396 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:Nat -> @+hi:T -> T

template iroot_k source · line 400 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:Nat -> T

2^(bits(n) / k + 1) > the k-th root of n

template iroot source · line 409 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:Nat -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template ilog_go source · line 417 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+q:T -> @+b:T -> @+k:Nat -> @+p:T -> @up:Bool -> Nat

the largest k with b^k <= n; p <= n / b is asked before p * b is formed

template ilog_ok source · line 426 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+b:T -> @bad:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, Nat>

template ilog source · line 433 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+b:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, Nat>

template mul_by source · line 439 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+x:T -> @st:Pair(T, Bool) -> Pair(T, Bool)

(acc * x, still fits)

template fact_go source · line 445 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+i:T -> @+n:T -> @st:Pair(T, Bool) -> @more:Bool -> Maybe<&2, T>

2 * 3 * ... * n: i runs up to n, stopping at the first overflow

template factorial source · line 456 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template perm_go source · line 460 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+k:T -> @+m:T -> @st:Pair(T, Bool) -> @more:Bool -> Maybe<&2, T>

n (n - 1) ... (n - k + 1): m runs down while k counts the factors left

template perm_big source · line 471 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:T -> @big:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template perm source · line 478 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template comb_mul source · line 484 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+r:T -> @+t:T -> @+j:T -> @+g:T -> Pair(T, Bool)

C(n, i+1) = (r / g) * ((n - i) / ((i + 1) / g)) with r = C(n, i) and g = gcd(r, i + 1): exact, and it overflows only if C(n, i+1) does (C(n, i) grows for i < n / 2)

template comb_next source · line 487 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+r:T -> @+t:T -> @+j:T -> Pair(T, Bool)

template comb_go source · line 491 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+n:T -> @+i:T -> @+k:T -> @st:Pair(T, Bool) -> @more:Bool -> Maybe<&2, T>

i runs up to k (k <= n / 2), r = C(n, i)

template comb_k source · line 502 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template comb_big source · line 505 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:T -> @big:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template comb source · line 512 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+n:T -> @+k:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template mm_bit source · line 517 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @odd:Bool -> @+m:T -> @+b:T -> @+acc:T -> T

template pow_mod_go source · line 526 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+m:T -> @+b:T -> @+acc:T -> @st:Pair(T, Bool) -> T

right-to-left binary exponentiation on (e, e == 0), every product reduced mod m

template pow_mod_pick source · line 535 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+b:T -> @+e:T -> @+m:T -> @mont:Bool -> T

template pow_mod_ok source · line 542 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+b:T -> @+e:T -> @+m:T -> @zero:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template pow_mod source · line 550 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+b:T -> @+e:T -> @+m:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

Python's pow(b, e, m) for m > 0

template submod source · line 554 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @+m:T -> @+s0:T -> @+x:T -> @below:Bool -> T

s0 - x mod m for s0, x < m, without leaving [0, m)

template inv_sub source · line 561 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+m:T -> @+s0:T -> @+x:T -> T

template inv_step source · line 564 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+m:T -> @+q:T -> @+s0:T -> @+s1:T -> T

template inv_go source · line 569 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @fuel:Nat -> @+m:T -> @+r0:T -> @+s0:T -> @+s1:T -> @st:Pair(T, Bool) -> Pair(T, T)

extended Euclid on (m, a mod m), keeping the coefficient of a mod m; st = (r1, r1 == 0)

template inv_one source · line 578 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @+m:T -> @+s:T -> @one:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template inv_fin source · line 585 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+m:T -> @r:Pair(T, T) -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template inv_ok source · line 589 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+m:T -> @zero:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

template mod_inverse source · line 597 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+m:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, T>

pow(a, -1, m): the x < m with a * x == 1 (mod m)

template divmod_ok source · line 602 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @+a:T -> @+b:T -> @zero:Bool -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, QuotRem<T>>

template divmod source · line 609 · raw

@-T:Data -> @-op:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Op<T> -> T) -> @-test:(@_:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.Test<T> -> Bool) -> @+a:T -> @+b:T -> Result<&2, &2, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/num.NumError, QuotRem<T>>