Common — library colibrilib.polynome — module ModRw

The 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.

716
module ModRw
717
use int.Int
718
use real.RealInfix
719
use real.Abs
720
use real.FromInt
721
use real.Truncate
722
use list.List
723
use option.Option
724
use colibrilib.ring.Atom
725
use colibrilib.stda.StdA as A
726
use colibrilib.q.Real as Real
727
use colibrilib.qa.ModE
728
use colibrilib.generic_divrem_rewrite.DefE
729
use Assoc
730
use PT
731
use Lin
732
use colibrilib.spec.EvalOn

The atoms of p have integer values in env

735
predicate
integer_atoms
(p:t) (env: Atom.t -> real) =
736
forall k. has k (bindings p.poly) -> Real.is_integer (env k)

r and p have the same remainder by any nonzero d with |d| = |y|, in every environment

740
predicate
same_rem_node
(y:Atom.t) (p r:t) =
741
forall d. d <> 0.0 ->
742
same_on (fun env -> abs d = abs (env y)) (fun v -> Real.mod_e v d) value p r

The remainder: in [0, |m|), and the same for x and x + m * n

  Valid (50ms) (colibri2)
745
let ghost
mod_facts
(x m:real) (n:int) : unit
746
requires { m <> 0.0 }
747
ensures { 0.0 <=. Real.mod_e x m <. abs m }
748
ensures { x = m *. from_int (Real.div_e x m) +. Real.mod_e x m }
749
ensures { Real.mod_e (x +. m *. from_int n) m = Real.mod_e x m }
750
ensures { 0.0 <=. x <. abs m -> Real.mod_e x m = x }
751
= {proof…} mod_e_facts x m;
752
GE.on_add_period x m n;
753
if pure { 0.0 <=. x <. abs m } then GE.when_in_bound x m {qed}

The sign of the divisor does not change the remainder

  Valid (37ms) (colibri2)
756
let ghost
mod_abs
(x m m':real) : unit
757
requires { m <> 0.0 /\ abs m = abs m' }
758
ensures { Real.mod_e x m = Real.mod_e x m' }
759
= {proof…} abs_divisor x m; abs_divisor x m' {qed}

The integer value of an integer real

762
function
iv
(x:real) : int = truncate x

The quotient of l and of its reduction by m

765
function
quot
(m:real) (env: Atom.t -> real) (l:list binding) : int =
766
match l with
767
| Nil -> 0
768
| Cons (k, a) r -> Real.div_e (A.real a) m * iv (env k) + quot m env r
769
end

The reduced coefficient

772
function
redo
(m:A.t) (o:option A.t) : option A.t =
773
match o with None -> None | Some a -> nzv (A.mod_e a m) end

The coefficients of l reduced modulo m

  Valid (453ms) (colibri2 19) (cvc4) (cvc5 3) (split_vc 3) (depth 2)
776
let rec ghost
lred
(m:A.t) (l:list binding) : list binding
777
requires { sorted l /\ A.real m <> 0.0 }
778
ensures { sorted result }
779
ensures { forall k. assoc k result = redo m (assoc k l) }
780
ensures { forall env. (forall k. has k l -> Real.is_integer (env k)) ->
781
evall env l
782
= evall env result +. A.real m *. from_int (quot (A.real m) env l) }
783
variant { l }
784
= match l with
785
| Nil -> Nil
786
| Cons (k, a) r ->
787
let t = lred m r in
788
let v = A.mod_e a m in
789
let res = if pure { A.real v = 0.0 } then t else Cons (k, v) t in
790
let lemma pw (k':Atom.t) : unit
791
ensures { assoc k' res = redo m (assoc k' l) }
792
= if pure { k' = k } then assert { not (has k t) by not (has k r) } in
793
let lemma ev (env: Atom.t -> real) : unit
794
requires { forall k. has k l -> Real.is_integer (env k) }
795
ensures { evall env l
796
= evall env res +. A.real m *. from_int (quot (A.real m) env l) }
797
= assert { forall k'. has k' r -> has k' l };
798
assert { Real.is_integer (env k) by has k l };
799
let ghost i = any int ensures { env k = from_int result } in
800
assert { iv (env k) = i };
801
mod_facts (A.real a) (A.real m) 0;
802
let ghost d = pure { Real.div_e (A.real a) (A.real m) } in
803
assert { A.real a *. env k
804
= A.real v *. env k +. A.real m *. from_int (d * i) };
805
let q = quot (A.real m) env r in
806
assert { evall env r = evall env t +. A.real m *. from_int q };
807
assert { quot (A.real m) env l = d * i + q };
808
assert { from_int (d * i + q) = from_int (d * i) +. from_int q };
809
assert { A.real m *. from_int (d * i + q)
810
= A.real m *. from_int (d * i) +. A.real m *. from_int q };
811
assert { evall env res = A.real v *. env k +. evall env t };
812
assert { evall env l = A.real a *. env k +. evall env r } in
813
res
814
end

The closure of reduce_cst

  Valid (20ms) (colibri2)
817
let function
redf
(m:A.t) (_k:Atom.t) (o1 _o2:option A.t) : option A.t
818
requires { A.real m <> 0.0 }
819
= match o1 with None -> None | Some a -> nz (A.mod_e a m) end

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)
823
let
reduce_cst
(p:t) (m:A.t) : t
824
requires { A.real m <> 0.0 }
825
ensures { 0.0 <=. A.real result.cst <. abs (A.real m) }
826
ensures { forall k v. get k result.poly = Some v ->
827
0.0 <=. A.real v <. abs (A.real m) }
828
ensures { forall k. has k (bindings result.poly) -> has k (bindings p.poly) }
829
ensures { same_on (integer_atoms p) (fun v -> Real.mod_e v (A.real m)) value p result }
830
ensures { bindings result.poly = Nil ->
831
forall env. integer_atoms p env ->
832
Real.mod_e (eval env p) (A.real m) = A.real result.cst }
833
= let mp = PT.merge (redf m) p.poly (PT.empty ()) in
834
let l = lred m (bindings p.poly) in
835
ext_eval (bindings mp) l;
836
let lemma nzm (k:Atom.t) (v:A.t) : unit
837
requires { get k mp = Some v }
838
ensures { A.real v <> 0.0 }
839
= match get k p.poly with None -> absurd | Some _ -> () end in
840
let r = { cst = A.mod_e p.cst m; poly = mp } in
841
let lemma rng (k:Atom.t) (v:A.t) : unit
842
requires { get k mp = Some v }
843
ensures { 0.0 <=. A.real v <. abs (A.real m) }
844
= match get k p.poly with
845
| None -> absurd
846
| Some a -> mod_facts (A.real a) (A.real m) 0
847
end in
848
mod_facts (A.real p.cst) (A.real m) 0;
849
let lemma ev (env: Atom.t -> real) : unit
850
requires { forall k. has k (bindings p.poly) -> Real.is_integer (env k) }
851
ensures { Real.mod_e (eval env p) (A.real m) = Real.mod_e (eval env r) (A.real m) }
852
= let ghost n = pure { Real.div_e (A.real p.cst) (A.real m) + quot (A.real m) env (bindings p.poly) } in
853
assert { eval env p = eval env r +. A.real m *. from_int n };
854
mod_facts (eval env r) (A.real m) n;
855
if pure { bindings mp = Nil } then mod_facts (A.real r.cst) (A.real m) 0 in
856
r
857
Valid (142ms) (cvc5)
858
let ghost
neg_mul
(a b:real) : unit
859
ensures { (-. a) *. b = -. (b *. a) }
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)
864
let
reduce_node
(p:t) (y:Atom.t) : t
865
ensures { same_rem_node y p result }
866
ensures { bindings result.poly = Nil -> A.real result.cst = 0.0 ->
867
forall env d. d <> 0.0 -> abs d = abs (env y) -> Real.mod_e (eval env p) d = 0.0 }
868
= match PT.find_opt y p.poly with
869
| None ->
870
let lemma z (d:real) : unit
871
requires { d <> 0.0 }
872
ensures { Real.mod_e 0.0 d = 0.0 }
873
= mod_facts 0.0 d 0 in
874
p
875
| Some a ->
876
let one = A.of_int 1 in
877
let a' = A.mod_e a one in
878
let c = A.sub a' a in
879
mod_facts (A.real a) 1.0 0;
880
let ghost n = pure { Real.div_e (A.real a) 1.0 } in
881
assert { A.real c = -. from_int n };
882
let my = monome one y in
883
let r = x_p_cy p c my in
884
let lemma ev (env: Atom.t -> real) (d:real) : unit
885
requires { d <> 0.0 /\ abs d = abs (env y) }
886
ensures { Real.mod_e (eval env p) d = Real.mod_e (eval env r) d }
887
= assert { value r env = value p env +. A.real c *. value my env };
888
assert { value my env = env y };
889
assert { eval env r = eval env p +. A.real c *. env y };
890
neg_mul (from_int n) (env y);
891
assert { A.real c *. env y = -. (env y *. from_int n) };
892
assert { eval env p = eval env r +. env y *. from_int n };
893
if pure { d = env y } then mod_facts (eval env r) d n
894
else begin
895
assert { d = -. env y };
896
assert { eval env p = eval env r +. d *. from_int (- n) };
897
mod_facts (eval env r) d (- n)
898
end;
899
mod_facts 0.0 d 0 in
900
r
901
end
902
end