Common — library colibrilib.modulo — module Divisible
1
module Divisible
2
3
use bool.Bool
4
use colibrilib.q.Z as Z
5
use colibrilib.q.Q as Q
6
use int.Int
7
use real.RealInfix
8
use real.Truncate
9
use real.FromInt
10
11
exception
FinitePositiveExpected
12
Valid (128ms) (cvc4)
13
let lemma
round_modulo
(a:real) (m:real): unit
14
requires { 0. <. m }
15
ensures { 0. <=. a -. from_int (floor (a /. m )) *. m <. m }
16
ensures { let r = from_int (floor (a /. m )) *. m in
17
r <. a -> forall q. not (r <. (from_int q) *. m <=. a) }
18
=
19
let d = a /. m in
20
let t = floor d in
21
let f = from_int t in
22
assert { f <=. d <. from_int (t + 1) }
23
24
predicate
ddivisible_using
(a b:real) (d:int) =
25
a = (from_int d) *. b
26
27
predicate
ddivisible
(a b: real) =
28
exists d. ddivisible_using a b d
29
Valid (57ms) (colibri2)
30
let
round_down_to
(a:Q.t) (m:Q.t) : (r:Q.t,ghost q':int)
31
requires { (0. <. Q.real m ) }
32
ensures { ddivisible_using r m q' }
33
ensures { Q.( r <= a) }
34
ensures { Q.(0. <=. (a.real -. r.real) <. m.real) }
35
ensures { Q.( r.real <. a.real) -> forall q. not Q.(r.real <. (from_int q) *. m.real <=. a.real ) }
36
=
37
if Q.(a = (Q.of_int 0)) then a,0
38
else begin
39
round_modulo pure { a.Q.real } pure { m.Q.real };

it is surely possible to improve this computation

41
let q' = Q.(floor (a / m)) in
42
let r = Q.(of_int q' * m) in
43
r, q'
44
end
45
Valid (3.7s) (colibri2 3) (cvc5 2) (split_vc 2) (depth 2)
46
let
round_up_to
(a:Q.t) (m:Q.t) : (r:Q.t,ghost q':int)
47
requires { 0. <. Q.real m }
48
ensures { ddivisible_using r m q' }
49
ensures { Q.(a <= r) }
50
ensures { Q.(0. <=. (r.real -. a.real) <. m.real) }
51
ensures { Q.( a.real <. r.real) -> forall q. not Q.(a.real <=. (from_int q) *. m.real <. r.real ) }
52
=
53
let res,q' = round_down_to Q.((of_int 0) - a) m in
54
Q.((of_int 0) - res),(-q')
55
Valid (23ms) (colibri2)
56
let lemma
simple_mul_div
(a b : real)
57
requires { b <> 0. }
58
ensures { (a /. b) *. b = a } =
59
()
60
Valid (24ms) (colibri2)
61
let lemma
remove_product_right
(a b c:int) : unit
62
requires { b <> 0 }
63
requires { a * b = c * b }
64
ensures { a = c } =
65
()
66
Valid (43ms) (colibri2)
67
let lemma
divisible_to_z
(a b:Q.t) (d:int) : (dnum:int, dden: int)
68
requires { b.Q.real <> 0. }
69
requires { ddivisible_using a.Q.real b.Q.real d }
70
ensures { Z.ddivisible_using a.Q.num b.Q.num dnum }
71
ensures { Z.ddivisible_using b.Q.den a.Q.den dden }
72
ensures { d = dnum * dden } =
73
assert { b.Q.den * a.Q.num = d * b.Q.num * a.Q.den
74
by from_int b.Q.den *. from_int a.Q.num = from_int d *. from_int b.Q.num *. from_int a.Q.den
75
by (from_int a.Q.num /. from_int a.Q.den) *. from_int a.Q.den *. from_int b.Q.den = (from_int d *. (from_int b.Q.num /. from_int b.Q.den)) *. from_int a.Q.den *. from_int b.Q.den
76
by from_int a.Q.num /. from_int a.Q.den = from_int d *. (from_int b.Q.num /. from_int b.Q.den)
77
};
78
let dnum = Z.prime_to_one_another_mul b.Q.num (d * a.Q.den) b.Q.den a.Q.num in
79
assert { Z.ddivisible_using a.Q.num b.Q.num dnum };
80
let dden = Z.prime_to_one_another_mul a.Q.num b.Q.den a.Q.den (d * b.Q.num) in
81
assert { Z.ddivisible_using b.Q.den a.Q.den dden };
82
assert { dnum * dden * b.Q.num * a.Q.den = d * b.Q.num * a.Q.den };
83
remove_product_right (dnum * dden * b.Q.num) a.Q.den (d * b.Q.num);
84
remove_product_right (dnum * dden) b.Q.num d;
85
(dnum,dden)
86
Valid (43ms) (colibri2)
87
let lemma
divisible_from_z
(a b:Q.t) (dnum:int) (dden:int) : unit
88
requires { Z.ddivisible_using a.Q.num b.Q.num dnum }
89
requires { Z.ddivisible_using b.Q.den a.Q.den dden }
90
ensures { ddivisible_using a.Q.real b.Q.real (dnum*dden) }
91
=
92
ghost (simple_mul_div (from_int a.Q.num) (from_int a.Q.den);
93
simple_mul_div (from_int b.Q.num) (from_int b.Q.den););
94
let ghost d = dnum * dden in
95
assert { a.Q.real = (from_int d) *. b.Q.real
96
by from_int a.Q.num /. from_int a.Q.den = from_int d *. (from_int b.Q.num /. from_int b.Q.den)
97
by (from_int a.Q.num /. from_int a.Q.den) *. (from_int b.Q.den /. from_int b.Q.den) = from_int d *. (from_int b.Q.num /. from_int b.Q.den) *. (from_int a.Q.den /. from_int a.Q.den)
98
by (from_int a.Q.num *. from_int b.Q.den) /. from_int a.Q.den /. from_int b.Q.den = (from_int d *. from_int b.Q.num *. from_int a.Q.den) /. from_int a.Q.den /. from_int b.Q.den
99
by from_int a.Q.num *. from_int b.Q.den = from_int d *. from_int b.Q.num *. from_int a.Q.den
100
by from_int a.Q.num *. from_int b.Q.den = from_int dnum *. from_int dden *. from_int b.Q.num *. from_int a.Q.den
101
by from_int a.Q.num *. from_int b.Q.den = from_int (dnum * b.Q.num) *. from_int (dden * a.Q.den)
102
}
103
Valid (115ms) (cvc4)
104
let
divisible
(a:Q.t) (b:Q.t) : (r:bool,ghost d: int)
105
ensures { not r -> forall d. not (ddivisible_using a.Q.real b.Q.real d) }
106
ensures { r -> ddivisible_using a.Q.real b.Q.real d } =
107
if Int.(=) b.Q.num 0 then
108
(Int.(=) a.Q.num 0, ghost 0)
109
else
110
let b1,dnum = Z.divisible a.Q.num b.Q.num in
111
if b1 then
112
let b2,dden = Z.divisible b.Q.den a.Q.den in
113
if b2 then
114
(true,dnum*dden)
115
else begin
116
let ghost () = if pure { exists d. ddivisible_using a.Q.real b.Q.real d } then
117
let d = any (d:int) ensures { ddivisible_using a.Q.real b.Q.real d } in
118
let _dnum, dden = divisible_to_z a b d in
119
assert { Z.ddivisible_using a.Q.den b.Q.den dden };
120
absurd
121
in
122
(false,ghost 0)
123
end
124
else begin
125
let ghost () = if pure { exists d. ddivisible_using a.Q.real b.Q.real d } then
126
let d = any (d:int) ensures { ddivisible_using a.Q.real b.Q.real d } in
127
let dnum, _dden = divisible_to_z a b d in
128
assert { Z.ddivisible_using a.Q.num b.Q.num dnum };
129
absurd
130
in
131
(false,ghost 0)
132
end
133
Valid (351ms) (colibri2)
134
let
mult_cst_divisible
(a:Q.t) (q:Q.t) : (a':Q.t)
135
ensures { forall r. ddivisible r a.Q.real -> ddivisible (r *. q.Q.real ) a'.Q.real } =
136
let a' = Q.(a*q) in
137
let lemma post (r:real) : unit
138
requires { ddivisible r a.Q.real }
139
ensures { ddivisible (r *. q.Q.real) a'.Q.real } =
140
let d = any int ensures { ddivisible_using r a.Q.real result } in
141
assert {ddivisible_using (r *. q.Q.real) a'.Q.real d }
142
in
143
a'
144
145
end