def low_mod

bend-collections-laws-math@1.0.0.0 · proofs/math/typed/fixgen.bend:101

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

101# low(k, n) is n mod 2^k
102def low_mod(+k: Nat, +n: Nat, +pp: Nat, +hp: {C.pow2(k) == 1n+pp : Nat}) -> {C.low(k, n) == Nat.mod(n, 1n+pp) : Nat}:
103  +l = C.low(k, n)
104  +q = C.high(k, n)
105  +hl = Equal.trans(Bool, Nat.is_lt(l, 1n+pp), Nat.is_lt(l, C.pow2(k)), True{}, Equal.cong(Nat, Bool, t => Nat.is_lt(l, t), 1n+pp, C.pow2(k), Equal.sym(Nat, C.pow2(k), 1n+pp, hp)), WW.low_lt(k, n))
106  +es = Equal.trans(Nat, C.shift(k, q), Nat.mul(q, C.shift(k, 1n)), Nat.mul(q, 1n+pp), WW.shift_mul(k, q), Equal.cong(Nat, Nat, t => Nat.mul(q, t), C.shift(k, 1n), 1n+pp, Equal.trans(Nat, C.shift(k, 1n), C.pow2(k), 1n+pp, WW.shift_one(k), hp)))
107  +en = Equal.trans(Nat, n, Nat.add(l, C.shift(k, q)), Nat.add(Nat.mul(q, 1n+pp), l), WW.low_high(k, n), Equal.trans(Nat, Nat.add(l, C.shift(k, q)), Nat.add(l, Nat.mul(q, 1n+pp)), Nat.add(Nat.mul(q, 1n+pp), l), Equal.cong(Nat, Nat, t => Nat.add(l, t), C.shift(k, q), Nat.mul(q, 1n+pp), es), N.add_comm(l, Nat.mul(q, 1n+pp))))
108  +em = Equal.trans(Nat, Nat.mod(n, 1n+pp), Nat.mod(Nat.add(Nat.mul(q, 1n+pp), l), 1n+pp), l, Equal.cong(Nat, Nat, t => Nat.mod(t, 1n+pp), n, Nat.add(Nat.mul(q, 1n+pp), l), en), R.mod_of(q, pp, l, hl))
109  Equal.sym(Nat, Nat.mod(n, 1n+pp), l, em)