| 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;; |