F64sqk.qb: def of bend-collections-laws-math@1.0.0.0
Import: import bend-collections-laws-math@1.0.0.0/proofs/math/typed/f64sqk.bend as F64sqk
Lines 29-38 of bend-collections-laws-math@1.0.0.0/proofs/math/typed/f64sqk.bend: https://jend.leeeet.dev/read.txt?path=bend-collections-laws-math@1.0.0.0/proofs/math/typed/f64sqk.bend&start_line=29&end_line=38

import Base
import bend-collections-laws-math@1.0.0.0/spec/lib/common.bend as C
import bend-collections-laws-math@1.0.0.0/proofs/lib/nat.bend as N
import bend-collections-laws-math@1.0.0.0/proofs/lib/logic.bend as L
import bend-collections-laws-math@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend as NA
import bend-collections-laws-math@1.0.0.0/proofs/math/typed/width.bend as WW
import bend-collections-laws-math@1.0.0.0/proofs/math/typed/w64dm.bend as DM
import bend-collections-laws-math@1.0.0.0/proofs/math/typed/w64div.bend as W64D

# from below: n 2^64 < (S0 + 1)^2, so isqrt(n 2^64) <= S0
# from above: S0^2 <= n 2^64 + q^2
# q <= 2^32: q D <= r 2^32 <= D 2^32 < (2^32 + 1) D
def qb(+one: Nat, +h1: {one == 1n : Nat}, +r: Nat, +q: Nat, +D: Nat, +hq: {Nat.is_le(Nat.mul(q, D), C.shift(32n, r)) == True{} : Bool}, +hr: {Nat.is_le(r, D) == True{} : Bool}, +hD: {Nat.is_lt(0n, D) == True{} : Bool}) -> {Nat.is_le(q, C.shift(32n, one)) == True{} : Bool}:
  +e1 = Equal.trans(Nat, C.shift(32n, D), Nat.mul(D, C.shift(32n, one)), Nat.mul(C.shift(32n, one), D), WW.shift_mul_one(32n, one, h1, D), NA.mul_comm(D, C.shift(32n, one)))
  +h2 = N.le_trans(Nat.mul(q, D), C.shift(32n, r), C.shift(32n, D), hq, WW.shift_mono(32n, r, D, hr))
  +h3 = L.subst(Nat, z => {Nat.is_le(Nat.mul(q, D), z) == True{} : Bool}, C.shift(32n, D), Nat.mul(C.shift(32n, one), D), e1, h2)
  +h4 = L.subst(Nat, z => {Nat.is_lt(Nat.mul(C.shift(32n, one), D), z) == True{} : Bool}, Nat.add(Nat.mul(C.shift(32n, one), D), D), Nat.add(D, Nat.mul(C.shift(32n, one), D)), NA.add_comm(Nat.mul(C.shift(32n, one), D), D), DM.lt_add_pos(Nat.mul(C.shift(32n, one), D), D, hD))
  +h5 = N.le_lt_trans(Nat.mul(q, D), Nat.mul(C.shift(32n, one), D), Nat.mul(1n+C.shift(32n, one), D), h3, h4)
  N.lt_succ_le(q, C.shift(32n, one), W64D.lt_cancel_mul(q, 1n+C.shift(32n, one), D, h5))

Uses (18):
  https://jend.leeeet.dev/definition.txt?path=Base/base.bend&name=Bool
  https://jend.leeeet.dev/definition.txt?path=Base/base.bend&name=Equal.trans
  https://jend.leeeet.dev/definition.txt?path=Base/base.bend&name=Nat
  https://jend.leeeet.dev/definition.txt?path=Base/base.bend&name=Nat.add
  https://jend.leeeet.dev/definition.txt?path=Base/base.bend&name=Nat.is_le
  https://jend.leeeet.dev/definition.txt?path=Base/base.bend&name=Nat.is_lt
  https://jend.leeeet.dev/definition.txt?path=Base/base.bend&name=Nat.mul
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend&name=add_comm
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend&name=mul_comm
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/lib/logic.bend&name=subst
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/lib/nat.bend&name=le_lt_trans
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/lib/nat.bend&name=le_trans
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/lib/nat.bend&name=lt_succ_le
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/math/typed/w64div.bend&name=lt_cancel_mul
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/math/typed/w64dm.bend&name=lt_add_pos
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/math/typed/width.bend&name=shift_mono
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/proofs/math/typed/width.bend&name=shift_mul_one
  https://jend.leeeet.dev/definition.txt?path=bend-collections-laws-math@1.0.0.0/spec/lib/common.bend&name=shift