Debian Codegraph @

Formal_ineqs/trig/unused.hl

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