Common — library colibrilib.stda — module A_intf

The real algebraic numbers, implemented by StdA. One name per notion, no program operator; the specifications are on the real value. A number has several representations at most for its value: the equality of the numbers is equal, not the logical equality. Only add, sub, mul and mod_e are logic functions on t (polynome.mlw needs their terms).

12
module A_intf
13
use real.RealInfix
14
use int.Int
15
use real.FromInt
16
use real.Abs
17
use real.Square
18
use real.Truncate
19
use mach.int.Int63
20
use colibrilib.q.Ord as Ord
21
use colibrilib.q.Real as Real
22
use colibrilib.dv.Dv
23
use colibrilib.stdq.StdQ as Q
24
use real.PowerInt
25
26
type
t
27
28
function
real
(x:t) : real
29
30
meta coercion function real

The rational numbers among the algebraic ones

33
predicate
rational
(a:t) = Q.is_rat (real a)
34
Valid (25ms) (colibri2)
35
val
equal
(a b:t) : bool
36
ensures { result <-> real a = real b }
37
Valid (22ms) (colibri2)
38
val
le
(a b:t) : bool
39
ensures { result <-> real a <=. real b }
40
Valid (22ms) (colibri2)
41
val
lt
(a b:t) : bool
42
ensures { result <-> real a <. real b }
43
Valid (28ms) (colibri2)
44
val
abs
(a:t) : t
45
ensures { real result = abs (real a) }
46
Valid (24ms) (colibri2)
47
val
compare
(a b:t) : Ord.t
48
ensures { match result with
49
| Ord.Eq -> real a = real b
50
| Ord.Lt -> real a <. real b
51
| Ord.Gt -> real b <. real a
52
end }
53
Valid (17ms) (colibri2)
54
val function
add
(a b:t) : t
55
ensures { real result = real a +. real b }
56
Valid (26ms) (colibri2)
57
val function
sub
(a b:t) : t
58
ensures { real result = real a -. real b }
59
Valid (31ms) (colibri2)
60
val function
mul
(a b:t) : t
61
ensures { real result = real a *. real b }

A function, for the closures given to the maps (polynome.Lin.nz)

  Valid (51ms) (colibri2)
64
val function
is_zero
(a:t) : bool
65
ensures { result <-> real a = 0. }
66
Valid (30ms) (colibri2)
67
val
div
(a b:t) : t
68
requires { real b <> 0. }
69
ensures { real result = real a /. real b }
70
Valid (35ms) (colibri2)
71
val
neg
(a:t) : t
72
ensures { real result = -. real a }
73
Valid (34ms) (colibri2)
74
val
of_int
(a:int63) : t
75
ensures { real result = from_int a }
76
Valid (28ms) (colibri2)
77
val
of_bigint
(a:int) : t
78
ensures { real result = from_int a }
79
Valid (28ms) (colibri2)
80
val
truncate_z
(a:t) : int
81
ensures { result = truncate (real a) }
82
Valid (29ms) (colibri2)
83
val
floor_z
(a:t) : int
84
ensures { result = floor (real a) }
85
Valid (24ms) (colibri2)
86
val
ceil_z
(a:t) : int
87
ensures { result = ceil (real a) }
88
Valid (42ms) (colibri2)
89
val
is_integer
(a:t) : bool
90
ensures { result <-> Real.is_integer (real a) }
91
Valid (32ms) (colibri2)
92
val
div_e
(a b:t) : t
93
requires { real b <> 0. }
94
ensures { real result = from_int (Real.div_e (real a) (real b)) }

The Euclidean remainder, as a term: polynome.mlw reduces coefficients

  Valid (37ms) (colibri2)
97
val function
mod_e
(a b:t) : t
98
requires { real b <> 0. }
99
ensures { real result = Real.mod_e (real a) (real b) }
100
Valid (26ms) (colibri2)
101
val
div_t
(a b:t) : t
102
requires { real b <> 0. }
103
ensures { real result = from_int (Real.div_t (real a) (real b)) }
104
Valid (29ms) (colibri2)
105
val
mod_t
(a b:t) : t
106
requires { real b <> 0. }
107
ensures { real result = Real.mod_t (real a) (real b) }
108
Valid (23ms) (colibri2)
109
val
div_f
(a b:t) : t
110
requires { real b <> 0. }
111
ensures { real result = from_int (Real.div_f (real a) (real b)) }
112
Valid (29ms) (colibri2)
113
val
mod_f
(a b:t) : t
114
requires { real b <> 0. }
115
ensures { real result = Real.mod_f (real a) (real b) }
116
Valid (33ms) (colibri2)
117
val
sqrt
(a:t) : t
118
requires { 0. <=. real a }
119
ensures { real result = sqrt (real a) }

The two cases of the representation: Irr is a number that is not a rational (the invariant of StdA.irr, proved from Flint's to_q)

123
type
view
=
Rat
Q.t |
Irr
124
Valid (34ms) (colibri2)
125
val
view
(a:t) : view
126
ensures { match result with
127
| Rat q -> real a = Q.real q
128
| Irr -> forall q:Q.t. real a <> Q.real q
129
end }
130
Valid (28ms) (colibri2)
131
val
of_q
(q:Q.t) : t
132
ensures { real result = Q.real q }

The value of an integer

  Valid (29ms) (colibri2)
135
val
to_z
(a:t) : int
136
requires { Real.is_integer (real a) }
137
ensures { from_int result = real a }

The largest multiple of m (positive) below a, and the smallest above

  Valid (24ms) (colibri2)
140
val
round_down_to
(a:t) (m:Q.t) : Q.t
141
requires { 0.0 <. Q.real m }
142
ensures { dv (Q.real result) (Q.real m) }
143
ensures { Q.real result <=. real a <. Q.real result +. Q.real m }
144
Valid (38ms) (colibri2)
145
val
round_up_to
(a:t) (m:Q.t) : Q.t
146
requires { 0.0 <. Q.real m }
147
ensures { dv (Q.real result) (Q.real m) }
148
ensures { Q.real result -. Q.real m <. real a <=. Q.real result }

a^e, the non negative root: for a fraction n/d equal to e, the d–th power of the result is the n–th power of a. The power of the reals is left out of this interface: colibrilib.product.APow derives it.

  Valid (242ms) (colibri2)
154
val
positive_pow
(a:t) (e:Q.t) : t
155
requires { 0. <. real a \/ (real a = 0. /\ 0. <. Q.real e) }
156
ensures { 0. <=. real result }
157
ensures { exists n d:int. 0 < d /\ Q.real e = from_int n /. from_int d /\
158
(0 <= n -> power (real result) d = power (real a) n) /\
159
(n < 0 -> power (real result) d *. power (real a) (- n) = 1.) }
160
end