def lo_bound

bend-collections-laws-math@1.0.0.0 · proofs/math/typed/f64sqr.bend:83

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/natural/sqrtn.bend as SQ2
import bend-collections-laws-math@1.0.0.0/proofs/math/typed/width.bend as WW

83# N < (S0 + 1)^2, so isqrt(N) <= S0
84def lo_bound(+s: Nat, +rr: Nat, +n: Nat, +Q: Nat, +U: Nat, +D: Nat, +hn: {Nat.add(Nat.mul(s, s), rr) == n : Nat}, +hD: {Nat.add(s, s) == D : Nat}, +hc: {Nat.add(Nat.mul(Q, D), U) == C.shift(32n, rr) : Nat}, +hU: {Nat.is_le(U, D) == True{} : Bool}) -> {Nat.is_lt(C.shift(64n, n), Nat.mul(1n+Nat.add(Q, C.shift(32n, s)), 1n+Nat.add(Q, C.shift(32n, s)))) == True{} : Bool}:
85  +a1 = N.le_add_right(C.shift(64n, n), Nat.mul(Q, Q))
86  +a2 = L.subst(Nat, z => {Nat.is_le(C.shift(64n, n), z) == True{} : Bool}, Nat.add(C.shift(64n, n), Nat.mul(Q, Q)), Nat.add(Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), C.shift(32n, U)), identN(s, rr, n, Q, U, D, hn, hD, hc), a1)
87  +hPs = L.subst(Nat, z => {Nat.is_le(C.shift(32n, s), z) == True{} : Bool}, Nat.add(C.shift(32n, s), Q), Nat.add(Q, C.shift(32n, s)), NA.add_comm(C.shift(32n, s), Q), N.le_add_right(C.shift(32n, s), Q))
88  +a3 = N.le_trans(C.shift(32n, U), C.shift(32n, D), Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), WW.shift_mono(32n, U, D, hU), L.subst(Nat, z => {Nat.is_le(C.shift(32n, z), Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))) == True{} : Bool}, Nat.add(s, s), D, hD, L.subst(Nat, z => {Nat.is_le(z, Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))) == True{} : Bool}, Nat.add(C.shift(32n, s), C.shift(32n, s)), C.shift(32n, Nat.add(s, s)), Equal.sym(Nat, C.shift(32n, Nat.add(s, s)), Nat.add(C.shift(32n, s), C.shift(32n, s)), WW.shift_add(32n, s, s)), SQ2.le_add2(C.shift(32n, s), Nat.add(Q, C.shift(32n, s)), C.shift(32n, s), Nat.add(Q, C.shift(32n, s)), hPs, hPs))))
89  +a4 = N.le_trans(C.shift(64n, n), Nat.add(Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), C.shift(32n, U)), Nat.add(Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), a2, N.le_add_left(C.shift(32n, U), Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), a3))
90  +a5 = L.subst(Nat, z => {Nat.is_le(C.shift(64n, n), z) == True{} : Bool}, Nat.add(Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), Nat.add(Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), NA.add_comm(Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), a4)
91  L.subst(Nat, z => {Nat.is_lt(C.shift(64n, n), z) == True{} : Bool}, 1n+Nat.add(Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), Nat.mul(1n+Nat.add(Q, C.shift(32n, s)), 1n+Nat.add(Q, C.shift(32n, s))), Equal.sym(Nat, Nat.mul(1n+Nat.add(Q, C.shift(32n, s)), 1n+Nat.add(Q, C.shift(32n, s))), 1n+Nat.add(Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), SQ2.succ_mul_succ(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), N.le_lt_trans(C.shift(64n, n), Nat.add(Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), 1n+Nat.add(Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))), a5, N.lt_succ(Nat.add(Nat.add(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s))), Nat.mul(Nat.add(Q, C.shift(32n, s)), Nat.add(Q, C.shift(32n, s)))))))