Debian Codegraph @

Formal_ineqs/trig/cos_bounds_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: cos *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/trig/sin_cos.hl";;
14 needs "Formal_ineqs/trig/poly_eval.hl";;
15
16 module type Cos_bounds_eval_sig =
17 sig
18 val float_cos_high_raw : int -> term -> thm
19 val float_cos_low_raw : int -> term -> thm
20 end;;
21
22 module Cos_bounds_eval : Cos_bounds_eval_sig = struct
23
24 open Misc_functions;;
25 open Sin_cos;;
26 open More_list;;
27 open Poly;;
28 open Poly_eval;;
29 open Interval_arith;;
30 open Float_theory;;
31 open Arith_float;;
32 open More_float;;
33 open Misc_vars;;
34
35 prioritize_real();;
36
37 let th_rule = UNDISCH_ALL o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL;;
38 let case_rule = PURE_REWRITE_RULE[NOT_CLAUSES; GSYM float1_eq; FLOAT_NEG] o th_rule;;
39
40 let cos_high_trivial = (case_rule o prove)
41 (`cos x <= &1`,
42 REWRITE_TAC[COS_BOUNDS]);;
43
44 let cos_low_trivial = (case_rule o prove)
45 (`-- &1 <= cos x`,
46 REWRITE_TAC[COS_BOUNDS]);;
47
48 let bound_high_transformation = prove(`!c x p1 p2 a b m n r. c <= p1 - x * p2 ==>
49 interval_arith p1 (&0, a) /\
50 interval_arith b (&0, p2) /\
51 interval_arith m (&0, x) /\
52 n <= m * b /\
53 a - n <= r
54 ==> c <= r`,
55 REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN
56 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a - n:real` THEN ASM_REWRITE_TAC[] THEN
57 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `p1 - x * p2:real` THEN ASM_REWRITE_TAC[] THEN
58 REWRITE_TAC[real_sub] THEN MATCH_MP_TAC REAL_LE_ADD2 THEN ASM_REWRITE_TAC[REAL_LE_NEG2] THEN
59 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `m * b:real` THEN ASM_REWRITE_TAC[] THEN
60 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[]);;
61
62 let bound_low_transformation = prove(`!c x p1 p2 a b m n r. p1 - x * p2 <= c ==>
63 interval_arith a (&0, p1) /\
64 interval_arith p2 (&0, b) /\
65 interval_arith x (&0, m) /\
66 m * b <= n /\
67 r <= a - n
68 ==> r <= c`,
69 REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN
70 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a - n:real` THEN ASM_REWRITE_TAC[] THEN
71 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `p1 - x * p2:real` THEN ASM_REWRITE_TAC[] THEN
72 REWRITE_TAC[real_sub] THEN MATCH_MP_TAC REAL_LE_ADD2 THEN ASM_REWRITE_TAC[REAL_LE_NEG2] THEN
73 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `m * b:real` THEN ASM_REWRITE_TAC[] THEN
74 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[]);;
75
76
77 let mk_cos_bound_tables cos_bound_th =
78 let cos_bound = (SPEC_ALL o
79 REWRITE_RULE[poly_f_even; poly_f_odd; GSYM REAL_POW_2; REAL_POW_POW] o
80 REWRITE_RULE[alt_sum_eq_poly_f_even; real_div]) cos_bound_th in
81 (* This rule does not simplify factorials *)
82 let reduce_rule = CONV_RULE (DEPTH_CONV (FIRST_CONV [NUM_SUC_CONV; NUM_ADD_CONV; NUM_MULT_CONV])) in
83 let find_poly_f = rev o find_terms (fun tm ->
84 try (rator o rator) tm = `poly_f` with Failure _ -> false) in
85 fun pp n ->
86 let n_tm = mk_small_numeral n in
87 let th0 = INST[n_tm, n_var_num] cos_bound in
88 let th1 = CONV_RULE NUM_REDUCE_CONV th0 in
89 let poly_tms0 = find_poly_f (concl th1) in
90 let ns_th = map (REDEPTH_CONV num_CONV o rand o rand o rator) poly_tms0 in
91 let th2 = REWRITE_RULE(ns_th @ [TABLE_SUC; TABLE_0; APPEND]) th1 in
92 let bound_th = reduce_rule th2 in
93 let poly_tms = find_poly_f (concl bound_th) in
94 let cs_tms = map (rand o rator) poly_tms in
95 let cs_lists = map (mk_poly_coeffs pp) cs_tms in
96 bound_th, zip cs_tms cs_lists;;
97
98
99 (* Computes x^k / k! *)
100 let rec x_pow_over_fact x k =
101 if k <= 0 then 1. else
102 x /. (float_of_int k) *. x_pow_over_fact x (k - 1);;
103
104
105 (* Computes i such that x^(2(i + 1))/(2(i + 1))! <= base^(-(p + 1)) and cond(i) *)
106 let n_of_p_cos x pp cond =
107 let t = (float_of_int Arith_num.arith_base) ** (float_of_int (-pp - 1)) in
108 let rec try_i i =
109 let _ = if i > 50 then failwith "n_of_p_cos: cannot find i" else () in
110 if cond i then
111 let r = x_pow_over_fact x (2 * (i + 1)) in
112 if r <= t then i else try_i (i + 1)
113 else
114 try_i (i + 1)
115 in
116 try_i 0;;
117
118 (* Makes the table of cosine coefficients assuming the interval [-pi/2, pi/2] *)
119 (* TODO: restrict cos to [-pi/4, pi/4] *)
120 let mk_cos_upper pp =
121 let n = n_of_p_cos (2.0 *. atan 1.0) pp (fun i -> i land 1 = 0) in
122 let bound_th0, css = mk_cos_bound_tables cos_poly_upper_bound (pp + 1) n in
123 let cs1, cs2 = pair_of_list css in
124 let RULE2 = UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL in
125 let bound_th = (RULE2 o MATCH_MP bound_high_transformation) bound_th0 in
126 bound_th, cs1, cs2;;
127
128 (* Makes the table of cosine coefficients assuming the interval [-pi/2, pi/2] *)
129 (* TODO: restrict cos to [-pi/4, pi/4] *)
130 let mk_cos_lower pp =
131 let n = n_of_p_cos (2.0 *. atan 1.0) pp (fun i -> i land 1 = 1) in
132 let bound_th0, css = mk_cos_bound_tables cos_poly_lower_bound (pp + 1) n in
133 let cs1, cs2 = pair_of_list css in
134 let RULE2 = UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL in
135 let bound_th = (RULE2 o MATCH_MP bound_low_transformation) bound_th0 in
136 bound_th, cs1, cs2;;
137
138 (* Computes an upper bound of cosine at the given floating-point number. *)
139 (* The given number should be relatively small (|x| <= pi/2) to get a good results. *)
140 let float_cos_high_raw =
141 let cos_upper_table = Array.init 21 mk_cos_upper in
142 fun pp x_tm ->
143 let bound_th, cs1, cs2 = cos_upper_table.(pp) in
144 let pp = pp + 1 in
145 let x_pow4_high = eval_pow4_high pp x_tm in
146 let x_pow2_low, x_pow4_low = eval_pow2_pow4_low pp x_tm in
147 let p1_high_th = eval_high_poly_f_pos_pos pp cs1 x_pow4_high in
148 let p2_low_th = eval_low_poly_f_pos_pos pp cs2 x_pow4_low in
149 let a_tm = (rand o rand o concl) p1_high_th in
150 let b_tm = (rand o rator o concl) p2_low_th in
151 let m_tm = (rand o rator o concl) x_pow2_low in
152 let n_le_mb_th = float_mul_lo pp m_tm b_tm in
153 let n_tm = (rand o rator o concl) n_le_mb_th in
154 let an_le_r_th = float_sub_hi pp a_tm n_tm in
155 let r_tm = (rand o concl) an_le_r_th in
156 let cmp_1 = float_le r_tm one_float in
157 if (fst o dest_const o rand o concl) cmp_1 = "F" then
158 INST[x_tm, x_var_real] cos_high_trivial
159 else
160 let th0 = INST[a_tm, a_var_real; b_tm, b_var_real; m_tm, m_var_real;
161 n_tm, n_var_real; r_tm, r_var_real; x_tm, x_var_real] bound_th in
162 itlist MY_PROVE_HYP [p1_high_th; p2_low_th; x_pow2_low; n_le_mb_th; an_le_r_th] th0;;
163
164 (* Computes a lower bound of cosine at the given floating-point number. *)
165 (* The given number should be relatively small (|x| <= pi/2) to get a good results. *)
166 let float_cos_low_raw =
167 let cos_lower_table = Array.init 21 mk_cos_lower in
168 let neg_one_tm = mk_float (-1) 0 in
169 fun pp x_tm ->
170 let bound_th, cs1, cs2 = cos_lower_table.(pp) in
171 let pp = pp + 1 in
172 let x_pow2_high, x_pow4_high = eval_pow2_pow4_high pp x_tm and
173 x_pow4_low = eval_pow4_low pp x_tm in
174 let p1_low_th = eval_low_poly_f_pos_pos pp cs1 x_pow4_low and
175 p2_high_th = eval_high_poly_f_pos_pos pp cs2 x_pow4_high in
176 let a_tm = (rand o rator o concl) p1_low_th in
177 let b_tm = (rand o rand o concl) p2_high_th in
178 let m_tm = (rand o rand o concl) x_pow2_high in
179 let mb_le_n = float_mul_hi pp m_tm b_tm in
180 let n_tm = (rand o concl) mb_le_n in
181 let r_le_an = float_sub_lo pp a_tm n_tm in
182 let r_tm = (rand o rator o concl) r_le_an in
183 let cmp_1 = float_le neg_one_tm r_tm in
184 if (fst o dest_const o rand o concl) cmp_1 = "F" then
185 INST[x_tm, x_var_real] cos_low_trivial
186 else
187 let th0 = INST[a_tm, a_var_real; b_tm, b_var_real; m_tm, m_var_real;
188 n_tm, n_var_real; r_tm, r_var_real; x_tm, x_var_real] bound_th in
189 itlist MY_PROVE_HYP [p1_low_th; p2_high_th; x_pow2_high; mb_le_n; r_le_an] th0;;
190
191
192 end;;
193
194 (*
195 let pp = 10;;
196 let x_tm = (rand o rand o concl o float_interval_const pp) `#3.1415926 / &2`;;
197 let x_tm = (rand o rand o concl o float_interval_const pp) `&1`;;
198
199 float_cos_high_raw 10 x_tm;;
200 float_cos_low_raw 10 x_tm;;
201 (* 0.492, 54030230603, real = 0.54030230586 *)
202 test 100 (float_cos_high_raw 10) x_tm;;
203
204 let x_th = Float_atn.pi_approx_array.(10);;
205 Float_atn.float_interval_atn 10 x_th;;
206
207 test 100 (Float_atn.float_interval_atn 10) x_th;;
208 *)