Debian Codegraph @

Formal_ineqs/trig/matan_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: matan, dmatan, ddmatan *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/arith/more_float.hl";;
14 needs "Formal_ineqs/trig/matan.hl";;
15 needs "Formal_ineqs/trig/atn_eval.hl";;
16
17 module type Matan_eval_sig =
18 sig
19 val float_interval_matan : int -> thm -> thm
20 val float_interval_dmatan : int -> thm -> thm
21 val float_interval_ddmatan : int -> thm -> thm
22 end;;
23
24
25 module Matan_eval : Matan_eval_sig = struct
26
27 open Misc_functions;;
28 open Float_theory;;
29 open Interval_arith;;
30 open More_float;;
31 open Arith_float;;
32 open Atn_eval;;
33 open Matan;;
34 open Misc_vars;;
35
36 prioritize_real();;
37
38 (* Creates an interval approximation of the given decimal term *)
39 let mk_float_interval_decimal =
40 let DECIMAL' = SPEC_ALL DECIMAL in
41 fun pp decimal_tm ->
42 let n_tm, d_tm = dest_binary "DECIMAL" decimal_tm in
43 let n, d = dest_numeral n_tm, dest_numeral d_tm in
44 let n_int, d_int = mk_float_interval_num n, mk_float_interval_num d in
45 let int = float_interval_div pp n_int d_int in
46 let eq_th = INST[n_tm, x_var_num; d_tm, y_var_num] DECIMAL' in
47 norm_interval int eq_th;;
48
49
50 (* -------------------------------- *)
51 (* Theorems for computations *)
52 (* -------------------------------- *)
53
54 let th_rule = UNDISCH_ALL o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL;;
55
56 let one_interval = mk_float_interval_small_num 1 and
57 three_interval = mk_float_interval_small_num 3 and
58 five_interval = mk_float_interval_small_num 5 and
59 seven_float = mk_float 7 0 and
60 two_float = mk_float 2 0 and
61 one_float = mk_float 1 0;;
62
63 let interval_neg_02 = float_interval_neg (mk_float_interval_decimal 10 `#0.2`);;
64 let interval_09 = mk_float_interval_decimal 10 `#0.9`;;
65 let interval_1e8 = mk_float_interval_decimal 10 `#0.00000001`;;
66 let float_1e8 = (fst o dest_pair o snd o dest_interval_arith o concl) interval_1e8;;
67
68 (* matan *)
69
70 let matan_gt0 = (th_rule o prove)(
71 `!x. interval_arith x (lo, hi) /\ (&0 < lo <=> T) /\
72 interval_arith (atn (sqrt x) / sqrt x) bounds
73 ==> interval_arith (matan x) bounds`,
74 REWRITE_TAC[interval_arith; matan] THEN REPEAT STRIP_TAC THEN
75 SUBGOAL_THEN `~(x = &0) /\ x > &0` ASSUME_TAC THENL [
76 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
77 ALL_TAC
78 ] THEN
79 ASM_REWRITE_TAC[]);;
80
81
82 let matan_abs1 =
83 let aux_th = (REWRITE_CONV[FLOAT_OF_NUM; min_exp_def] THENC
84 DEPTH_CONV Arith_nat.NUMERAL_TO_NUM_CONV THENC
85 REWRITE_CONV[Arith_num.NUM_THM]) `r1 <= &1 - u` in
86 (th_rule o PURE_REWRITE_RULE[SYM (FLOAT_TO_NUM_CONV seven_float); aux_th] o prove)(
87 `!x.
88 interval_arith x (lo, hi) /\
89 interval_arith ((&1 - x / &3) + (x * x) / &5) (a, b) /\
90 iabs (lo, hi) = u /\
91 u <= #0.9 /\
92 u * u <= u2 /\
93 u2 * u <= u3 /\
94 r1 <= &1 - u /\
95 r2 <= &7 * r1 /\ (&0 < r2 <=> T) /\
96 u3 / r2 <= e /\
97 low <= a - e /\
98 b + e <= high
99 ==> interval_arith (matan x) (low, high)`,
100 REWRITE_TAC[interval_arith; GSYM IMP_IMP; iabs] THEN GEN_TAC THEN REPEAT DISCH_TAC THEN
101 SUBGOAL_THEN `abs x <= u` (LABEL_TAC "u") THENL [
102 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
103 ALL_TAC
104 ] THEN
105 MP_TAC (SPECL[`2`; `x:real`] matan_abs1_bound) THEN ANTS_TAC THENL [
106 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
107 ALL_TAC
108 ] THEN
109 REWRITE_TAC[TWO; ONE; SUM_CLAUSES_NUMSEG] THEN
110 CONV_TAC NUM_REDUCE_CONV THEN
111 REWRITE_TAC[real_pow; REAL_POW_1; REAL_POW_2] THEN CONV_TAC REAL_RAT_REDUCE_CONV THEN
112 MATCH_MP_TAC (REAL_ARITH `low <= s - r /\ s + r <= high ==> (abs (m - s) <= r ==> low <= m /\ m <= high)`) THEN
113 ABBREV_TAC `e2 = abs x pow 3 / (&7 * (&1 - abs x))` THEN
114 REWRITE_TAC[REAL_ARITH `(&1 + -- &1 / &3 * x) + &1 / &5 * x * x = &1 - x / &3 + (x * x) / &5`] THEN
115 SUBGOAL_THEN `e2 <= e:real` ASSUME_TAC THENL [
116 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `u3 / r2:real` THEN ASM_REWRITE_TAC[] THEN
117 EXPAND_TAC "e2" THEN
118 SUBGOAL_THEN `&0 < &7 * (&1 - abs x)` ASSUME_TAC THENL [
119 MATCH_MP_TAC REAL_LT_MUL THEN
120 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
121 ALL_TAC
122 ] THEN
123 ASM_SIMP_TAC[RAT_LEMMA4] THEN
124 MATCH_MP_TAC REAL_LE_MUL2 THEN REPEAT CONJ_TAC THENL [
125 MATCH_MP_TAC REAL_POW_LE THEN REAL_ARITH_TAC;
126 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `u2 * u:real` THEN ASM_REWRITE_TAC[] THEN
127 REWRITE_TAC[ARITH_RULE `3 = SUC 2`; real_pow; REAL_ARITH `u2 * u = u * u2`] THEN
128 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[REAL_ABS_POS; REAL_LE_POW_2] THEN
129 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `u * u:real` THEN ASM_REWRITE_TAC[] THEN
130 REWRITE_TAC[GSYM REAL_POW_2; GSYM REAL_LE_SQUARE_ABS] THEN
131 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
132 MATCH_MP_TAC REAL_LT_IMP_LE THEN ASM_REWRITE_TAC[];
133 ALL_TAC
134 ] THEN
135 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&7 * r1` THEN ASM_REWRITE_TAC[] THEN
136 MATCH_MP_TAC REAL_LE_LMUL THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THEN
137 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1 - u` THEN ASM_REWRITE_TAC[] THEN
138 ASM_REWRITE_TAC[REAL_ARITH `&1 - u <= &1 - x <=> x <= u`];
139 ALL_TAC
140 ] THEN
141 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);;
142
143
144 (* dmatan *)
145
146 let dmatan_gt0 = (th_rule o prove)(
147 `!x. interval_arith x (lo, hi) /\ (&0 < lo <=> T) /\
148 interval_arith (inv ((&2 * x) * (x + &1)) - atn (sqrt x) / ((&2 * x) * sqrt x)) bounds
149 ==> interval_arith (dmatan x) bounds`,
150 REWRITE_TAC[interval_arith; dmatan] THEN REPEAT STRIP_TAC THEN
151 SUBGOAL_THEN `&0 < x` ASSUME_TAC THENL [
152 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
153 ALL_TAC
154 ] THEN
155 ASM_SIMP_TAC[matan_real_derivative_gt0; REAL_MUL_ASSOC]);;
156
157
158 let dmatan_abs1 =
159 let aux_conv = (REWRITE_CONV[FLOAT_OF_NUM; min_exp_def] THENC
160 DEPTH_CONV Arith_nat.NUMERAL_TO_NUM_CONV THENC
161 REWRITE_CONV[Arith_num.NUM_THM]) in
162 let aux1 = aux_conv `r1 <= &1 - u` and
163 aux2 = aux_conv `r2 <= &2 * r1` in
164 (th_rule o PURE_REWRITE_RULE[aux1; aux2] o prove)(
165 `!x.
166 interval_arith x (lo, hi) /\
167 interval_arith (&2 * (x / &5) - &1 / &3) (a, b) /\
168 iabs (lo, hi) = u /\
169 u <= #0.9 /\
170 u * u <= u2 /\
171 r1 <= &1 - u /\
172 r2 <= &2 * r1 /\ (&0 < r2 <=> T) /\
173 u2 / r2 <= e /\
174 low <= a - e /\
175 b + e <= high
176 ==> interval_arith (dmatan x) (low, high)`,
177 REWRITE_TAC[interval_arith; GSYM IMP_IMP; iabs; dmatan] THEN GEN_TAC THEN REPEAT DISCH_TAC THEN
178 SUBGOAL_THEN `abs x <= u` (LABEL_TAC "u") THENL [
179 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
180 ALL_TAC
181 ] THEN
182 MP_TAC (SPECL[`x:real`; `1`] matan_real_derivative_abs1_bound) THEN ANTS_TAC THENL [
183 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
184 ALL_TAC
185 ] THEN
186 REWRITE_TAC[ONE; SUM_CLAUSES_NUMSEG] THEN CONV_TAC NUM_REDUCE_CONV THEN
187 REWRITE_TAC[real_pow; REAL_POW_1; REAL_POW_2] THEN CONV_TAC REAL_RAT_REDUCE_CONV THEN
188 MATCH_MP_TAC (REAL_ARITH `low <= s - r /\ s + r <= high ==> (abs (m - s) <= r ==> low <= m /\ m <= high)`) THEN
189 ABBREV_TAC `e2 = (abs x * abs x) / (&2 * (&1 - abs x))` THEN
190 REWRITE_TAC[REAL_ARITH `-- &1 / &3 + &2 / &5 * x = &2 * x / &5 - &1 / &3`] THEN
191 SUBGOAL_THEN `e2 <= e:real` ASSUME_TAC THENL [
192 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `u2 / r2:real` THEN ASM_REWRITE_TAC[] THEN
193 EXPAND_TAC "e2" THEN
194 SUBGOAL_THEN `&0 < &2 * (&1 - abs x)` ASSUME_TAC THENL [
195 MATCH_MP_TAC REAL_LT_MUL THEN
196 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
197 ALL_TAC
198 ] THEN
199 ASM_SIMP_TAC[RAT_LEMMA4] THEN
200 MATCH_MP_TAC REAL_LE_MUL2 THEN REPEAT CONJ_TAC THENL [
201 MATCH_MP_TAC REAL_LE_MUL THEN REAL_ARITH_TAC;
202 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `u * u:real` THEN ASM_REWRITE_TAC[] THEN
203 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[REAL_ABS_POS];
204 MATCH_MP_TAC REAL_LT_IMP_LE THEN ASM_REWRITE_TAC[];
205 ALL_TAC
206 ] THEN
207 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&2 * r1` THEN ASM_REWRITE_TAC[] THEN
208 MATCH_MP_TAC REAL_LE_LMUL THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THEN
209 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1 - u` THEN ASM_REWRITE_TAC[] THEN
210 ASM_REWRITE_TAC[REAL_ARITH `&1 - u <= &1 - x <=> x <= u`];
211 ALL_TAC
212 ] THEN
213 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);;
214
215
216 (* ddmatan *)
217
218 let ddmatan_ge_neg02 = (th_rule o prove)(
219 `!x. interval_arith x (lo, hi) /\
220 -- #0.2 <= lo /\
221 interval_arith (#0.65) (a, b) /\
222 b2 = --b
223 ==> interval_arith (ddmatan x) (b2, b)`,
224 REWRITE_TAC[interval_arith; ddmatan] THEN GEN_TAC THEN STRIP_TAC THEN
225 SUBGOAL_THEN `-- #0.2 <= x` ASSUME_TAC THENL [
226 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
227 ALL_TAC
228 ] THEN
229 MP_TAC (SPEC `x:real` matan_d2_bound) THEN ASM_REWRITE_TAC[] THEN
230 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);;
231
232
233 (* -------------------------------- *)
234 (* Procedures *)
235 (* -------------------------------- *)
236
237 (* matan *)
238
239 let float_interval_matan =
240 let e_var_real = `e:real` and
241 u_var_real = `u:real` and
242 u2_var_real = `u2:real` and
243 u3_var_real = `u3:real` and
244 r1_var_real = `r1:real` and
245 r2_var_real = `r2:real` in
246 fun pp x_th ->
247 let x_tm, bounds = dest_interval_arith (concl x_th) in
248 let ltm, hi_tm = dest_comb bounds in
249 let lo_tm = rand ltm in
250 let flag, _ = float_prove_le lo_tm float_1e8 in
251 if flag then
252 (* Use series *)
253 let u_eq = float_iabs bounds in
254 let u_tm = rand (concl u_eq) in
255 let flag, u_le_09 = float_prove_le_interval u_tm interval_09 in
256 if not flag then
257 failwith "float_interval_matan: the argument is out of range"
258 else
259 let s_th =
260 let ( * ) = float_interval_mul pp and
261 ( / ) = float_interval_div pp and
262 ( + ) = float_interval_add pp and
263 ( - ) = float_interval_sub pp in
264 (one_interval - x_th / three_interval) + (x_th * x_th) / five_interval in
265 let a_tm, b_tm = dest_pair (rand (concl s_th)) in
266 let uu_le_u2 = float_mul_hi pp u_tm u_tm in
267 let u2_tm = rand (concl uu_le_u2) in
268 let u2u_le_u3 = float_mul_hi pp u2_tm u_tm in
269 let u3_tm = rand (concl u2u_le_u3) in
270 let r1_le_1u = float_sub_lo pp one_float u_tm in
271 let r1_tm = rand (rator (concl r1_le_1u)) in
272 let r2_le_7r1 = float_mul_lo pp seven_float r1_tm in
273 let r2_tm = rand (rator (concl r2_le_7r1)) in
274 let u3r2_le_e = float_div_hi pp u3_tm r2_tm in
275 let e_tm = rand (concl u3r2_le_e) in
276 let low_le = float_sub_lo pp a_tm e_tm and
277 high_ge = float_add_hi pp b_tm e_tm in
278 let low_tm = rand (rator (concl low_le)) and
279 high_tm = rand (concl high_ge) in
280 let r2_gt0 = float_gt0 r2_tm in
281 let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real;
282 a_tm, a_var_real; b_tm, b_var_real; e_tm, e_var_real;
283 u_tm, u_var_real; u2_tm, u2_var_real; u3_tm, u3_var_real;
284 r1_tm, r1_var_real; r2_tm, r2_var_real;
285 low_tm, low_var_real; high_tm, high_var_real] matan_abs1 in
286 itlist MY_PROVE_HYP [x_th; s_th; u_eq; u_le_09; uu_le_u2; u2u_le_u3;
287 r1_le_1u; r2_le_7r1; u3r2_le_e;
288 low_le; high_ge; r2_gt0] th0
289 else
290 (* atn (sqrt x) / (sqrt x) *)
291 let lo_gt0 = float_gt0 lo_tm in
292 let r = float_interval_sqrt pp x_th in
293 let atn_r = float_interval_atn pp r in
294 let th1 = float_interval_div pp atn_r r in
295 let bounds_tm = rand (concl th1) in
296 let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real;
297 bounds_tm, bounds_var] matan_gt0 in
298 itlist MY_PROVE_HYP [x_th; lo_gt0; th1] th0;;
299
300
301 (* dmatan *)
302
303 let float_interval_dmatan =
304 let e_var_real = `e:real` and
305 u_var_real = `u:real` and
306 u2_var_real = `u2:real` and
307 r1_var_real = `r1:real` and
308 r2_var_real = `r2:real` in
309 fun pp x_th ->
310 let x_tm, bounds = dest_interval_arith (concl x_th) in
311 let ltm, hi_tm = dest_comb bounds in
312 let lo_tm = rand ltm in
313 let flag, _ = float_prove_le lo_tm float_1e8 in
314 if flag then
315 (* Use series *)
316 let u_eq = float_iabs bounds in
317 let u_tm = rand (concl u_eq) in
318 let flag, u_le_09 = float_prove_le_interval u_tm interval_09 in
319 if not flag then
320 failwith "float_interval_dmatan: the argument is out of range"
321 else
322 let s_th =
323 let ( * ) = float_interval_mul pp and
324 ( / ) = float_interval_div pp and
325 ( - ) = float_interval_sub pp in
326 (two_interval * (x_th / five_interval) - one_interval / three_interval) in
327 let a_tm, b_tm = dest_pair (rand (concl s_th)) in
328 let uu_le_u2 = float_mul_hi pp u_tm u_tm in
329 let u2_tm = rand (concl uu_le_u2) in
330 let r1_le_1u = float_sub_lo pp one_float u_tm in
331 let r1_tm = rand (rator (concl r1_le_1u)) in
332 let r2_le_2r1 = float_mul_lo pp two_float r1_tm in
333 let r2_tm = rand (rator (concl r2_le_2r1)) in
334 let u2r2_le_e = float_div_hi pp u2_tm r2_tm in
335 let e_tm = rand (concl u2r2_le_e) in
336 let low_le = float_sub_lo pp a_tm e_tm and
337 high_ge = float_add_hi pp b_tm e_tm in
338 let low_tm = rand (rator (concl low_le)) and
339 high_tm = rand (concl high_ge) in
340 let r2_gt0 = float_gt0 r2_tm in
341 let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real;
342 a_tm, a_var_real; b_tm, b_var_real; e_tm, e_var_real;
343 u_tm, u_var_real; u2_tm, u2_var_real;
344 r1_tm, r1_var_real; r2_tm, r2_var_real;
345 low_tm, low_var_real; high_tm, high_var_real] dmatan_abs1 in
346 itlist MY_PROVE_HYP [x_th; s_th; u_eq; u_le_09; uu_le_u2;
347 r1_le_1u; r2_le_2r1; u2r2_le_e;
348 low_le; high_ge; r2_gt0] th0
349 else
350 (* inv ((2 * x) * (x + 1)) - atn (sqrt x) / ((2 * x) * (sqrt x)) *)
351 let lo_gt0 = float_gt0 lo_tm in
352 let r = float_interval_sqrt pp x_th in
353 let th1 =
354 let ( * ) = float_interval_mul pp and
355 ( / ) = float_interval_div pp and
356 ( + ) = float_interval_add pp and
357 ( - ) = float_interval_sub pp and
358 atn = float_interval_atn pp and
359 inv = float_interval_inv pp in
360 let two_x = two_interval * x_th in
361 inv (two_x * (x_th + one_interval)) - (atn r / (two_x * r)) in
362 let bounds_tm = rand (concl th1) in
363 let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real;
364 bounds_tm, bounds_var] dmatan_gt0 in
365 itlist MY_PROVE_HYP [x_th; lo_gt0; th1] th0;;
366
367
368 (* ddmatan *)
369
370 let array_065 =
371 let interval = mk_float_interval_decimal 20 `#0.65` in
372 Array.init 20 (fun i -> float_interval_round i interval);;
373
374 let float_interval_ddmatan pp x_th =
375 let x_tm, bounds = dest_interval_arith (concl x_th) in
376 let ltm, hi_tm = dest_comb bounds in
377 let lo_tm = rand ltm in
378 let flag, lo_ge = float_prove_ge_interval lo_tm interval_neg_02 in
379 if not flag then
380 failwith "float_interval_ddmatan: the argument is out of range"
381 else
382 let int065 = array_065.(pp) in
383 let a_tm, b_tm = dest_pair (rand (concl int065)) in
384 let b2_eq = float_neg b_tm in
385 let b2_tm = rand (rator (concl b2_eq)) in
386 let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real;
387 a_tm, a_var_real; b_tm, b_var_real; b2_tm, b2_var_real] ddmatan_ge_neg02 in
388 itlist MY_PROVE_HYP [x_th; lo_ge; int065; b2_eq] th0;;
389
390
391 end;;