Common — library colibrilib.dv — module Dv

Integer multiples of a real

9
module Dv
10
use int.Int
11
use real.RealInfix
12
use real.FromInt
13
use real.Abs
14
use real.Truncate

dv a b: a is an integer multiple of b (b divides a). Zero is the only multiple of zero.

18
predicate
dv
(a b:real) = exists k:int. a = from_int k *. b

The integer k such that a is k times b. It replaces a skolemization of dv.

  Valid (15ms) (colibri2)
22
let ghost
quot
(a b:real) : int
23
requires { dv a b }
24
ensures { a = from_int result *. b }
25
= any int ensures { a = from_int result *. b }

The introduction of dv with its multiple

  Valid (17ms) (colibri2)
28
let ghost
dv_intro
(a b:real) (k:int) : unit
29
requires { a = from_int k *. b }
30
ensures { dv a b }
31
= ()
32
Valid (16ms) (colibri2)
33
let ghost
dv_zero
(b:real) : unit
34
ensures { dv 0.0 b }
35
= assert { 0.0 = from_int 0 *. b }
36
Valid (15ms) (colibri2)
37
let ghost
dv_self
(b:real) : unit
38
ensures { dv b b }
39
= assert { b = from_int 1 *. b }
40
Valid (22ms) (colibri2 4) (split_vc) (depth 1)
41
let ghost
dv_add
(a b c:real) : unit
42
requires { dv a c }
43
requires { dv b c }
44
ensures { dv (a +. b) c }
45
= {proof…} let k = quot a c in
46
let l = quot b c in
47
assert { a +. b = from_int (k + l) *. c } {qed}
48
Valid (21ms) (colibri2 4) (split_vc) (depth 1)
49
let ghost
dv_sub
(a b c:real) : unit
50
requires { dv a c }
51
requires { dv b c }
52
ensures { dv (a -. b) c }
53
= {proof…} let k = quot a c in
54
let l = quot b c in
55
assert { a -. b = from_int (k - l) *. c } {qed}
56
Valid (79ms) (colibri2 3) (cvc5) (split_vc) (depth 1)
57
let ghost
dv_neg
(a c:real) : unit
58
requires { dv a c }
59
ensures { dv (-. a) c }
60
= {proof…} let k = quot a c in
61
assert { from_int (- k) = -. from_int k };
62
assert { -. a = from_int (- k) *. c } {qed}
63
Valid (21ms) (colibri2 6) (split_vc) (depth 1)
64
let ghost
dv_trans
(a b c:real) : unit
65
requires { dv a b }
66
requires { dv b c }
67
ensures { dv a c }
68
= {proof…} let k = quot a b in
69
let l = quot b c in
70
assert { from_int (k * l) = from_int k *. from_int l };
71
assert { a = from_int k *. (from_int l *. c) };
72
assert { a = from_int (k * l) *. c } {qed}

Multiples of zero

  Valid (23ms) (colibri2)
75
let ghost
dv_zero_iff
(a:real) : unit
76
ensures { dv a 0.0 <-> a = 0.0 }
77
= ()

k * c is a multiple of c

  Valid (15ms) (colibri2)
80
let ghost
dv_mul_int
(k:int) (c:real) : unit
81
ensures { dv (from_int k *. c) c }
82
= assert { from_int k *. c = from_int k *. c }

A multiple of a multiple of c

  Valid (22ms) (colibri2 5) (split_vc) (depth 1)
85
let ghost
dv_mul
(a c:real) (i:int) : unit
86
requires { dv a c }
87
ensures { dv (from_int i *. a) c }
88
= {proof…} let k = quot a c in
89
assert { from_int (i * k) = from_int i *. from_int k };
90
assert { from_int i *. a = from_int i *. (from_int k *. c) };
91
assert { from_int i *. a = from_int (i * k) *. c } {qed}

The sign of the divisor does not matter

  Valid (64ms) (colibri2 6) (cvc5 2) (split_vc 4) (depth 3)
94
let ghost
dv_abs
(a c:real) : unit
95
ensures { dv a (abs c) <-> dv a c }
96
= {proof…} if c >=. 0.0 then ()
97
else begin
98
if pure { dv a c } then begin
99
let k = quot a c in
100
assert { a = from_int (- k) *. abs c }
101
end;
102
if pure { dv a (abs c) } then begin
103
let k = quot a (abs c) in
104
assert { a = from_int (- k) *. c }
105
end
106
end {qed}

Adding a multiple of c does not change the divisibility by c

  Valid (21ms) (colibri2)
109
let ghost
dv_shift
(a b c:real) : unit
110
requires { dv b c }
111
ensures { dv a c <-> dv (a -. b) c }
112
= {proof…} if pure { dv a c } then dv_sub a b c;
113
if pure { dv (a -. b) c } then dv_add (a -. b) b c {qed}

An integer k with k * g = 1 and g non negative: g is 1

  Valid (18ms) (colibri2)
116
let ghost
unit_int
(k g:int) : unit
117
requires { 0 <= g }
118
requires { k * g = 1 }
119
ensures { g = 1 }
120
= {proof…} if k > 0 then assert { k * g >= g }
121
else if k < 0 then assert { k * g <= 0 } {qed}

Two non negative numbers that divide each other are equal

  Valid (32ms) (colibri2)
124
let ghost
dv_antisym
(x y:real) : unit
125
requires { 0.0 <=. x /\ 0.0 <=. y }
126
requires { dv x y /\ dv y x }
127
ensures { x = y }
128
= {proof…} let k = quot x y in
129
let l = quot y x in
130
if x >. 0.0 then begin
131
assert { from_int (k * l) = from_int k *. from_int l };
132
assert { x = from_int k *. (from_int l *. x) };
133
assert { (from_int (k * l) -. 1.0) *. x = 0.0 };
134
assert { from_int (k * l) = from_int 1 };
135
assert { k * l = 1 };
136
(* `k` and `l` are 1 or both -1; -1 gives a negative `x` *)
137
if k > 0 then unit_int l k
138
else begin
139
unit_int (- l) (- k);
140
assert { x = -. y }
141
end
142
end {qed}

Moving a representative by a multiple of |d| is moving it by a multiple of d

  Valid (121ms) (colibri2 5) (cvc5) (split_vc) (depth 1)
146
let ghost
abs_shift
(a r d:real) (k:int) : unit
147
requires { r = a -. from_int k *. abs d }
148
ensures { exists k':int. r = a +. from_int k' *. d }
149
= {proof…} if d >=. 0.0 then begin
150
assert { abs d = d };
151
assert { from_int (- k) = -. from_int k };
152
assert { r = a +. from_int (- k) *. d }
153
end else begin
154
assert { abs d = -. d };
155
assert { r = a +. from_int k *. d }
156
end {qed}
157
end