Common — library colibrilib.pow2r — module Pow2r
6
module Pow2r
7
use int.Int
8
use int.Power
9
use real.RealInfix
10
use real.FromInt
11
12
function
pow2r
(e: int) : real =
13
if 0 <= e then from_int (power 2 e) else 1.0 /. from_int (power 2 (-e))
14
Valid (23ms) (colibri2)
15
let ghost
pow2r_pos
(e: int) : unit
16
ensures { 0.0 <. pow2r e }
17
= {proof…}
18
if 0 <= e then assert { 0 < power 2 e } else assert { 0 < power 2 (-e) }
19
{qed}
20
Valid (37ms) (colibri2)
21
let ghost
pow2r_succ
(e: int) : unit
22
ensures { pow2r (e + 1) = 2.0 *. pow2r e }
23
= {proof…}
24
if 0 <= e then assert { power 2 (e + 1) = 2 * power 2 e }
25
else if e = -1 then assert { power 2 1 = 2 }
26
else begin
27
assert { power 2 (-e) = 2 * power 2 (-e - 1) };
28
assert { 0 < power 2 (-e - 1) }
29
end
30
{qed}
31
Valid (149ms) (colibri2)
32
let rec ghost
pow2r_add
(a b: int) : unit
33
ensures { pow2r (a + b) = pow2r a *. pow2r b }
34
variant { if b < 0 then -b else b }
35
= {proof…}
36
if b > 0 then begin
37
pow2r_add a (b - 1); pow2r_succ (a + b - 1); pow2r_succ (b - 1)
38
end else if b < 0 then begin
39
pow2r_add a (b + 1); pow2r_succ (a + b); pow2r_succ b
40
end else assert { pow2r 0 = 1.0 }
41
{qed}
42
Valid (20ms) (colibri2)
43
let ghost
pow2r_int
(e: int) : unit
44
requires { 0 <= e }
45
ensures { pow2r e = from_int (power 2 e) }
46
= ()
47
Valid (26ms) (colibri2)
48
let ghost
pow2r_le
(a b: int) : unit
49
requires { a <= b }
50
ensures { pow2r a <=. pow2r b }
51
= {proof…}
52
pow2r_add a (b - a); pow2r_pos a;
53
assert { 1 <= power 2 (b - a) };
54
assert { 1.0 <=. pow2r (b - a) }
55
{qed}

Comparing integers scaled by the same positive real

  Valid (81ms) (cvc5)
58
let ghost
scale_cmp
(x y: int) (c: real) : unit
59
requires { 0.0 <. c }
60
ensures { from_int x *. c <. from_int y *. c <-> x < y }
61
ensures { from_int x *. c <=. from_int y *. c <-> x <= y }
62
ensures { from_int x *. c = from_int y *. c <-> x = y }
63
= {proof…}
64
assert { from_int y *. c -. from_int x *. c = from_int (y - x) *. c };
65
if x < y then assert { 0.0 <. from_int (y - x) *. c }
66
else if y < x then assert { 0.0 <. from_int (x - y) *. c }
67
{qed}
68
end