def quotient_below

bendtorch-core@0.1.0.0 · src/autograd/reduce_fiber_proof.bend:147

import Base
import bendtorch-core@0.1.0.0/src/shape/core.bend as Shape
import bendtorch-core@0.1.0.0/src/storage/arith.bend as Arith
import bendtorch-core@0.1.0.0/src/storage/api.bend as Api

147# Below a * size, the quotient by size is below a.
148def quotient_below(+t: Nat, +a: Nat, +size: Nat, below: {Nat.is_lt(t, Nat.mul(a, size)) == True{} : Bool},
149  decision: Shape.BoolCase<Nat.is_lt(Nat.div(t, size), a)>, given: Decomposed<t, size>) ->
150  {Nat.is_lt(Nat.div(t, size), a) == True{} : Bool}:
151  match decision:
152    case Shape.BTrue{equal}:
153      Equal.sym(Bool, True{}, Nat.is_lt(Nat.div(t, size), a), equal)
154    case Shape.BFalse{equal}:
155      Decomposed{rest, sum} = given
156      +q = Nat.div(t, size)
157      +r = Nat.mod(t, size)
158      +grown = le_trans(Nat.mul(a, size), Nat.mul(q, size), t,
159        mul_le_mono(a, q, size, Arith.not_lt_le(q, a, Equal.sym(Bool, False{}, Nat.is_lt(q, a), equal))),
160        %sum : {Nat.is_le(Nat.mul(q, size), _) == True{} : Bool}
161        Api.le_add_right(Nat.mul(q, size), r))
162      Empty.absurd({Nat.is_lt(q, a) == True{} : Bool},
163        Arith.clash(Equal.trans(Bool, False{}, Nat.is_lt(t, t), True{}, Equal.sym(Bool, Nat.is_lt(t, t), False{}, lt_irrefl(t)),
164          Arith.lt_le_trans(t, Nat.mul(a, size), t, below, grown))))