| 1 |
let float_interval_1 = mk_float_interval_small_num 1;; |
| 2 |
|
| 3 |
let HALFATN' = (SYM o SPEC_ALL o REWRITE_RULE[REAL_POW_2]) halfatn;; |
| 4 |
let HALFATN4' = prove(`halfatn(halfatn(halfatn(halfatn x))) = halfatn4 x`, |
| 5 |
REWRITE_TAC[halfatn4; o_THM]);; |
| 6 |
|
| 7 |
let float_interval_halfatn pp x_th = |
| 8 |
let x_tm = (rand o rator o concl) x_th in |
| 9 |
let xx_th = float_interval_mul pp x_th x_th in |
| 10 |
let one_xx_th = float_interval_add pp float_interval_1 xx_th in |
| 11 |
let sqrt_th = float_interval_sqrt pp one_xx_th in |
| 12 |
let one_sqrt_th = float_interval_add pp sqrt_th float_interval_1 in |
| 13 |
let r_th = float_interval_div pp x_th one_sqrt_th in |
| 14 |
let th0 = INST[x_tm, x_var_real] HALFATN' in |
| 15 |
let ltm, rtm = dest_comb(concl r_th) in |
| 16 |
EQ_MP (AP_THM (AP_TERM (rator ltm) th0) rtm) r_th;; |
| 17 |
|
| 18 |
let float_interval_halfatn4 pp x_th = |
| 19 |
let x_tm = (rand o rator o concl) x_th in |
| 20 |
let r_th = float_interval_halfatn pp |
| 21 |
(float_interval_halfatn pp |
| 22 |
(float_interval_halfatn pp (float_interval_halfatn pp x_th))) in |
| 23 |
let th0 = INST[x_tm, x_var_real] HALFATN4' in |
| 24 |
let ltm, rtm = dest_comb(concl r_th) in |
| 25 |
EQ_MP (AP_THM (AP_TERM (rator ltm) th0) rtm) r_th;; |
| 26 |
|
| 27 |
(************************) |
| 28 |
|
| 29 |
let reduce_float_lemma = (th_rule o NUMERALS_TO_NUM o prove) |
| 30 |
(`k <= e /\ e - k = m /\ num_exp 1 k = t /\ t = r |
| 31 |
==> float_num s n m = float_num s n e / &r`, |
| 32 |
REPEAT STRIP_TAC THEN REWRITE_TAC[float; real_div] THEN |
| 33 |
ONCE_REWRITE_TAC[REAL_ARITH `(a * b * c) * d = a * (b * d) * c`] THEN |
| 34 |
REPEAT (FIRST [AP_TERM_TAC; AP_THM_TAC]) THEN |
| 35 |
EXPAND_TAC "m" THEN ASM_SIMP_TAC[NUM_EXP_SUB_lemma]);; |
| 36 |
|
| 37 |
|
| 38 |
let comb_size = |
| 39 |
let rec size n tm = |
| 40 |
match tm with |
| 41 |
| Comb (_, rtm) -> size (n + 1) rtm |
| 42 |
| _ -> n in |
| 43 |
size 0;; |
| 44 |
|
| 45 |
let reduce_float = |
| 46 |
let one_num = rand (mk_small_numeral_array 1) in |
| 47 |
fun x_tm -> |
| 48 |
let ltm, e_tm = dest_comb x_tm in |
| 49 |
let ltm, n_tm = dest_comb ltm in |
| 50 |
let s_tm = rand ltm in |
| 51 |
let exp = Num.int_of_num (raw_dest_hash e_tm) - min_exp in |
| 52 |
let k = comb_size n_tm + exp + 1 in |
| 53 |
if k <= 0 then |
| 54 |
false, TRUTH, k |
| 55 |
else |
| 56 |
let k_tm = rand (mk_small_numeral_array k) in |
| 57 |
let sub_th, le_th = raw_sub_and_le_hash_conv e_tm k_tm in |
| 58 |
let m_tm = rand (concl sub_th) in |
| 59 |
let eq_th = denormalize (mk_num_exp one_num k_tm) in |
| 60 |
let t_tm = rand (concl eq_th) in |
| 61 |
let eq2_th = raw_num_to_numeral t_tm in |
| 62 |
let r_tm = rand (concl eq2_th) in |
| 63 |
let th0 = INST[s_tm, s_var_bool; n_tm, n_var_num; e_tm, e_var_num; |
| 64 |
k_tm, k_var_num; m_tm, m_var_num; |
| 65 |
t_tm, t_var_num; r_tm, r_var_num] reduce_float_lemma in |
| 66 |
let th1 = itlist MY_PROVE_HYP [le_th; sub_th; eq_th; eq2_th] th0 in |
| 67 |
if hyp th1 <> [] then |
| 68 |
error "reduce_float" [x_tm] [sub_th; le_th; eq_th] |
| 69 |
else |
| 70 |
true, th1, Num.int_of_num (raw_dest_hash t_tm);; |
| 71 |
|
| 72 |
(* log experiments *) |
| 73 |
|
| 74 |
let bound_low_trans = prove |
| 75 |
(`x * (p1 - x * p2) <= e ==> |
| 76 |
interval_arith a (&0, p1) /\ |
| 77 |
interval_arith p2 (&0, b) /\ |
| 78 |
&0 <= x /\ |
| 79 |
x * b <= n /\ |
| 80 |
t <= a - n /\ |
| 81 |
r <= x * t |
| 82 |
==> r <= e`, |
| 83 |
REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN |
| 84 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * (p1 - x * p2)` THEN ASM_REWRITE_TAC[] THEN |
| 85 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * (a - n)` THEN CONJ_TAC THENL [ |
| 86 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * t` THEN ASM_REWRITE_TAC[] THEN |
| 87 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[]; |
| 88 |
ALL_TAC |
| 89 |
] THEN |
| 90 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[] THEN |
| 91 |
REWRITE_TAC[real_sub] THEN MATCH_MP_TAC REAL_LE_ADD2 THEN ASM_REWRITE_TAC[REAL_LE_NEG2] THEN |
| 92 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * b:real` THEN ASM_REWRITE_TAC[] THEN |
| 93 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[]);; |
| 94 |
|
| 95 |
let bound_high_trans = prove |
| 96 |
(`e <= x * (p1 - x * p2) ==> |
| 97 |
interval_arith p1 (&0, a) /\ |
| 98 |
interval_arith b (&0, p2) /\ |
| 99 |
&0 <= x /\ |
| 100 |
n <= x * b /\ |
| 101 |
a - n <= t /\ |
| 102 |
x * t <= r |
| 103 |
==> e <= r`, |
| 104 |
REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN |
| 105 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * (p1 - x * p2)` THEN ASM_REWRITE_TAC[] THEN |
| 106 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * (a - n)` THEN CONJ_TAC THENL [ |
| 107 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[] THEN |
| 108 |
REWRITE_TAC[real_sub] THEN MATCH_MP_TAC REAL_LE_ADD2 THEN ASM_REWRITE_TAC[REAL_LE_NEG2] THEN |
| 109 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * b:real` THEN ASM_REWRITE_TAC[] THEN |
| 110 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[]; |
| 111 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * t` THEN ASM_REWRITE_TAC[] THEN |
| 112 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[] |
| 113 |
]);; |
| 114 |
|
| 115 |
let mk_log_bound_tables log_bound_th = |
| 116 |
let log_bound = (SPEC_ALL o |
| 117 |
REWRITE_RULE[poly_f_even; poly_f_odd; GSYM REAL_POW_2; REAL_POW_POW] o |
| 118 |
REWRITE_RULE[sum_eq_poly_f] o |
| 119 |
REWRITE_RULE[alt_sum_eq_poly_f; real_div]) log_bound_th in |
| 120 |
let reduce_rule = CONV_RULE (DEPTH_CONV |
| 121 |
(FIRST_CONV [NUM_SUC_CONV; NUM_ADD_CONV; NUM_MULT_CONV])) in |
| 122 |
let find_poly_f = rev o find_terms (fun tm -> try (rator o rator) tm = `poly_f` |
| 123 |
with Failure _ -> false) in |
| 124 |
fun pp n -> |
| 125 |
let n_tm = mk_small_numeral n in |
| 126 |
let th0 = INST[n_tm, n_var_num] log_bound in |
| 127 |
let th1 = CONV_RULE NUM_REDUCE_CONV th0 in |
| 128 |
let poly_tms0 = find_poly_f (concl th1) in |
| 129 |
let ns_th = map (REDEPTH_CONV num_CONV o rand o rand o rator) poly_tms0 in |
| 130 |
let th2 = REWRITE_RULE(ns_th @ [TABLE_SUC; TABLE_0; APPEND]) th1 in |
| 131 |
let bound_th = (REWRITE_RULE[REAL_INV_1] o reduce_rule) th2 in |
| 132 |
let poly_tms = find_poly_f (concl bound_th) in |
| 133 |
let cs_tms = map (rand o rator) poly_tms in |
| 134 |
let cs_lists = map (mk_poly_coeffs pp) cs_tms in |
| 135 |
bound_th, zip cs_tms cs_lists;; |
| 136 |
|
| 137 |
(* Computes i such that x^i / i <= base^(-(p + 1)) and cond(i) *) |
| 138 |
let n_of_p_log x pp cond = |
| 139 |
let t = (float_of_int Arith_num.arith_base) ** (float_of_int (-pp - 1)) in |
| 140 |
let rec try_i i = |
| 141 |
let _ = if i > 50 then failwith "n_of_p_exp: cannot find i" else () in |
| 142 |
if cond i then |
| 143 |
(* let d = float_of_int (2 * i + 1) in *) |
| 144 |
let d = float_of_int i in |
| 145 |
let r = (x ** d) /. d in |
| 146 |
if r <= t then i else try_i (i + 1) |
| 147 |
else |
| 148 |
try_i (i + 1) |
| 149 |
in |
| 150 |
try_i 0;; |
| 151 |
|
| 152 |
(* |
| 153 |
|
| 154 |
let sq = float_sqrt;; |
| 155 |
let t = sq (1.0 -. 1.0 /. 3.0) -. 1.0;; |
| 156 |
let t = float_sqrt 2.0 -. 1.0;; |
| 157 |
let t = float_sqrt 2.0 /. 2.0 -. 1.0;; |
| 158 |
t /. (2.0 +. t);; |
| 159 |
|
| 160 |
n_of_p_log 0.11 20 (fun i -> true);; |
| 161 |
|
| 162 |
*) |
| 163 |
|
| 164 |
(* Makes the table of exp coefficients assuming the interval [0, exp_max_x] *) |
| 165 |
let mk_log_lower pp = |
| 166 |
let n = n_of_p_log log_max_x pp (fun i -> i land 1 = 1) in |
| 167 |
let bound_th0, css = mk_log_bound_tables log_poly_lower_bound (pp + 1) n in |
| 168 |
let cs1, cs2 = pair_of_list css in |
| 169 |
let RULE2 = UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL in |
| 170 |
let bound_th = (RULE2 o MATCH_MP bound_low_trans o th_rule o |
| 171 |
GEN_REWRITE_RULE (LAND_CONV o ONCE_DEPTH_CONV) [GSYM float1_eq]) bound_th0 in |
| 172 |
bound_th, cs1, cs2;; |
| 173 |
|
| 174 |
(* Makes the table of exp coefficients assuming the interval [0, exp_max_x] *) |
| 175 |
let mk_log_upper pp = |
| 176 |
let n = n_of_p_log log_max_x pp (fun i -> i land 1 = 0) in |
| 177 |
let bound_th0, css = mk_log_bound_tables log_poly_upper_bound (pp + 1) n in |
| 178 |
let cs1, cs2 = pair_of_list css in |
| 179 |
let RULE2 = UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL in |
| 180 |
let bound_th = (RULE2 o MATCH_MP bound_high_trans o th_rule o |
| 181 |
GEN_REWRITE_RULE (LAND_CONV o ONCE_DEPTH_CONV) [GSYM float1_eq]) bound_th0 in |
| 182 |
bound_th, cs1, cs2;; |
| 183 |
|
| 184 |
let th, _, _ = mk_log_upper 1;; |
| 185 |
|
| 186 |
(* Computes a lower bound of log(1 + x) for the given floating-point number 0 <= x < 1. *) |
| 187 |
(* The given number should be relatively small (|x| <= log_max_x) to get a good results. *) |
| 188 |
let log1_pos_low = |
| 189 |
let table = Array.init 21 mk_log_lower in |
| 190 |
fun pp x_tm -> |
| 191 |
let bound_th, cs1, cs2 = table.(pp) in |
| 192 |
let pp = pp + 1 in |
| 193 |
let x_pow2_high = eval_pow2_high pp x_tm and |
| 194 |
x_pow2_low = eval_pow2_low pp x_tm in |
| 195 |
let p1_low_th = eval_low_poly_f_pos_pos pp cs1 x_pow2_low and |
| 196 |
p2_high_th = eval_high_poly_f_pos_pos pp cs2 x_pow2_high in |
| 197 |
let a_tm = (rand o rator o concl) p1_low_th in |
| 198 |
let b_tm = (rand o rand o concl) p2_high_th in |
| 199 |
let xb_le_n = float_mul_hi pp x_tm b_tm in |
| 200 |
let n_tm = (rand o concl) xb_le_n in |
| 201 |
let t_le_an = float_sub_lo pp a_tm n_tm in |
| 202 |
let t_tm = (rand o rator o concl) t_le_an in |
| 203 |
let r_le_xt = float_mul_lo pp x_tm t_tm in |
| 204 |
let r_tm = rand (rator (concl r_le_xt)) in |
| 205 |
let cmp_1 = EQT_ELIM (float_lt x_tm one_float) in |
| 206 |
let cmp_0 = EQT_ELIM (float_ge0 x_tm) in |
| 207 |
let th0 = INST[a_tm, a_var_real; b_tm, b_var_real; n_tm, n_var_real; |
| 208 |
t_tm, t_var_real; r_tm, r_var_real; x_tm, x_var_real] bound_th in |
| 209 |
itlist MY_PROVE_HYP [p1_low_th; p2_high_th; xb_le_n; t_le_an; r_le_xt; cmp_0; cmp_1] th0;; |
| 210 |
|
| 211 |
(* Computes an upper bound of log(1 + x) for the given floating-point number 0 <= x < 1. *) |
| 212 |
(* The given number should be relatively small (|x| <= log_max_x) to get a good results. *) |
| 213 |
let log1_pos_high = |
| 214 |
let table = Array.init 21 mk_log_upper in |
| 215 |
fun pp x_tm -> |
| 216 |
let bound_th, cs1, cs2 = table.(pp) in |
| 217 |
let pp = pp + 1 in |
| 218 |
let x_pow2_high = eval_pow2_high pp x_tm and |
| 219 |
x_pow2_low = eval_pow2_low pp x_tm in |
| 220 |
let p1_high_th = eval_high_poly_f_pos_pos pp cs1 x_pow2_high in |
| 221 |
let p2_low_th = eval_low_poly_f_pos_pos pp cs2 x_pow2_low in |
| 222 |
let a_tm = (rand o rand o concl) p1_high_th in |
| 223 |
let b_tm = (rand o rator o concl) p2_low_th in |
| 224 |
let n_le_xb = float_mul_lo pp x_tm b_tm in |
| 225 |
let n_tm = (rand o rator o concl) n_le_xb in |
| 226 |
let an_le_t = float_sub_hi pp a_tm n_tm in |
| 227 |
let t_tm = (rand o concl) an_le_t in |
| 228 |
let xt_le_r = float_mul_hi pp x_tm t_tm in |
| 229 |
let r_tm = rand (concl xt_le_r) in |
| 230 |
let cmp_1 = EQT_ELIM (float_lt x_tm one_float) in |
| 231 |
let cmp_0 = EQT_ELIM (float_ge0 x_tm) in |
| 232 |
let th0 = INST[a_tm, a_var_real; b_tm, b_var_real; n_tm, n_var_real; |
| 233 |
t_tm, t_var_real; r_tm, r_var_real; x_tm, x_var_real] bound_th in |
| 234 |
itlist MY_PROVE_HYP [p1_high_th; p2_low_th; n_le_xb; an_le_t; xt_le_r; cmp_1; cmp_0] th0;; |
| 235 |
|
| 236 |
let log2_eq = prove |
| 237 |
(`log (&2) = &2 * log (&1 + &1 / &4) + log (&1 + &7 / &25)`, |
| 238 |
SIMP_TAC[GSYM LOG_POW; REAL_ARITH `&0 < &1 + &1 / &4`] THEN |
| 239 |
SIMP_TAC[GSYM LOG_MUL; REAL_ARITH `&0 < (&1 + &1 / &4) pow 2 /\ &0 < &1 + &7 / &25`] THEN |
| 240 |
AP_TERM_TAC THEN REAL_ARITH_TAC);; |