bend-collections

Releases (1)

• 1.0.0.0 indexed

Definitions (4,483)

src/math/generic.bend

• def zsm(d, d == 0, a and d small)
• def bnx2
• def bnx
• def bloop(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)
• def bl_start
• def dbl
• def ev2
• def tw
• def bg_b
• def bg_a
• def gcd_rb
• def gcd_binone Euclid step first (so a tiny b costs one division, not a bit per subtraction), then the binary loop
• def gcd_pick
• def gcdEuclid when division is native, the binary gcd otherwise
• def lcm_ok
• def lcm
• def gcd_all_go
• def gcd_all
• def lcm_all_go
• def lcm_all
• def bit_length_gothe number of halvings to reach zero
• def bit_length
• def isqrtthe instance's integer square root (a hardware estimate and an exact integer correction for U32 and U64)
• def root_le_finr^k <= n, with an overflowing power counted as > n
• def root_le
• def imidlo + (hi - lo) / 2, never above hi
• def search_gothe last r in [lo, hi) with r^k <= n, given it holds at lo and fails at hi: bisection while hi - lo > 1
• def search
• def iroot_k2^(bits(n) / k + 1) > the k-th root of n
• def iroot
• def ilog_gothe largest k with b^k <= n; p <= n / b is asked before p * b is formed
• def ilog_ok
• def ilog
• def mul_by(acc * x, still fits)
• def fact_go2 * 3 * ...
• def factorial
• def perm_gon (n - 1) ...
• def perm_big
• def perm
• def comb_mulC(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)
• def comb_next
• def comb_goi runs up to k (k <= n / 2), r = C(n, i)
• def comb_k
• def comb_big
• def comb
• def mm_bit
• def pow_mod_goright-to-left binary exponentiation on (e, e == 0), every product reduced mod m
• def pow_mod_pick
• def pow_mod_ok
• def pow_modPython's pow(b, e, m) for m > 0
• def submods0 - x mod m for s0, x < m, without leaving [0, m)
• def inv_sub
• def inv_step
• def inv_goextended Euclid on (m, a mod m), keeping the coefficient of a mod m; st = (r1, r1 == 0)
• def inv_one
• def inv_fin
• def inv_ok
• def mod_inversepow(a, -1, m): the x < m with a * x == 1 (mod m)
• def divmod_ok
• def divmod

src/math/hash.bend

• def phi32
• def mix
• def fold
• def bucket

src/math/instances.bend

• def u32_mul_overa * b >= 2^32: the full product has a nonzero high word
• def u32_mulmod
• def u32_op
• def u32_add_over
• def u32_odd
• def u32_is
• def u64_pow22^k for k < 64
• def u64_op
• def u64_is
• def f32_op
• def f32_is

src/math/natural.bend

• type MathError
• type Bezoutthe last nonzero remainder of the extended Euclid loop and its coefficient: a * coef == gcd (mod m)
• type QuotRema // b and a % b
• def gcd_goEuclid's algorithm; b <= fuel throughout (every step lowers b).
• def gcd
• def lcm
• def gcd_all_go
• def gcd_all
• def lcm_all_go
• def lcm_all
• def sum_go
• def sum
• def prod_go
• def prod
• def factorial_go
• def factorial
• def perm_gon * (n - 1) * ...
• def perm
• def comb_gor_{i+1} = r_i * (n - i) / (i + 1): every r_i is C(n, i), so the division is exact (reference section 8.6).
• def comb_small
• def comb
• def bit_length_go
• def bit_length
• def midBinary search for the last r in [lo, hi) where the test holds, given it holds at lo and fails at hi (reference section 8.5 notes the float-sqrt shortcut is wrong above 2^52; this search is exact).
• def pow_le_gor^k <= n without forming a product above n: `ok` is acc * r <= n, asked as acc <= n / r, and acc * r is only formed once it is known to fit.