Debian Codegraph @

Formal_ineqs/trig/atn_eval.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2014 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Formal interval evaluation of functions: atn *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/trig/atn.hl";;
14 needs "Formal_ineqs/trig/poly_eval.hl";;
15
16 module type Atn_eval_sig =
17 sig
18 val float_atn_lo : int -> term -> thm
19 val float_atn_hi : int -> term -> thm
20 val float_interval_atn : int -> thm -> thm
21 val pi_approx_array : thm array
22 val pi2_approx_array : thm array
23 end;;
24
25 module Atn_eval : Atn_eval_sig = struct
26
27 open Misc_functions;;
28 open Atn;;
29 open More_list;;
30 open Poly;;
31 open Poly_eval;;
32 open Interval_arith;;
33 open Arith_nat;;
34 open Float_theory;;
35 open Arith_float;;
36 open More_float;;
37 open Misc_vars;;
38
39 prioritize_real();;
40
41
42 let th_rule = UNDISCH_ALL o PURE_REWRITE_RULE[real_zero] o
43 PURE_REWRITE_RULE[GSYM IMP_IMP; GSYM float1_eq; NUMERAL] o SPEC_ALL;;
44
45
46 let halfatn_pos_hi_th = (th_rule o prove)
47 (`interval_arith x (real_zero, t) /\
48 a <= t * t /\
49 b <= &1 + a /\
50 c <= sqrt b /\
51 float_num F n1 e1 <= c + &1 /\
52 (n1 = 0 <=> F) /\
53 t / (float_num F n1 e1) <= hi
54 ==> interval_arith (halfatn x) (real_zero, hi)`,
55 REWRITE_TAC[real_zero; interval_arith] THEN REPEAT STRIP_TAC THENL [
56 MATCH_MP_TAC halfatn_pos THEN ASM_REWRITE_TAC[];
57 ALL_TAC
58 ] THEN
59 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `halfatn t` THEN
60 ASM_SIMP_TAC[halfatn_mono] THEN
61 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `t / (float_num F n1 e1)` THEN
62 SUBGOAL_THEN `&0 < float_num F n1 e1` ASSUME_TAC THENL [
63 ASM_REWRITE_TAC[REAL_LT_LE; FLOAT_EQ_0; EQ_SYM_EQ; FLOAT_F_POS];
64 ALL_TAC
65 ] THEN
66 ASM_SIMP_TAC[halfatn; pos_lemma2; RAT_LEMMA4] THEN
67 MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[FLOAT_F_POS] THEN
68 CONJ_TAC THENL [ ASM_ARITH_TAC; ALL_TAC ] THEN
69 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `c + &1` THEN
70 ASM_REWRITE_TAC[REAL_LE_RADD] THEN
71 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `sqrt b` THEN
72 ASM_REWRITE_TAC[SQRT_MONO_LE_EQ] THEN
73 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1 + a` THEN
74 ASM_REWRITE_TAC[REAL_LE_LADD; REAL_POW_2]);;
75
76 let halfatn_pos_lo_th = (th_rule o prove)
77 (`interval_arith t (real_zero, x) /\
78 t * t <= a /\
79 &1 + a <= b /\
80 sqrt b <= c /\
81 c + &1 <= r /\
82 float_num F n e <= t / r
83 ==> interval_arith (float_num F n e) (real_zero, halfatn x)`,
84 REWRITE_TAC[real_zero; interval_arith; FLOAT_F_POS] THEN REPEAT STRIP_TAC THEN
85 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `halfatn t` THEN
86 ASM_SIMP_TAC[halfatn_mono] THEN
87 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `t / r` THEN
88 SUBGOAL_THEN `&0 < r` ASSUME_TAC THENL [
89 SUBGOAL_THEN `&0 <= c` MP_TAC THENL [
90 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `sqrt b` THEN ASM_REWRITE_TAC[SQRT_LE_0] THEN
91 MP_TAC (SPEC `t:real` REAL_LE_SQUARE) THEN ASM_ARITH_TAC;
92 ALL_TAC
93 ] THEN
94 ASM_ARITH_TAC;
95 ALL_TAC
96 ] THEN
97 ASM_SIMP_TAC[halfatn; pos_lemma2; RAT_LEMMA4] THEN
98 MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[] THEN
99 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `c + &1` THEN
100 ASM_REWRITE_TAC[REAL_LE_RADD] THEN
101 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `sqrt b` THEN
102 ASM_REWRITE_TAC[SQRT_MONO_LE_EQ] THEN
103 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1 + a` THEN
104 ASM_REWRITE_TAC[REAL_LE_LADD; REAL_POW_2]);;
105
106 let halfatn4_eq = prove
107 (`halfatn(halfatn(halfatn(halfatn x))) = halfatn4 x`,
108 REWRITE_TAC[halfatn4; o_THM]);;
109
110 let float16 = mk_float 16 0;;
111 let float16_eq = FLOAT_TO_NUM_CONV float16;;
112
113 let atn_high0 = (th_rule o PURE_REWRITE_RULE[SYM float0_eq] o prove)
114 (`(x = real_zero <=> T) ==> atn x <= &0`,
115 SIMP_TAC[real_zero; ATN_0; REAL_LE_REFL]);;
116
117 let atn_low0 = (th_rule o PURE_REWRITE_RULE[SYM float0_eq] o prove)
118 (`(x = real_zero <=> T) ==> &0 <= atn x`,
119 SIMP_TAC[real_zero; ATN_0; REAL_LE_REFL]);;
120
121 let atn_neg_high = (th_rule o prove)
122 (`lo <= atn (float_num F n e) /\ hi = --lo
123 ==> atn (float_num T n e) <= hi`,
124 MP_TAC ((GSYM o SPEC `F`) FLOAT_NEG) THEN SIMP_TAC[] THEN DISCH_TAC THEN
125 REWRITE_TAC[ATN_NEG] THEN REAL_ARITH_TAC);;
126
127 let atn_neg_low = (th_rule o prove)
128 (`atn (float_num F n e) <= hi /\ lo = --hi
129 ==> lo <= atn (float_num T n e)`,
130 MP_TAC ((GSYM o SPEC `F`) FLOAT_NEG) THEN SIMP_TAC[] THEN DISCH_TAC THEN
131 REWRITE_TAC[ATN_NEG] THEN REAL_ARITH_TAC);;
132
133 let atn_interval_th = (th_rule o prove)
134 (`interval_arith x (a, b) /\
135 lo <= atn a /\
136 atn b <= hi
137 ==> interval_arith (atn x) (lo, hi)`,
138 REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THENL [
139 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `atn a` THEN
140 ASM_REWRITE_TAC[ATN_MONO_LE_EQ];
141 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `atn b` THEN
142 ASM_REWRITE_TAC[ATN_MONO_LE_EQ]
143 ]);;
144
145 let bound_high_transformation = (PURE_REWRITE_RULE[SYM float16_eq] o
146 GEN_REWRITE_RULE (RAND_CONV o ONCE_DEPTH_CONV) [SYM float1_eq] o
147 prove)
148 (`(&0 <= t /\ t < &1 ==> atn t <= t * (p1 - t pow 2 * p2)) ==>
149 interval_arith (halfatn4 x) (&0, t) /\
150 (t < &1 <=> T) /\
151 interval_arith p1 (&0, a) /\
152 interval_arith b (&0, p2) /\
153 interval_arith m (&0, t pow 2) /\
154 n <= m * b /\
155 a - n <= c /\
156 t * c <= r /\
157 &16 * r <= hi
158 ==> atn x <= hi`,
159 REWRITE_TAC[interval_arith; halfatn4_pos_eq] THEN REPEAT STRIP_TAC THEN
160 SUBGOAL_THEN `&0 <= t` ASSUME_TAC THENL [
161 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `halfatn4 x` THEN ASM_REWRITE_TAC[halfatn4_pos_eq];
162 ALL_TAC
163 ] THEN
164 ONCE_REWRITE_TAC[atn_halfatn4] THEN
165 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&16 * r` THEN ASM_REWRITE_TAC[] THEN
166 MATCH_MP_TAC REAL_LE_LMUL THEN REWRITE_TAC[REAL_ARITH `&0 <= &16`] THEN
167 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `atn t` THEN ASM_REWRITE_TAC[ATN_MONO_LE_EQ] THEN
168 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `t * c` THEN ASM_REWRITE_TAC[] THEN
169 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `t * (p1 - t pow 2 * p2)` THEN ASM_SIMP_TAC[] THEN
170 MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[] THEN
171 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a - n` THEN ASM_REWRITE_TAC[] THEN
172 MATCH_MP_TAC (REAL_ARITH `p1 <= a /\ n <= x ==> p1 - x <= a - n`) THEN ASM_REWRITE_TAC[] THEN
173 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `m * b` THEN ASM_REWRITE_TAC[] THEN
174 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[]);;
175
176 let bound_low_transformation = (PURE_REWRITE_RULE[SYM float16_eq] o
177 GEN_REWRITE_RULE (RAND_CONV o ONCE_DEPTH_CONV) [SYM float1_eq] o
178 prove)
179 (`(&0 <= t /\ t < &1 ==> t * (p1 - t pow 2 * p2) <= atn t) ==>
180 interval_arith t (&0, halfatn4 x) /\
181 (t < &1 <=> T) /\
182 interval_arith a (&0, p1) /\
183 interval_arith p2 (&0, b) /\
184 interval_arith (t pow 2) (&0, m) /\
185 m * b <= n /\
186 c <= a - n /\
187 r <= t * c /\
188 lo <= &16 * r
189 ==> lo <= atn x`,
190 REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN
191 ONCE_REWRITE_TAC[atn_halfatn4] THEN
192 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&16 * r` THEN ASM_REWRITE_TAC[] THEN
193 MATCH_MP_TAC REAL_LE_LMUL THEN REWRITE_TAC[REAL_ARITH `&0 <= &16`] THEN
194 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `atn t` THEN ASM_REWRITE_TAC[ATN_MONO_LE_EQ] THEN
195 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `t * c` THEN ASM_REWRITE_TAC[] THEN
196 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `t * (p1 - t pow 2 * p2)` THEN ASM_SIMP_TAC[] THEN
197 MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[] THEN
198 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a - n` THEN ASM_REWRITE_TAC[] THEN
199 MATCH_MP_TAC (REAL_ARITH `a <= p1 /\ x <= n ==> a - n <= p1 - x`) THEN ASM_REWRITE_TAC[] THEN
200 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `m * b` THEN ASM_REWRITE_TAC[] THEN
201 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[]);;
202
203 let atn_low_trivial = (th_rule o PURE_REWRITE_RULE[SYM float0_eq] o prove)
204 (`interval_arith t (real_zero, halfatn4 x) ==> &0 <= atn x`,
205 REWRITE_TAC[interval_arith; real_zero] THEN
206 DISCH_THEN (MP_TAC o MATCH_MP REAL_LE_TRANS) THEN
207 REWRITE_TAC[halfatn4_pos_eq; ATN_POS_LE]);;
208
209 let interval_pos_th = prove
210 (`interval_arith (float_num F n e) (&0, float_num F n e)`,
211 REWRITE_TAC[interval_arith; FLOAT_F_POS; REAL_LE_REFL]);;
212
213 (* ---------------------------------- *)
214 (* halfatn, halfatn4 *)
215 (* ---------------------------------- *)
216
217 (* x_th = |- interval_arith x (&0, t) *)
218 let eval_halfatn_pos_hi pp x_th =
219 let x_tm, bounds = dest_interval_arith (concl x_th) in
220 let t_tm = rand bounds in
221 let tt_th = float_mul_lo pp t_tm t_tm in
222 let a_tm = lhand (concl tt_th) in
223 let a1_th = float_add_lo pp one_float a_tm in
224 let b_tm = lhand (concl a1_th) in
225 let sqrt_th = float_sqrt_lo pp b_tm in
226 let c_tm = lhand (concl sqrt_th) in
227 let c1_th = float_add_lo pp c_tm one_float in
228 let f_tm = lhand (concl c1_th) in
229 let s, n1_tm, e1_tm = dest_float f_tm in
230 let _ =
231 if s <> "F" then
232 failwith ("eval_halfatn_pos_hi: s <> F: " ^ string_of_term (concl x_th))
233 else () in
234 let div_th = float_div_hi pp t_tm f_tm in
235 let hi_tm = rand (concl div_th) in
236 let n1_not0 = raw_eq0_hash_conv n1_tm in
237 let _ =
238 if fst (dest_const (rand (concl n1_not0))) = "T" then
239 failwith ("eval_halfatn_pos_hi: n1 = 0: " ^ string_of_term (concl x_th))
240 else () in
241 let th0 = INST[x_tm, x_var_real; t_tm, t_var_real; hi_tm, hi_var_real;
242 a_tm, a_var_real; b_tm, b_var_real; c_tm, c_var_real;
243 n1_tm, n1_var_num; e1_tm, e1_var_num] halfatn_pos_hi_th in
244 itlist MY_PROVE_HYP [tt_th; a1_th; sqrt_th; c1_th; n1_not0; div_th; x_th] th0;;
245
246
247 (* x_th = |- interval_arith t (&0, x) *)
248 let eval_halfatn_pos_lo pp x_th =
249 let t_tm, bounds = dest_interval_arith (concl x_th) in
250 let x_tm = rand bounds in
251 let tt_th = float_mul_hi pp t_tm t_tm in
252 let a_tm = rand (concl tt_th) in
253 let a1_th = float_add_hi pp one_float a_tm in
254 let b_tm = rand (concl a1_th) in
255 let sqrt_th = float_sqrt_hi pp b_tm in
256 let c_tm = rand (concl sqrt_th) in
257 let c1_th = float_add_hi pp c_tm one_float in
258 let r_tm = rand (concl c1_th) in
259 let div_th = float_div_lo pp t_tm r_tm in
260 let lo_tm = lhand (concl div_th) in
261 let s, n_tm, e_tm = dest_float lo_tm in
262 let _ =
263 if s <> "F" then
264 failwith ("eval_halfatn_pos_lo: s <> F: " ^ string_of_term (concl x_th))
265 else () in
266 let th0 = INST[x_tm, x_var_real; t_tm, t_var_real; r_tm, r_var_real;
267 a_tm, a_var_real; b_tm, b_var_real; c_tm, c_var_real;
268 n_tm, n_var_num; e_tm, e_var_num] halfatn_pos_lo_th in
269 itlist MY_PROVE_HYP [tt_th; a1_th; sqrt_th; c1_th; div_th; x_th] th0;;
270
271 (* x_th = |- interval_arith x (&0, t) *)
272 let eval_halfatn4_pos_hi pp x_th =
273 let x_tm = (rand o rator o concl) x_th in
274 let f = eval_halfatn_pos_hi pp in
275 let th0 = f (f (f (f x_th))) in
276 let eq_th = INST[x_tm, x_var_real] halfatn4_eq in
277 let ltm, bounds = dest_comb (concl th0) in
278 EQ_MP (AP_THM (AP_TERM (rator ltm) eq_th) bounds) th0;;
279
280 (* x_th = |- interval_arith t (&0, x) *)
281 let eval_halfatn4_pos_lo pp x_th =
282 let x_tm = (rand o rand o concl) x_th in
283 let f = eval_halfatn_pos_lo pp in
284 let th0 = f (f (f (f x_th))) in
285 let eq_th = INST[x_tm, x_var_real] halfatn4_eq in
286 let ltm, bounds = dest_comb (concl th0) in
287 EQ_MP (AP_TERM ltm (AP_TERM (rator bounds) eq_th)) th0;;
288
289
290 (* ---------------------------------- *)
291 (* atn upper/lower bounds *)
292 (* ---------------------------------- *)
293
294 let mk_bound_tables bound_th =
295 let bound = (SPEC_ALL o
296 REWRITE_RULE[poly_f_even; poly_f_odd; GSYM REAL_POW_2; REAL_POW_POW] o
297 REWRITE_RULE[alt_sum_eq_poly_f_even; alt_sum_eq_poly_f_odd; real_div]) bound_th in
298 (* This rule does not simplify factorials *)
299 let reduce_rule = CONV_RULE (DEPTH_CONV (FIRST_CONV [NUM_SUC_CONV; NUM_ADD_CONV; NUM_MULT_CONV])) in
300 let find_poly_f = rev o find_terms (fun tm ->
301 try (rator o rator) tm = `poly_f` with Failure _ -> false) in
302 fun pp n ->
303 let n_tm = mk_small_numeral n in
304 let th0 = INST[n_tm, n_var_num] bound in
305 let th1 = CONV_RULE NUM_REDUCE_CONV th0 in
306 let poly_tms0 = find_poly_f (concl th1) in
307 let ns_th = map (REDEPTH_CONV num_CONV o rand o rand o rator) poly_tms0 in
308 let th2 = REWRITE_RULE(ns_th @ [TABLE_SUC; TABLE_0; APPEND]) th1 in
309 let bound_th = (REWRITE_RULE[REAL_INV_1] o reduce_rule) th2 in
310 let poly_tms = find_poly_f (concl bound_th) in
311 let cs_tms = map (rand o rator) poly_tms in
312 let cs_lists = map (mk_poly_coeffs pp) cs_tms in
313 bound_th, zip cs_tms cs_lists;;
314
315 (* Computes i such that x^(2 * i + 1) / (2 * i + 1) <= base^(-(p + 1)) and cond(i) *)
316 let n_of_p_atn x pp cond =
317 let t = (float_of_int Arith_num.arith_base) ** (float_of_int (-pp - 1)) in
318 let rec try_i i =
319 let _ = if i > 50 then failwith "n_of_p_atn: cannot find i" else () in
320 if cond i then
321 let d = float_of_int (2 * i + 1) in
322 let r = (x ** d) /. d in
323 if r <= t then i else try_i (i + 1)
324 else
325 try_i (i + 1)
326 in
327 try_i 0;;
328
329 (* Makes the table of atn coefficients assuming the interval [0, 0.125] *)
330 let mk_atn_upper pp =
331 let n = n_of_p_atn 0.125 pp (fun i -> i land 1 = 0) in
332 let bound_th0, css = mk_bound_tables atn_poly_pos_upper_bound (pp + 1) n in
333 let cs1, cs2 = pair_of_list css in
334 let RULE2 = UNDISCH_ALL o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL in
335 let bound_th1 = INST[t_var_real, x_var_real] bound_th0 in
336 let bound_th = RULE2 (MATCH_MP bound_high_transformation bound_th1) in
337 bound_th, cs1, cs2;;
338
339 let mk_atn_lower pp =
340 let n = n_of_p_atn 0.125 pp (fun i -> i land 1 = 1) in
341 let bound_th0, css = mk_bound_tables atn_poly_pos_lower_bound (pp + 1) n in
342 let cs1, cs2 = pair_of_list css in
343 let RULE2 = UNDISCH_ALL o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL in
344 let bound_th1 = INST[t_var_real, x_var_real] bound_th0 in
345 let bound_th = RULE2 (MATCH_MP bound_low_transformation bound_th1) in
346 bound_th, cs1, cs2;;
347
348 (* x_th = |- interval_arith x (&0, x) *)
349 let float_atn_pos_high =
350 let atn_upper_table = Array.init 21 mk_atn_upper in
351 fun pp x_tm x_th ->
352 let bound_th, cs1, cs2 = atn_upper_table.(pp) in
353 let pp = pp + 1 in
354 let h4 = eval_halfatn4_pos_hi pp x_th in
355 let t_tm = rand (rand (concl h4)) in
356 let t_pow4_high = eval_pow4_high pp t_tm in
357 let t_pow2_low, t_pow4_low = eval_pow2_pow4_low pp t_tm in
358 let p1_high = eval_high_poly_f_pos_pos pp cs1 t_pow4_high in
359 let p2_low = eval_low_poly_f_pos_pos pp cs2 t_pow4_low in
360 let a_tm = rand (rand (concl p1_high)) in
361 let b_tm = rand (rator (concl p2_low)) in
362 let m_tm = rand (rator (concl t_pow2_low)) in
363 let n_le_mb = float_mul_lo pp m_tm b_tm in
364 let n_tm = rand (rator (concl n_le_mb)) in
365 let an_le_c = float_sub_hi pp a_tm n_tm in
366 let c_tm = rand (concl an_le_c) in
367 let tc_le_r = float_mul_hi pp t_tm c_tm in
368 let r_tm = rand (concl tc_le_r) in
369 let r16_le_hi = float_mul_hi pp float16 r_tm in
370 let hi_tm = rand (concl r16_le_hi) in
371 let cmp_1 = float_lt t_tm one_float in
372 if (fst o dest_const o rand o concl) cmp_1 = "F" then
373 failwith ("float_atn_pos_high: t >= 1: " ^ string_of_term x_tm)
374 else
375 let th0 = INST[a_tm, a_var_real; b_tm, b_var_real; c_tm, c_var_real;
376 n_tm, n_var_real; m_tm, m_var_real; r_tm, r_var_real;
377 x_tm, x_var_real; t_tm, t_var_real; hi_tm, hi_var_real] bound_th in
378 itlist MY_PROVE_HYP [p1_high; p2_low; t_pow2_low; n_le_mb; an_le_c;
379 tc_le_r; r16_le_hi; cmp_1; h4] th0;;
380
381 (* x_th = |- interval_arith x (&0, x) *)
382 let float_atn_pos_low =
383 let atn_lower_table = Array.init 21 mk_atn_lower in
384 fun pp x_tm x_th ->
385 let bound_th, cs1, cs2 = atn_lower_table.(pp) in
386 let pp = pp + 1 in
387 let h4 = eval_halfatn4_pos_lo pp x_th in
388 let t_tm = rand (rator (concl h4)) in
389 let t_pow4_low = eval_pow4_low pp t_tm in
390 let t_pow2_high, t_pow4_high = eval_pow2_pow4_high pp t_tm in
391 let p1_low = eval_low_poly_f_pos_pos pp cs1 t_pow4_low in
392 let p2_high = eval_high_poly_f_pos_pos pp cs2 t_pow4_high in
393 let a_tm = rand (rator (concl p1_low)) in
394 let b_tm = rand (rand (concl p2_high)) in
395 let m_tm = rand (rand (concl t_pow2_high)) in
396 let mb_le_n = float_mul_hi pp m_tm b_tm in
397 let n_tm = rand (concl mb_le_n) in
398 let c_le_an = float_sub_lo pp a_tm n_tm in
399 let c_tm = rand (rator (concl c_le_an)) in
400 let r_le_tc = float_mul_lo pp t_tm c_tm in
401 let r_tm = rand (rator (concl r_le_tc)) in
402 let lo_le_r16 = float_mul_lo pp float16 r_tm in
403 let lo_tm = rand (rator (concl lo_le_r16)) in
404 if (fst o dest_const o rand o rator o rator) lo_tm = "T" then
405 (* lo <= 0 ==> return the trivail bound 0 *)
406 let th0 = INST[x_tm, x_var_real; t_tm, t_var_real] atn_low_trivial in
407 MY_PROVE_HYP h4 th0
408 else
409 let cmp_1 = float_lt t_tm one_float in
410 if (fst o dest_const o rand o concl) cmp_1 = "F" then
411 failwith ("float_atn_pos_low: t >= 1: " ^ string_of_term x_tm)
412 else
413 let th0 = INST[a_tm, a_var_real; b_tm, b_var_real; c_tm, c_var_real;
414 n_tm, n_var_real; m_tm, m_var_real; r_tm, r_var_real;
415 x_tm, x_var_real; t_tm, t_var_real; lo_tm, lo_var_real] bound_th in
416 itlist MY_PROVE_HYP [p1_low; p2_high; t_pow2_high; mb_le_n; c_le_an;
417 r_le_tc; lo_le_r16; cmp_1; h4] th0;;
418
419 (* Computes an upper bound of atn for a given floating-point number *)
420 let float_atn_hi pp x_tm =
421 let s, n_tm, e_tm = dest_float x_tm in
422 let x_th = INST[n_tm, n_var_num; e_tm, e_var_num] interval_pos_th in
423 if s = "F" then
424 float_atn_pos_high pp x_tm x_th
425 else
426 let x_pos_tm = rand (rand (concl x_th)) in
427 let lo_th = float_atn_pos_low pp x_pos_tm x_th in
428 let lo_tm = rand (rator (concl lo_th)) in
429 let neg_lo = float_neg lo_tm in
430 let hi_tm = rand (rator (concl neg_lo)) in
431 let th0 = INST[n_tm, n_var_num; e_tm, e_var_num;
432 lo_tm, lo_var_real; hi_tm, hi_var_real] atn_neg_high in
433 MY_PROVE_HYP lo_th (MY_PROVE_HYP neg_lo th0);;
434
435 (* Computes a lower bound of atn for a given floating-point number *)
436 let float_atn_lo pp x_tm =
437 let s, n_tm, e_tm = dest_float x_tm in
438 let x_th = INST[n_tm, n_var_num; e_tm, e_var_num] interval_pos_th in
439 if s = "F" then
440 float_atn_pos_low pp x_tm x_th
441 else
442 let x_pos_tm = rand (rand (concl x_th)) in
443 let hi_th = float_atn_pos_high pp x_pos_tm x_th in
444 let hi_tm = rand (concl hi_th) in
445 let neg_hi = float_neg hi_tm in
446 let lo_tm = rand (rator (concl neg_hi)) in
447 let th0 = INST[n_tm, n_var_num; e_tm, e_var_num;
448 lo_tm, lo_var_real; hi_tm, hi_var_real] atn_neg_low in
449 MY_PROVE_HYP hi_th (MY_PROVE_HYP neg_hi th0);;
450
451
452 (* ---------------------------------- *)
453 (* atn interval *)
454 (* ---------------------------------- *)
455
456 let float_interval_atn pp x_th =
457 let x_tm, bounds = dest_interval_arith (concl x_th) in
458 let ltm, b_tm = dest_comb bounds in
459 let a_tm = rand ltm in
460 let lo_th = float_atn_lo pp a_tm and
461 hi_th = float_atn_hi pp b_tm in
462 let lo_tm = rand (rator (concl lo_th)) and
463 hi_tm = rand (concl hi_th) in
464 let th0 = INST[x_tm, x_var_real; a_tm, a_var_real; b_tm, b_var_real;
465 lo_tm, lo_var_real; hi_tm, hi_var_real] atn_interval_th in
466 MY_PROVE_HYP x_th (MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th th0));;
467
468
469 (* ---------------------------------- *)
470 (* pi approximations *)
471 (* ---------------------------------- *)
472
473 let pi_approx_array, pi2_approx_array =
474 let pp = 20 in
475 let x_th = one_interval in
476 let th1 = float_interval_atn pp x_th in
477 let th2 = float_interval_mul pp (mk_float_interval_small_num 4) th1 in
478 let float_interval_pi = REWRITE_RULE[ATN_1; REAL_ARITH `&4 * pi / &4 = pi`] th2 in
479 let float_interval_pi2 = float_interval_div pp float_interval_pi two_interval in
480 let pi = Array.init 19 (fun i -> float_interval_round i float_interval_pi) and
481 pi2 = Array.init 19 (fun i -> float_interval_round i float_interval_pi2) in
482 pi, pi2;;
483
484 end;;