Debian Codegraph @

Formal_ineqs/informal/informal_interval.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2012 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Informal arithmetic procedures: interval arithmetic *)
11 (* -------------------------------------------------------------------------- *)
12
13 (* Dependencies *)
14 needs "Formal_ineqs/informal/informal_float.hl";;
15
16 (* Interval arithmetic *)
17
18 module type Informal_interval_sig =
19 sig
20 type interval
21 val print_interval_fmt : Format.formatter -> interval -> unit
22 val print_interval : interval -> unit
23 val zero_interval : interval
24 val one_interval : interval
25 val two_interval : interval
26 val mk_interval : Informal_float.ifloat * Informal_float.ifloat -> interval
27 val mk_num_interval : num -> interval
28 val mk_small_num_interval : int -> interval
29 val dest_interval : interval -> Informal_float.ifloat * Informal_float.ifloat
30 val round_interval : int -> interval -> interval
31 val abs_interval : interval -> interval
32 val neg_interval : interval -> interval
33 val mul_interval : int -> interval -> interval -> interval
34 val div_interval : int -> interval -> interval -> interval
35 val add_interval : int -> interval -> interval -> interval
36 val sub_interval : int -> interval -> interval -> interval
37 val sqrt_interval : int -> interval -> interval
38 val inv_interval : int -> interval -> interval
39 val pow_interval : int -> int -> interval -> interval
40 (* Computes max(-lo, hi) *)
41 val iabs_interval : interval -> Informal_float.ifloat
42 (* Compares a floating-point value and an interval *)
43 val le_interval : Informal_float.ifloat -> interval -> bool
44 val ge_interval : Informal_float.ifloat -> interval -> bool
45 val compare_interval : Informal_float.ifloat -> interval -> int
46 (* Returns -1 if the interval is negative, 1 if it is positive, and
47 0 if it contains 0 *)
48 val compare0_interval : interval -> int
49 end;;
50
51 module Informal_interval : Informal_interval_sig = struct
52
53 open Informal_float;;
54
55
56 type interval = ifloat * ifloat;;
57
58 let print_interval_fmt fmt (lo, hi) =
59 pp_print_string fmt "(";
60 print_ifloat_fmt fmt lo;
61 pp_print_string fmt ",";
62 print_ifloat_fmt fmt hi;
63 pp_print_string fmt ")";;
64
65 let print_interval = print_interval_fmt Format.std_formatter;;
66
67 let mk_interval (lo,hi) =
68 if lt_float hi lo then failwith "mk_interval: hi < lo" else (lo,hi);;
69
70 let mk_num_interval n =
71 let f = mk_num_float n in (f, f);;
72
73 let mk_small_num_interval n =
74 let f = mk_small_num_float n in (f, f);;
75
76 let zero_float = mk_small_num_float 0;;
77 let zero_interval = mk_small_num_interval 0;;
78 let one_interval = mk_small_num_interval 1;;
79 let two_interval = mk_small_num_interval 2;;
80
81 let dest_interval ((lo,hi) : interval) = (lo,hi);;
82
83 let round_interval pp (lo,hi) = (lo_float pp lo, hi_float pp hi);;
84
85 let abs_interval (lo,hi) =
86 let s1 = sign_float lo and
87 s2 = sign_float hi in
88 if s1 = s2 then
89 if not s1 then
90 (lo,hi)
91 else
92 (neg_float hi, neg_float lo)
93 else
94 if not s1 then
95 zero_interval
96 else
97 (zero_float, max_float (neg_float lo) hi);;
98
99 let neg_interval (lo,hi) = (neg_float hi, neg_float lo);;
100
101 let iabs_interval (lo,hi) = max_float hi (neg_float lo);;
102
103 let add_interval pp (lo1,hi1) (lo2,hi2) =
104 (add_float_lo pp lo1 lo2, add_float_hi pp hi1 hi2);;
105
106 let sub_interval pp (lo1,hi1) (lo2,hi2) =
107 (sub_float_lo pp lo1 hi2, sub_float_hi pp hi1 lo2);;
108
109 let sqrt_interval pp (lo,hi) =
110 if sign_float lo then
111 failwith "sqrt_interval: negative lower bound"
112 else
113 (sqrt_float_lo pp lo, sqrt_float_hi pp hi);;
114
115 (* mul *)
116 let mul_interval pp (l_lo,l_hi) (r_lo,r_hi) =
117 let s1 = sign_float l_lo and
118 s2 = sign_float l_hi and
119 s3 = sign_float r_lo and
120 s4 = sign_float r_hi in
121 if s1 <> s2 && not s1 then
122 zero_interval
123 else if s3 <> s4 && not s3 then
124 zero_interval
125 else
126 if s1 <> s2 && s3 <> s4 then
127 let lo1, lo2 = mul_float_lo pp l_lo r_hi, mul_float_lo pp l_hi r_lo and
128 hi1, hi2 = mul_float_hi pp l_lo r_lo, mul_float_hi pp l_hi r_hi in
129 (min_float lo1 lo2, max_float hi1 hi2)
130 else
131 let lo1, lo2, hi1, hi2 =
132 if s1 <> s2 then
133 if not s3 then
134 l_lo, r_hi, l_hi, r_hi
135 else
136 l_hi, r_lo, l_lo, r_lo
137 else
138 if s3 <> s4 then
139 if not s1 then
140 l_hi, r_lo, l_hi, r_hi
141 else
142 l_lo, r_hi, l_lo, r_lo
143 else
144 if not s1 then
145 if not s3 then
146 l_lo, r_lo, l_hi, r_hi
147 else
148 l_hi, r_lo, l_lo, r_hi
149 else
150 if not s3 then
151 l_lo, r_hi, l_hi, r_lo
152 else
153 l_hi, r_hi, l_lo, r_lo in
154 (mul_float_lo pp lo1 lo2, mul_float_hi pp hi1 hi2);;
155
156 (* div *)
157 let div_interval pp (l_lo,l_hi) (r_lo,r_hi) =
158 let s1 = sign_float l_lo and
159 s2 = sign_float l_hi and
160 s3 = sign_float r_lo and
161 s4 = sign_float r_hi in
162 if s1 <> s2 && not s1 then
163 zero_interval
164 else if s3 <> s4 then
165 failwith "div_interval: division by an interval containing 0"
166 else
167 let lo1, lo2, hi1, hi2 =
168 if s1 = s2 then
169 if not s1 then
170 if not s3 then
171 l_lo, r_hi, l_hi, r_lo
172 else
173 l_hi, r_hi, l_lo, r_lo
174 else
175 if not s3 then
176 l_lo, r_lo, l_hi, r_hi
177 else
178 l_hi, r_lo, l_lo, r_hi
179 else
180 if not s3 then
181 l_lo, r_lo, l_hi, r_lo
182 else
183 l_hi, r_hi, l_lo, r_hi in
184 (div_float_lo pp lo1 lo2, div_float_hi pp hi1 hi2);;
185
186 (* inv *)
187 let inv_interval pp int =
188 div_interval pp one_interval int;;
189
190 (* pow *)
191 let pow_interval pp n (lo, hi) =
192 match n with
193 | 0 -> one_interval
194 | 1 -> (lo, hi)
195 | _ ->
196 let _ = assert (n > 1) in
197 if (n land 1) = 1 then
198 (pow_float_lo pp n lo, pow_float_hi pp n hi)
199 else
200 let s1 = sign_float lo and
201 s2 = sign_float hi in
202 if s1 = s2 then
203 if not s1 then
204 (* FF *)
205 (pow_float_lo pp n lo, pow_float_hi pp n hi)
206 else
207 (* TT *)
208 (pow_float_lo pp n (abs_float hi), pow_float_hi pp n (abs_float lo))
209 else
210 if not s1 then
211 (* FT *)
212 zero_interval
213 else
214 (* TF *)
215 let m = max_float (abs_float lo) hi in
216 (float0, pow_float_hi pp n m);;
217
218 (* le_interval *)
219 let le_interval x (lo, hi) = le_float x lo;;
220
221 (* ge_interval *)
222 let ge_interval x (lo, hi) = le_float hi x;;
223
224 (* compare_interval *)
225 let compare_interval x (lo, hi) =
226 if le_float x lo then -1
227 else if le_float hi x then 1
228 else 0;;
229
230 (* compare0_interval *)
231 let compare0_interval (lo, hi) =
232 if gt0_float lo then 1
233 else if lt0_float hi then -1
234 else 0;;
235
236 end;;
237
238 (*
239 open Informal_float;;
240 open Informal_interval;;
241
242 #install_printer print_float;;
243 #install_printer print_interval;;
244
245 let pp = 3;;
246 let n = 41;;
247 let mk_test a b = mk_interval (mk_float a 0, mk_float b 0);;
248
249 pow_interval pp n (mk_test 1 2);;
250 pow_interval pp n (mk_test (-1) 2);;
251 pow_interval pp n (mk_test (-3) (-2));;
252 pow_interval pp n (mk_test 0 1);;
253 pow_interval pp n (mk_test (-2) 1);;
254 *)