bend-collections

Releases (1)

• 1.0.0.0 indexed

Definitions (4,483)

src/math/natural.bend

• def root_le
• def search_gothe test is r^k <= n
• def search
• def sqrt_nextthe largest r with r * r <= n, by Heron's (Newton's) iteration as in Lean 4 Mathlib's Nat.sqrt: g := (g + n / g) / 2 while that decreases g.
• def sqrt_iter
• def isqrt_from
• def isqrt
• def iroot_kthe largest r with r^k <= n (k >= 1)
• def iroot
• def ilog_gothe largest k with b^k <= n: p is b^k, `up` is p * b <= n, asked as p <= n / b so no product above n is formed
• def ilog_ok
• def ilog
• def pow_mod_oddright-to-left binary exponentiation, reducing mod m after every product: acc * base^e == b^e0 (mod m) throughout
• def pow_mod_go
• def pow_mod
• def inv_stepExtended Euclid on (m, a mod m) keeping only the coefficient of a, mod m: a * s0 == r0 and a * s1 == r1 (mod m).
• def inv_go
• def inv_fin
• def mod_inversepow(a, -1, m): the x < m with a * x == 1 (mod m)
• def divmod
• def clamp_ok
• def clamp

src/math/num.bend

• type NumError
• type Op
• type Test

src/math/pow2.bend

• def go
• def pow2t

src/math/random.bend

• def chacha8
• def chacha8_next
• def pcg
• def pcg_next
• def uint64
• def uint32
• def int64
• def int32
• def uint64n
• def uint_below
• def uint32n
• def intn
• def int_range
• def float64
• def shuffle
• def perm

src/math/random/chacha8.bend

• type Phasethe next group of the iteration: blocks 0-3, 4-7, 8-11 or 12-15
• type ChaCha8
• def zero
• def of_key
• def rekeythe key of the next iteration: the last four words of the last group
• def lastthe last group: 28 words of output, then the next key
• def refill
• def pop
• def nextthe next 64-bit output (a refill always yields a nonempty buffer)
• def le32the little-endian word of four bytes (Go's byteorder.LEUint32)
• def all_bytes
• def key_of
• def lift
• def seed_ok
• def newGo's NewChaCha8(seed): the seed is 32 bytes, each below 256

src/math/random/chacha8/block.bend

• type Keythe 256-bit key as eight little-endian words
• type Vectorthe ChaCha state x[0..15]
• def initthe initial state: constants, key, 32-bit block counter, zero nonce
• def drone double round: four column quarter rounds, then four diagonal ones
• def finishthe key words added back to words 4..11
• def blockthe ChaCha8Rand block with counter ctr: eight rounds
• def interleavefour blocks interleaved word by word, as 32 little-endian 64-bit words
• def groupthe group of the blocks ctr, ctr + 1, ctr + 2, ctr + 3

src/math/random/pcg.bend

• type PCG
• def new
• def mul_hi2549297995355413924, 4865540595714422341
• def mul_lo
• def inc_hi6364136223846793005, 1442695040888963407
• def inc_lo
• def cheap_mul0xda942042e4dd58b5
• def xor64
• def step_finthe new state from the product's low word l and high word h
• def step_mul
• def step_withstate * (mh:ml) + (ih:il) mod 2^128 (Go's (*PCG).next with its constants as parameters)
• def step
• def dxsm2
• def dxsm_withthe DXSM output of a state hi:lo with the multiplier cm
• def out
• def next

src/math/random/rand.bend

• def fst
• def snd
• def uint64
• def top32
• def uint32
• def low63
• def int64
• def top31
• def int32
• def and64
• def is_pow2n & (n - 1) == 0: n is a power of two (or zero)
• def mask
• def thresh2^64 mod n = (2^64 - n) mod n, for n > 0 (Go: -n % n)
• type Drawthe draw x as the product x * n = hi:lo, kept with the state
• def draw_fin
• def draw
• def againone rejection step: while lo < t, draw again; an accepted draw is kept
• def step