library colibrilib.polynome — module ModRwThe rewriting of the Euclidean remainders mod_e x d (colibri2/theories/LRA/dom_modrw.ml): a linear form that differs from the linear form of x by an integer multiple of d, so with the same remainder. Two remainders with the same reduced form and the same |d| are equal.
module ModRw716use int.Int717use real.RealInfix718use real.Abs719use real.FromInt720use real.Truncate721use list.List722use option.Option723use colibrilib.ring.Atom724use colibrilib.stda.StdA as A725use colibrilib.q.Real as Real726use colibrilib.qa.ModE727use colibrilib.generic_divrem_rewrite.DefE728use Assoc729use PT730use Lin731use colibrilib.spec.EvalOn732
The atoms of p have integer values in env
predicate integer_atoms (p:t) (env: Atom.t -> real) =735forall k. has k (bindings p.poly) -> Real.is_integer (env k)736
r and p have the same remainder by any nonzero d with |d| = |y|, in every environment
predicate same_rem_node (y:Atom.t) (p r:t) =740forall d. d <> 0.0 ->741same_on (fun env -> abs d = abs (env y)) (fun v -> Real.mod_e v d) value p r742
The remainder: in [0, |m|), and the same for x and x + m * n
Valid (50ms) (colibri2)let ghost mod_facts (x m:real) (n:int) : unit745requires { m <> 0.0 }746ensures { 0.0 <=. Real.mod_e x m <. abs m }747ensures { x = m *. from_int (Real.div_e x m) +. Real.mod_e x m }748ensures { Real.mod_e (x +. m *. from_int n) m = Real.mod_e x m }749ensures { 0.0 <=. x <. abs m -> Real.mod_e x m = x }750= {proof…} mod_e_facts x m;751GE.on_add_period x m n;752if pure { 0.0 <=. x <. abs m } then GE.when_in_bound x m {qed}753
The sign of the divisor does not change the remainder
Valid (37ms) (colibri2)let ghost mod_abs (x m m':real) : unit756requires { m <> 0.0 /\ abs m = abs m' }757ensures { Real.mod_e x m = Real.mod_e x m' }758= {proof…} abs_divisor x m; abs_divisor x m' {qed}759
The integer value of an integer real
function iv (x:real) : int = truncate x762
The quotient of l and of its reduction by m
function quot (m:real) (env: Atom.t -> real) (l:list binding) : int =765match l with766| Nil -> 0767| Cons (k, a) r -> Real.div_e (A.real a) m * iv (env k) + quot m env r768end769
The reduced coefficient
function redo (m:A.t) (o:option A.t) : option A.t =772match o with None -> None | Some a -> nzv (A.mod_e a m) end773
The coefficients of l reduced modulo m
Valid (453ms) (colibri2 19) (cvc4) (cvc5 3) (split_vc 3) (depth 2)let rec ghost lred (m:A.t) (l:list binding) : list binding776requires { sorted l /\ A.real m <> 0.0 }777ensures { sorted result }778ensures { forall k. assoc k result = redo m (assoc k l) }779ensures { forall env. (forall k. has k l -> Real.is_integer (env k)) ->780evall env l781= evall env result +. A.real m *. from_int (quot (A.real m) env l) }782variant { l }783= match l with784| Nil -> Nil785| Cons (k, a) r ->786let t = lred m r in787let v = A.mod_e a m in788let res = if pure { A.real v = 0.0 } then t else Cons (k, v) t in789let lemma pw (k':Atom.t) : unit790ensures { assoc k' res = redo m (assoc k' l) }791= if pure { k' = k } then assert { not (has k t) by not (has k r) } in792let lemma ev (env: Atom.t -> real) : unit793requires { forall k. has k l -> Real.is_integer (env k) }794ensures { evall env l795= evall env res +. A.real m *. from_int (quot (A.real m) env l) }796= assert { forall k'. has k' r -> has k' l };797assert { Real.is_integer (env k) by has k l };798let ghost i = any int ensures { env k = from_int result } in799assert { iv (env k) = i };800mod_facts (A.real a) (A.real m) 0;801let ghost d = pure { Real.div_e (A.real a) (A.real m) } in802assert { A.real a *. env k803= A.real v *. env k +. A.real m *. from_int (d * i) };804let q = quot (A.real m) env r in805assert { evall env r = evall env t +. A.real m *. from_int q };806assert { quot (A.real m) env l = d * i + q };807assert { from_int (d * i + q) = from_int (d * i) +. from_int q };808assert { A.real m *. from_int (d * i + q)809= A.real m *. from_int (d * i) +. A.real m *. from_int q };810assert { evall env res = A.real v *. env k +. evall env t };811assert { evall env l = A.real a *. env k +. evall env r } in812res813end814
The closure of reduce_cst
Valid (20ms) (colibri2)let function redf (m:A.t) (_k:Atom.t) (o1 _o2:option A.t) : option A.t817requires { A.real m <> 0.0 }818= match o1 with None -> None | Some a -> nz (A.mod_e a m) end819
The constant and the coefficients reduced modulo m: the same remainder by m when the atoms are integers
Valid (728ms) (colibri2 11) (cvc4) (cvc5 10) (split_vc) (depth 1)let reduce_cst (p:t) (m:A.t) : t823requires { A.real m <> 0.0 }824ensures { 0.0 <=. A.real result.cst <. abs (A.real m) }825ensures { forall k v. get k result.poly = Some v ->8260.0 <=. A.real v <. abs (A.real m) }827ensures { forall k. has k (bindings result.poly) -> has k (bindings p.poly) }828ensures { same_on (integer_atoms p) (fun v -> Real.mod_e v (A.real m)) value p result }829ensures { bindings result.poly = Nil ->830forall env. integer_atoms p env ->831Real.mod_e (eval env p) (A.real m) = A.real result.cst }832= let mp = PT.merge (redf m) p.poly (PT.empty ()) in833let l = lred m (bindings p.poly) in834ext_eval (bindings mp) l;835let lemma nzm (k:Atom.t) (v:A.t) : unit836requires { get k mp = Some v }837ensures { A.real v <> 0.0 }838= match get k p.poly with None -> absurd | Some _ -> () end in839let r = { cst = A.mod_e p.cst m; poly = mp } in840let lemma rng (k:Atom.t) (v:A.t) : unit841requires { get k mp = Some v }842ensures { 0.0 <=. A.real v <. abs (A.real m) }843= match get k p.poly with844| None -> absurd845| Some a -> mod_facts (A.real a) (A.real m) 0846end in847mod_facts (A.real p.cst) (A.real m) 0;848let lemma ev (env: Atom.t -> real) : unit849requires { forall k. has k (bindings p.poly) -> Real.is_integer (env k) }850ensures { Real.mod_e (eval env p) (A.real m) = Real.mod_e (eval env r) (A.real m) }851= let ghost n = pure { Real.div_e (A.real p.cst) (A.real m) + quot (A.real m) env (bindings p.poly) } in852assert { eval env p = eval env r +. A.real m *. from_int n };853mod_facts (eval env r) (A.real m) n;854if pure { bindings mp = Nil } then mod_facts (A.real r.cst) (A.real m) 0 in855r856Valid (142ms) (cvc5)857let ghost neg_mul (a b:real) : unit858ensures { (-. a) *. b = -. (b *. a) }859= ()860
The integer multiples of y removed from p: the same remainder by any d with |d| = |y|
Valid (675ms) (colibri2 13) (cvc4 4) (cvc5) (split_vc) (depth 1)let reduce_node (p:t) (y:Atom.t) : t864ensures { same_rem_node y p result }865ensures { bindings result.poly = Nil -> A.real result.cst = 0.0 ->866forall env d. d <> 0.0 -> abs d = abs (env y) -> Real.mod_e (eval env p) d = 0.0 }867= match PT.find_opt y p.poly with868| None ->869let lemma z (d:real) : unit870requires { d <> 0.0 }871ensures { Real.mod_e 0.0 d = 0.0 }872= mod_facts 0.0 d 0 in873p874| Some a ->875let one = A.of_int 1 in876let a' = A.mod_e a one in877let c = A.sub a' a in878mod_facts (A.real a) 1.0 0;879let ghost n = pure { Real.div_e (A.real a) 1.0 } in880assert { A.real c = -. from_int n };881let my = monome one y in882let r = x_p_cy p c my in883let lemma ev (env: Atom.t -> real) (d:real) : unit884requires { d <> 0.0 /\ abs d = abs (env y) }885ensures { Real.mod_e (eval env p) d = Real.mod_e (eval env r) d }886= assert { value r env = value p env +. A.real c *. value my env };887assert { value my env = env y };888assert { eval env r = eval env p +. A.real c *. env y };889neg_mul (from_int n) (env y);890assert { A.real c *. env y = -. (env y *. from_int n) };891assert { eval env p = eval env r +. env y *. from_int n };892if pure { d = env y } then mod_facts (eval env r) d n893else begin894assert { d = -. env y };895assert { eval env p = eval env r +. d *. from_int (- n) };896mod_facts (eval env r) d (- n)897end;898mod_facts 0.0 d 0 in899r900end901end902