Common — library colibrilib.qa — module Rat

Facts about the rationals, used in the proofs only. Like those of Dv, they are let ghost functions that a proof calls.

40
module Rat
41
use int.Int
42
use real.RealInfix
43
use real.FromInt
44
use colibrilib.stdq.StdQ
45
Valid (42ms) (colibri2)
46
let ghost
rat_q
(q:StdQ.t) : unit
47
ensures { is_rat (real q) }
48
= ()
49
Valid (43ms) (colibri2)
50
let ghost
rat_int
(k:int) : unit
51
ensures { is_rat (from_int k) }
52
= {proof…} let q = of_bigint k in
53
assert { real q = from_int k } {qed}
54
Valid (57ms) (colibri2)
55
let ghost
rat_add
(x y:real) : unit
56
requires { is_rat x }
57
requires { is_rat y }
58
ensures { is_rat (x +. y) }
59
= {proof…} let a = any StdQ.t ensures { real result = x } in
60
let b = any StdQ.t ensures { real result = y } in
61
let c = add a b in
62
assert { real c = x +. y } {qed}
63
Valid (42ms) (colibri2)
64
let ghost
rat_sub
(x y:real) : unit
65
requires { is_rat x }
66
requires { is_rat y }
67
ensures { is_rat (x -. y) }
68
= {proof…} let a = any StdQ.t ensures { real result = x } in
69
let b = any StdQ.t ensures { real result = y } in
70
let c = sub a b in
71
assert { real c = x -. y } {qed}
72
Valid (51ms) (colibri2)
73
let ghost
rat_mul_int
(k:int) (x:real) : unit
74
requires { is_rat x }
75
ensures { is_rat (from_int k *. x) }
76
= {proof…} let a = any StdQ.t ensures { real result = x } in
77
let c = mul (of_bigint k) a in
78
assert { real c = from_int k *. x } {qed}

x is a rational iff c * x is, for an integer c that is not zero

  Valid (61ms) (colibri2)
81
let ghost
rat_scale
(c:int) (x:real) : unit
82
requires { c <> 0 }
83
ensures { is_rat (from_int c *. x) <-> is_rat x }
84
= {proof…} if pure { is_rat x } then rat_mul_int c x;
85
if pure { is_rat (from_int c *. x) } then begin
86
let a = any StdQ.t ensures { real result = from_int c *. x } in
87
assert { from_int c <> 0.0 };
88
let c' = of_bigint c in
89
let b = div a c' in
90
assert { real b = x }
91
end {qed}
92
Valid (42ms) (colibri2)
93
let ghost
rat_neg
(x:real) : unit
94
ensures { is_rat (0.0 -. x) <-> is_rat x }
95
= {proof…} rat_int 0;
96
assert { from_int 0 = 0.0 };
97
if pure { is_rat x } then rat_sub 0.0 x;
98
if pure { is_rat (0.0 -. x) } then begin
99
rat_sub 0.0 (0.0 -. x);
100
assert { 0.0 -. (0.0 -. x) = x }
101
end {qed}

Adding a multiple of a rational does not change the rationality

  Valid (43ms) (colibri2)
104
let ghost
rat_shift
(x d:real) (k:int) : unit
105
requires { is_rat d }
106
ensures { is_rat (x +. from_int k *. d) <-> is_rat x }
107
= {proof…} if pure { is_rat x } then begin
108
rat_mul_int k d;
109
rat_add x (from_int k *. d)
110
end;
111
if pure { is_rat (x +. from_int k *. d) } then begin
112
rat_mul_int k d;
113
rat_sub (x +. from_int k *. d) (from_int k *. d);
114
assert { x +. from_int k *. d -. from_int k *. d = x }
115
end {qed}

a - n where n is -a moved by a multiple of a rational

  Valid (33ms) (colibri2 3) (cvc5) (split_vc) (depth 1)
118
let ghost
rat_double
(a n d:real) (k:int) : unit
119
requires { is_rat d }
120
requires { n = -. a +. from_int k *. d }
121
ensures { is_rat (a -. n) <-> is_rat a }
122
= {proof…} assert { a -. n = from_int 2 *. a +. from_int (- k) *. d
123
by from_int (- k) = -. from_int k /\ from_int 2 = 2.0 };
124
rat_shift (from_int 2 *. a) d (- k);
125
rat_scale 2 a {qed}
126
end