Common — library colibrilib.generic_divrem_rewrite — module Gen
1
module Gen
2
3
use int.Int
4
use real.RealInfix
5
use real.Abs
6
use real.FromInt
7
use real.Truncate
8
9
function
round
(x:real) real : int
10
11
axiom
round_increasing
: Valid (18ms) (colibri2)
12
forall x y z. x <. y -> round x z <= round y z
13
Valid (19ms) (colibri2)
14
axiom
round_zero
: forall z. round 0. z = 0
15
16
axiom
round_add_int
: Valid (115ms) (cvc5)
17
forall x:real, n:int, z:real. round (x +. from_int n) z = round x z + n
18
19
predicate
in_bound
(y r:real)
20
21
function
div
(a:real) (b:real) : int = round (a /. b) b
22
function
mod
(a:real) (b:real) : real =
23
a -. b*.(from_int (div a b))
24
Valid (52ms) (cvc4) (split_vc) (depth 1)
25
axiom
mod_in_bound
: forall x y. y <> 0. -> in_bound y (mod x y)
26
Valid (196ms) (cvc4)
27
axiom
in_bound_scale
: forall x y k. k >. 0. -> y <> 0. -> in_bound y x -> in_bound (k *. y) (k *. x)
28
Valid (160ms) (cvc4)
29
axiom
in_bound_bigger_scale
: forall x y k. k >. 1. -> y <> 0. -> in_bound y x -> in_bound (k*.y) x
30
Valid (321ms) (cvc5)
31
axiom
in_bound_scale2
: forall x y k. 1. >. k >=. 0. -> y <> 0. -> in_bound y x -> in_bound y (k *. x)
32
Valid (31ms) (colibri2)
33
axiom
in_bound_uniq
: forall x y d r.
34
y <> 0. ->
35
in_bound y r ->
36
x = y*.(from_int d) +. r ->
37
d = div x y /\ r = mod x y
38
Valid (535ms) (cvc4)
39
axiom
Scaling
: forall y n r_y r_n.
40
y >. 0. -> n > 0 ->
41
in_bound y r_y ->
42
in_bound (from_int n) (from_int r_n) ->
43
in_bound (y *. from_int n) (((from_int r_n) *. y) +. r_y)
44
45
46
function
div_int
(x y:int) : int = div (from_int x) (from_int y)
47
function
mod_int
(x y: int) : int = x - y*(div_int x y)
48
Valid (17ms) (colibri2)
49
let ghost
mod_from_int
(x y:int) : int
50
requires { y <> 0 }
51
ensures { mod (from_int x) (from_int y) = from_int result }
52
ensures { result = mod_int x y } =
53
mod_int x y
54
Valid (16ms) (colibri2)
55
let ghost
divmod_uniq
(x y r:real) (d:int) : unit
56
requires { y <> 0. }
57
requires { in_bound y r }
58
requires { x = y*.(from_int d) +. r }
59
ensures { r = mod x y }
60
ensures { d = div x y } =
61
in_bound_uniq x y d r
62
Valid (26ms) (colibri2 5) (split_vc) (depth 1)
63
let ghost
divmod_uniq2
(x y r:real) (d:int) : unit
64
requires { y <> 0. }
65
requires { x = y*.(from_int d) +. r }
66
ensures { mod r y = mod x y }
67
ensures { d + div r y = div x y } =
68
divmod_uniq x y (mod r y) (d + div r y)

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

111
(* 8 * 8 = 64 - > 4 -> 3 * 3 = 9 -> 4 *) Valid (68ms) (colibri2 7) (cvc5) (split_vc) (depth 1)
112
let ghost
on_mul
(x1 x2:real) (r1 r2:int) (y:int) : unit
113
requires { y <> 0 }
114
requires { from_int r1 = mod x1 (from_int y) }
115
requires { from_int r2 = mod x2 (from_int y) }
116
ensures { (mod (x1*.x2) (from_int y)) = mod (mod x1 (from_int y) *. mod x2 (from_int y)) (from_int y) } =
117
ensures { div (x1*.x2) (from_int y) =
118
(y * div x1 (from_int y) * div x2 (from_int y)
119
+ div x1 (from_int y) * r2
120
+ div x2 (from_int y) * r1
121
+ div (mod x1 (from_int y) *. mod x2 (from_int y)) (from_int y)
122
)
123
}
124
let yy = from_int y in
125
let q1 = div x1 yy in
126
let q2 = div x2 yy in
127
let m1 = mod x1 yy in
128
let m2 = mod x2 yy in
129
assert { x1 = yy *. from_int q1 +. m1 };
130
assert { x2 = yy *. from_int q2 +. m2 };
131
assert { x1 *. x2 = yy *. (yy *. from_int q1 *. from_int q2 +. from_int q1 *. m2
132
+. from_int q2 *. m1) +. m1 *. m2 };
133
assert { from_int (y * q1 * q2 + q1 * r2 + q2 * r1)
134
= yy *. from_int q1 *. from_int q2 +. from_int q1 *. m2 +. from_int q2 *. m1 };
135
divmod_uniq2 (x1*.x2) (from_int y)
136
(mod x1 (from_int y) *. mod x2 (from_int y))
137
(y * div x1 (from_int y) * div x2 (from_int y)
138
+ div x1 (from_int y) * r2
139
+ div x2 (from_int y) * r1
140
)
141
142
Valid (20ms) (colibri2)
143
let ghost
on_mul_x_int
(x1 :int) (x2:real) (y:real) : unit
144
requires { y <> 0. }
145
ensures { (mod (from_int x1*.x2) y) = mod (from_int x1 *. mod x2 y) y }
146
ensures { (div (from_int x1*.x2) y) = x1 * div x2 y + div (from_int x1 *. mod x2 y) y }
147
=
148
divmod_uniq2 (from_int x1*.x2) y
149
(from_int x1 *. mod x2 y)
150
(x1 * div x2 y)
151
Valid (54ms) (colibri2 12) (split_vc) (depth 1)
152
let ghost
on_mul_int
(x1 x2:int) (y:int) : unit
153
requires { y <> 0 }
154
ensures { (mod_int (x1*x2) y) = mod_int ((mod_int x1 y) * (mod_int x2 y)) y } =
155
ensures { div_int (x1*x2) y =
156
(y * div_int x1 y * div_int x2 y
157
+ div_int x1 y * (mod_int x2 y)
158
+ div_int x2 y * (mod_int x1 y)
159
+ div_int (mod_int x1 y * mod_int x2 y) y
160
)
161
}
162
let r1 = mod_from_int x1 y in
163
let r2 = mod_from_int x2 y in
164
on_mul (from_int x1) (from_int x2) r1 r2 y;
165
let _ = mod_from_int (x1*x2) y in
166
let _ = mod_from_int (r1*r2) y in
167
assert { from_int x1 *. from_int x2 = from_int (x1*x2) };
168
assert { from_int r1 *. from_int r2 = from_int (r1*r2) };
169
assert { from_int (mod_int (x1*x2) y) = from_int (mod_int (r1*r2) y) }
170
Valid (27ms) (colibri2 5) (split_vc) (depth 1)
171
let ghost
on_add_period
(x y:real) (n:int) : unit
172
requires { y <> 0. }
173
ensures { (mod (x+.y*.(from_int n)) y) = mod x y }
174
ensures { (div (x+.y*.(from_int n)) y) = div x y + n } =
175
divmod_uniq (x+.y*.(from_int n)) y (mod x y) (div x y + n)
176
Valid (25ms) (colibri2 5) (split_vc) (depth 1)
177
let ghost
on_scale
(x y:real) (k:real) : unit
178
requires { y <> 0. }
179
requires { k >. 0. }
180
ensures { (mod (k*.x) (k*.y)) = k*.(mod x y) }
181
ensures { (div (k*.x) (k*.y)) = (div x y) } =
182
divmod_uniq (k*.x) (k*.y) (k*.(mod x y)) (div x y)
183
Valid (23ms) (colibri2)
184
let ghost
on_x_mul_to_y
(x y:real) (k:real) : unit
185
requires { y <> 0. }
186
requires { k >. 0. }
187
ensures { (mod (k*.x) y) = k*.(mod x (y/.k)) }
188
ensures { (div (k*.x) y) = (div x (y/.k)) } =
189
on_scale x (y/.k) k
190
Valid (53ms) (colibri2)
191
let ghost
on_neg
(x y:real) : unit
192
requires { y <> 0. }
193
ensures { (mod (-.x) y) = mod (-. (mod x y)) y }
194
ensures { (div (-.x) y) = - div x y + div (-. (mod x y)) y } =
195
divmod_uniq2 (-.x) y (-.(mod x y)) (-div x y)
196
Valid (26ms) (colibri2)
197
let ghost
on_sub
(x1 x2 y:real) : unit
198
requires { y <> 0. }
199
ensures { (mod (x1-.x2) y) = mod (mod x1 y -. mod x2 y) y }
200
ensures { (div (x1-.x2) y) = div x1 y - div x2 y + div (mod x1 y -. mod x2 y) y} =
201
divmod_uniq2 (x1-.x2) y (mod x1 y-.mod x2 y) (div x1 y-div x2 y)
202
Valid (28ms) (colibri2)
203
let ghost
on_y_scale
(x y:real) (n:int) : unit
204
requires { y <> 0. }
205
requires { n > 0 }
206
ensures { mod (mod x ((from_int n) *. y)) y = mod x y } =
207
let yn = (from_int n) *. y in
208
divmod_uniq2 x y (mod x yn) (div x yn * n)
209
Valid (23ms) (colibri2)
210
let ghost
when_in_bound
(x y:real) : unit
211
requires { y <> 0. }
212
requires { in_bound y x }
213
ensures { (mod x y) = x }
214
ensures { (div x y) = 0 } =
215
divmod_uniq x y x 0
216
Valid (26ms) (colibri2 7) (split_vc) (depth 1)
217
let ghost
on_out_mod
(x y z:real) : unit
218
requires { y <> 0. }
219
requires { z >. 1. }
220
ensures { mod (mod x y) (z*.y) = mod x y }
221
ensures { div (mod x y) (z*.y) = 0 } =
222
in_bound_bigger_scale (mod x y) y z;
223
when_in_bound (mod x y) (z*.y)
224
Valid (367ms) (colibri2)
225
let ghost
on_same
(x:real) : unit
226
requires { x <> 0. }
227
requires { in_bound x x }
228
ensures { (mod x x) = 0. }
229
ensures { (div x x) = 1 } =
230
divmod_uniq x x 0. 1
231
Valid (27ms) (colibri2)
232
let ghost
on_zero
(y:real) : unit
233
requires { y <> 0. }
234
ensures { (mod 0. y) = 0. }
235
ensures { (div 0. y) = 0 } =
236
divmod_uniq 0. y 0. 0
237
238
Valid (16ms) (colibri2)
239
let ghost
on_eq_mod
(x1 x2 y1 y2:real) : unit
240
requires { (mod x1 y1) = (mod x2 y2) }
241
ensures { x1 = x2 -. y2*.from_int (div x2 y2) +. y1*.from_int (div x1 y1) } =
242
()
243
Valid (25ms) (colibri2)
244
let ghost
on_eq_div
(x1 x2 y:real) : unit
245
requires { y <> 0. }
246
requires { (div x1 y) = (div x2 y) }
247
ensures { x1 = x2 +. mod x1 y -. mod x2 y } =
248
()
253
254
(* 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) } *)
255
Valid (39ms) (colibri2 9) (split_vc) (depth 1)
256
let ghost
mod_split
(x y:real) (n:int) : unit
257
requires { y >. 0. }
258
requires { n > 0 }
259
ensures { mod x (y *. from_int n) =
260
y *. (mod (from_int (div x y)) (from_int n)) +. (mod x y) }
261
=
262
let yn = y *. from_int n in
263
let qy = div x y in
264
let ry = mod x y in
265
let qn = div (from_int qy) (from_int n) in
266
let rn = mod (from_int qy) (from_int n) in
267
mod_in_bound x y;
268
mod_in_bound (from_int qy) (from_int n);
269
let rni = mod_from_int qy n in
270
assert { in_bound (from_int n) (from_int rni) };
271
assert { in_bound yn (from_int rni *. y +. ry) };
272
divmod_uniq x yn (rn *. y +. ry) qn
273
Valid (29ms) (colibri2 7) (split_vc) (depth 1)
274
let ghost
mod_mod_divisible
(x y:real) (i:int) : unit
275
requires { i > 0 }
276
requires { y >. 0. }
277
ensures { mod (mod x ((from_int i)*.y)) y = mod x y } =
278
let d = mod_from_int (div x y) i in
279
mod_split x y i;
280
divmod_uniq (mod x ((from_int i)*.y)) y (mod x y) d
281
Valid (34ms) (colibri2)
282
let ghost
div_mod_divisible
(x y:real) (i:int) : int
283
requires { i > 0 }
284
requires { y >. 0. }
285
ensures { (mod (from_int (div x y)) (from_int i)) = from_int result }
286
ensures { (div (mod x ((from_int i)*.y)) y) = result } =
287
let mdi = mod_from_int (div x y) i in
288
mod_split x y i;
289
on_add_period (mod x y) y mdi;
290
on_mod x y;
291
mdi
292
Valid (24ms) (colibri2)
293
let ghost
div_split
(x y:real) (n:int) : unit
294
requires { y >. 0. /\ n > 0 }
295
ensures { div x (y *. from_int n) = div (from_int (div x y)) (from_int n) } =
296
mod_split x y n
297
298
end