def search_go

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

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

383# the last r in [lo, hi) with r^k <= n, given it holds at lo and fails at
384# hi: bisection while hi - lo > 1
385def search_go(~T: Data, ~op: N.Op<T> -> T, ~test: N.Test<T> -> Bool, fu: Nat, +n: T, +k: Nat, +lo: T, +hi: T, +m: T, +more: Bool, +hit: Bool) -> T:
386  match fu more hit:
387    case 0n _ _:
388      lo
389    case 1n+f False{} _:
390      lo
391    case 1n+f True{} True{}:
392      search_go(~T, ~op, ~test, f, n, k, m, hi, imid(~T, ~op, m, hi), test(N.Lt{inc(~T, ~op, m), hi}), root_le(~T, ~op, ~test, n, k, imid(~T, ~op, m, hi)))
393    case 1n+f True{} False{}:
394      search_go(~T, ~op, ~test, f, n, k, lo, m, imid(~T, ~op, lo, m), test(N.Lt{inc(~T, ~op, lo), m}), root_le(~T, ~op, ~test, n, k, imid(~T, ~op, lo, m)))