def iroot_k

bend-collections-laws-math@1.0.0.0 · src/math/generic.bend:399

import Base
import bend-collections-laws-math@1.0.0.0/src/math/num.bend as N

399# 2^(bits(n) / k + 1) > the k-th root of n
400def iroot_k(~T: Data, ~op: N.Op<T> -> T, ~test: N.Test<T> -> Bool, +n: T, +k: Nat) -> T:
401  match k:
402    case 0n:
403      op(N.ZeroOp{})
404    case 1n:
405      n
406    case 2n+ +kp:
407      search(~T, ~op, ~test, n, 2n+kp, op(N.Pow2{1n+Nat.div(bit_length(~T, ~op, ~test, n), 2n+kp)}))