library colibrilib.generic_divrem_rewrite — module Genmodule Gen12use int.Int3use real.RealInfix4use real.Abs5use real.FromInt6use real.Truncate78function round (x:real) real : int910axiom round_increasing: Valid (18ms) (colibri2)11forall x y z. x <. y -> round x z <= round y z12Valid (19ms) (colibri2)13axiom round_zero: forall z. round 0. z = 01415axiom round_add_int: Valid (115ms) (cvc5)16forall x:real, n:int, z:real. round (x +. from_int n) z = round x z + n1718predicate in_bound (y r:real)1920function div (a:real) (b:real) : int = round (a /. b) b21function mod (a:real) (b:real) : real =22a -. b*.(from_int (div a b))23Valid (52ms) (cvc4) (split_vc) (depth 1)24axiom mod_in_bound: forall x y. y <> 0. -> in_bound y (mod x y)25Valid (196ms) (cvc4)26axiom in_bound_scale: forall x y k. k >. 0. -> y <> 0. -> in_bound y x -> in_bound (k *. y) (k *. x)27Valid (160ms) (cvc4)28axiom in_bound_bigger_scale: forall x y k. k >. 1. -> y <> 0. -> in_bound y x -> in_bound (k*.y) x29Valid (321ms) (cvc5)30axiom in_bound_scale2: forall x y k. 1. >. k >=. 0. -> y <> 0. -> in_bound y x -> in_bound y (k *. x)31Valid (31ms) (colibri2)32axiom in_bound_uniq: forall x y d r.33y <> 0. ->34in_bound y r ->35x = y*.(from_int d) +. r ->36d = div x y /\ r = mod x y37Valid (535ms) (cvc4)38axiom Scaling: forall y n r_y r_n.39y >. 0. -> n > 0 ->40in_bound y r_y ->41in_bound (from_int n) (from_int r_n) ->42in_bound (y *. from_int n) (((from_int r_n) *. y) +. r_y)434445function div_int (x y:int) : int = div (from_int x) (from_int y)46function mod_int (x y: int) : int = x - y*(div_int x y)47Valid (17ms) (colibri2)48let ghost mod_from_int (x y:int) : int49requires { y <> 0 }50ensures { mod (from_int x) (from_int y) = from_int result }51ensures { result = mod_int x y } =52mod_int x y53Valid (16ms) (colibri2)54let ghost divmod_uniq (x y r:real) (d:int) : unit55requires { y <> 0. }56requires { in_bound y r }57requires { x = y*.(from_int d) +. r }58ensures { r = mod x y }59ensures { d = div x y } =60in_bound_uniq x y d r61Valid (26ms) (colibri2 5) (split_vc) (depth 1)62let ghost divmod_uniq2 (x y r:real) (d:int) : unit63requires { y <> 0. }64requires { x = y*.(from_int d) +. r }65ensures { mod r y = mod x y }66ensures { d + div r y = div x y } =67divmod_uniq x y (mod r y) (d + div r y)68
The decomposition x = y * div x y + mod x y with the remainder in bound (mod_e_facts of colibrilib/qa.mlw for the Euclidean division)
Valid (15ms) (colibri2)
72 let ghost divmod_facts (x y:real) : unit
73 requires { y <> 0. }
74 ensures { in_bound y (mod x y) }
75 ensures { x = y *. from_int (div x y) +. mod x y } =
76 mod_in_bound x y
Two remainders in bound that differ by a multiple of y are equal (mod_e_unique of colibrilib/congruence.mlw)
Valid (20ms) (cvc5)
80 let ghost mod_unique (r r0 y:real) (n:int) : unit
81 requires { y <> 0. }
82 requires { in_bound y r }
83 requires { in_bound y r0 }
84 requires { r -. r0 = from_int n *. y }
85 ensures { r = r0 } =
86 divmod_uniq r0 y r (- n);
87 divmod_uniq r0 y r0 0
Two numbers that differ by a multiple of y have the same remainder (the members of a congruence class)
Valid (23ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
91 let ghost on_diff_period (x1 x2 y:real) (n:int) : unit
92 requires { y <> 0. }
93 requires { x1 -. x2 = from_int n *. y }
94 ensures { mod x1 y = mod x2 y }
95 ensures { div x1 y = div x2 y + n } =
96 divmod_uniq x1 y (mod x2 y) (div x2 y + n)
97
Valid (21ms) (colibri2)
98 let ghost on_mod (x y:real) : unit
99 requires { y <> 0. }
100 ensures { mod (mod x y) y = mod x y }
101 ensures { div (mod x y) y = 0 } =
102 divmod_uniq2 x y (mod x y) (div x y)
103
Valid (20ms) (colibri2)
104 let ghost on_add (x1 x2 y:real) : unit
105 requires { y <> 0. }
106 ensures { (mod (x1+.x2) y) = mod (mod x1 y +. mod x2 y) y }
107 ensures { (div (x1+.x2) y) = div x1 y + div x2 y + div (mod x1 y +. mod x2 y) y} =
108 divmod_uniq2 (x1+.x2) y (mod x1 y+.mod x2 y) (div x1 y+div x2 y)
if y not integer y= 0.5 x1,x2=0.8 –> 0.8 0.8 = 0.64 –> 0.14 & 0.3 0.3 = 0.09 –> 0.09
(* 8 * 8 = 64 - > 4 -> 3 * 3 = 9 -> 4 *) Valid (68ms) (colibri2 7) (cvc5) (split_vc) (depth 1)111let ghost on_mul (x1 x2:real) (r1 r2:int) (y:int) : unit112requires { y <> 0 }113requires { from_int r1 = mod x1 (from_int y) }114requires { from_int r2 = mod x2 (from_int y) }115ensures { (mod (x1*.x2) (from_int y)) = mod (mod x1 (from_int y) *. mod x2 (from_int y)) (from_int y) } =116ensures { div (x1*.x2) (from_int y) =117(y * div x1 (from_int y) * div x2 (from_int y)118+ div x1 (from_int y) * r2119+ div x2 (from_int y) * r1120+ div (mod x1 (from_int y) *. mod x2 (from_int y)) (from_int y)121)122}123let yy = from_int y in124let q1 = div x1 yy in125let q2 = div x2 yy in126let m1 = mod x1 yy in127let m2 = mod x2 yy in128assert { x1 = yy *. from_int q1 +. m1 };129assert { x2 = yy *. from_int q2 +. m2 };130assert { x1 *. x2 = yy *. (yy *. from_int q1 *. from_int q2 +. from_int q1 *. m2131+. from_int q2 *. m1) +. m1 *. m2 };132assert { from_int (y * q1 * q2 + q1 * r2 + q2 * r1)133= yy *. from_int q1 *. from_int q2 +. from_int q1 *. m2 +. from_int q2 *. m1 };134divmod_uniq2 (x1*.x2) (from_int y)135(mod x1 (from_int y) *. mod x2 (from_int y))136(y * div x1 (from_int y) * div x2 (from_int y)137+ div x1 (from_int y) * r2138+ div x2 (from_int y) * r1139)140141Valid (20ms) (colibri2)142let ghost on_mul_x_int (x1 :int) (x2:real) (y:real) : unit143requires { y <> 0. }144ensures { (mod (from_int x1*.x2) y) = mod (from_int x1 *. mod x2 y) y }145ensures { (div (from_int x1*.x2) y) = x1 * div x2 y + div (from_int x1 *. mod x2 y) y }146=147divmod_uniq2 (from_int x1*.x2) y148(from_int x1 *. mod x2 y)149(x1 * div x2 y)150Valid (54ms) (colibri2 12) (split_vc) (depth 1)151let ghost on_mul_int (x1 x2:int) (y:int) : unit152requires { y <> 0 }153ensures { (mod_int (x1*x2) y) = mod_int ((mod_int x1 y) * (mod_int x2 y)) y } =154ensures { div_int (x1*x2) y =155(y * div_int x1 y * div_int x2 y156+ div_int x1 y * (mod_int x2 y)157+ div_int x2 y * (mod_int x1 y)158+ div_int (mod_int x1 y * mod_int x2 y) y159)160}161let r1 = mod_from_int x1 y in162let r2 = mod_from_int x2 y in163on_mul (from_int x1) (from_int x2) r1 r2 y;164let _ = mod_from_int (x1*x2) y in165let _ = mod_from_int (r1*r2) y in166assert { from_int x1 *. from_int x2 = from_int (x1*x2) };167assert { from_int r1 *. from_int r2 = from_int (r1*r2) };168assert { from_int (mod_int (x1*x2) y) = from_int (mod_int (r1*r2) y) }169Valid (27ms) (colibri2 5) (split_vc) (depth 1)170let ghost on_add_period (x y:real) (n:int) : unit171requires { y <> 0. }172ensures { (mod (x+.y*.(from_int n)) y) = mod x y }173ensures { (div (x+.y*.(from_int n)) y) = div x y + n } =174divmod_uniq (x+.y*.(from_int n)) y (mod x y) (div x y + n)175Valid (25ms) (colibri2 5) (split_vc) (depth 1)176let ghost on_scale (x y:real) (k:real) : unit177requires { y <> 0. }178requires { k >. 0. }179ensures { (mod (k*.x) (k*.y)) = k*.(mod x y) }180ensures { (div (k*.x) (k*.y)) = (div x y) } =181divmod_uniq (k*.x) (k*.y) (k*.(mod x y)) (div x y)182Valid (23ms) (colibri2)183let ghost on_x_mul_to_y (x y:real) (k:real) : unit184requires { y <> 0. }185requires { k >. 0. }186ensures { (mod (k*.x) y) = k*.(mod x (y/.k)) }187ensures { (div (k*.x) y) = (div x (y/.k)) } =188on_scale x (y/.k) k189Valid (53ms) (colibri2)190let ghost on_neg (x y:real) : unit191requires { y <> 0. }192ensures { (mod (-.x) y) = mod (-. (mod x y)) y }193ensures { (div (-.x) y) = - div x y + div (-. (mod x y)) y } =194divmod_uniq2 (-.x) y (-.(mod x y)) (-div x y)195Valid (26ms) (colibri2)196let ghost on_sub (x1 x2 y:real) : unit197requires { y <> 0. }198ensures { (mod (x1-.x2) y) = mod (mod x1 y -. mod x2 y) y }199ensures { (div (x1-.x2) y) = div x1 y - div x2 y + div (mod x1 y -. mod x2 y) y} =200divmod_uniq2 (x1-.x2) y (mod x1 y-.mod x2 y) (div x1 y-div x2 y)201Valid (28ms) (colibri2)202let ghost on_y_scale (x y:real) (n:int) : unit203requires { y <> 0. }204requires { n > 0 }205ensures { mod (mod x ((from_int n) *. y)) y = mod x y } =206let yn = (from_int n) *. y in207divmod_uniq2 x y (mod x yn) (div x yn * n)208Valid (23ms) (colibri2)209let ghost when_in_bound (x y:real) : unit210requires { y <> 0. }211requires { in_bound y x }212ensures { (mod x y) = x }213ensures { (div x y) = 0 } =214divmod_uniq x y x 0215Valid (26ms) (colibri2 7) (split_vc) (depth 1)216let ghost on_out_mod (x y z:real) : unit217requires { y <> 0. }218requires { z >. 1. }219ensures { mod (mod x y) (z*.y) = mod x y }220ensures { div (mod x y) (z*.y) = 0 } =221in_bound_bigger_scale (mod x y) y z;222when_in_bound (mod x y) (z*.y)223Valid (367ms) (colibri2)224let ghost on_same (x:real) : unit225requires { x <> 0. }226requires { in_bound x x }227ensures { (mod x x) = 0. }228ensures { (div x x) = 1 } =229divmod_uniq x x 0. 1230Valid (27ms) (colibri2)231let ghost on_zero (y:real) : unit232requires { y <> 0. }233ensures { (mod 0. y) = 0. }234ensures { (div 0. y) = 0 } =235divmod_uniq 0. y 0. 0236237Valid (16ms) (colibri2)238let ghost on_eq_mod (x1 x2 y1 y2:real) : unit239requires { (mod x1 y1) = (mod x2 y2) }240ensures { x1 = x2 -. y2*.from_int (div x2 y2) +. y1*.from_int (div x1 y1) } =241()242Valid (25ms) (colibri2)243let ghost on_eq_div (x1 x2 y:real) : unit244requires { y <> 0. }245requires { (div x1 y) = (div x2 y) }246ensures { x1 = x2 +. mod x1 y -. mod x2 y } =247()248253(* let ghost function mod_radix_split (x y z:real) : unit requires { y >. 0. /\ z >. 0. } ensures { mod x (y *. z) = y *. (from_int (mod_int (div x y) (round z))) +. (mod x y) } *)254Valid (39ms) (colibri2 9) (split_vc) (depth 1)255let ghost mod_split (x y:real) (n:int) : unit256requires { y >. 0. }257requires { n > 0 }258ensures { mod x (y *. from_int n) =259y *. (mod (from_int (div x y)) (from_int n)) +. (mod x y) }260=261let yn = y *. from_int n in262let qy = div x y in263let ry = mod x y in264let qn = div (from_int qy) (from_int n) in265let rn = mod (from_int qy) (from_int n) in266mod_in_bound x y;267mod_in_bound (from_int qy) (from_int n);268let rni = mod_from_int qy n in269assert { in_bound (from_int n) (from_int rni) };270assert { in_bound yn (from_int rni *. y +. ry) };271divmod_uniq x yn (rn *. y +. ry) qn272Valid (29ms) (colibri2 7) (split_vc) (depth 1)273let ghost mod_mod_divisible (x y:real) (i:int) : unit274requires { i > 0 }275requires { y >. 0. }276ensures { mod (mod x ((from_int i)*.y)) y = mod x y } =277let d = mod_from_int (div x y) i in278mod_split x y i;279divmod_uniq (mod x ((from_int i)*.y)) y (mod x y) d280Valid (34ms) (colibri2)281let ghost div_mod_divisible (x y:real) (i:int) : int282requires { i > 0 }283requires { y >. 0. }284ensures { (mod (from_int (div x y)) (from_int i)) = from_int result }285ensures { (div (mod x ((from_int i)*.y)) y) = result } =286let mdi = mod_from_int (div x y) i in287mod_split x y i;288on_add_period (mod x y) y mdi;289on_mod x y;290mdi291Valid (24ms) (colibri2)292let ghost div_split (x y:real) (n:int) : unit293requires { y >. 0. /\ n > 0 }294ensures { div x (y *. from_int n) = div (from_int (div x y)) (from_int n) } =295mod_split x y n296297end298