Debian Codegraph @

Formal_ineqs/arith/float_pow.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 integer exponents *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/arith/arith_float.hl";;
14
15 module type Float_pow_sig =
16 sig
17 (* pp -> n -> x_tm -> |- x pow n <= r *)
18 val float_pow_hi : int -> int -> term -> thm
19 (* pp -> n -> x_tm -> |- r <= x pow n *)
20 val float_pow_lo : int -> int -> term -> thm
21 (* pp -> n -> x_th -> |- interval_arith (x pow n) (lo, hi) *)
22 val float_interval_pow : int -> int -> thm -> thm
23 end;;
24
25 module Float_pow : Float_pow_sig = struct
26
27 open Arith_nat;;
28 open Interval_arith;;
29 open Float_theory;;
30 open Arith_float;;
31 open Misc_functions;;
32 open Misc_vars;;
33
34 prioritize_real();;
35
36 (* ------------------------------------------------ *)
37 (* Power of a float *)
38 (* ------------------------------------------------ *)
39
40 let RULE = UNDISCH_ALL o Arith_nat.NUMERALS_TO_NUM o
41 PURE_REWRITE_RULE[FLOAT_OF_NUM; min_exp_def; GSYM IMP_IMP] o SPEC_ALL;;
42
43 let float_eq n = SYM (FLOAT_TO_NUM_CONV (mk_float n 0));;
44
45 let th_rule = UNDISCH_ALL o PURE_REWRITE_RULE[FLOAT_OF_NUM; min_exp_def; GSYM IMP_IMP] o SPEC_ALL;;
46
47 let eval_suc i_tm =
48 NUM_SUC_CONV (mk_comb (suc_op_num, i_tm));;
49
50 let eval_eq0 =
51 let eq_const = `(=):num->num->bool` and
52 zero_const = `0` in
53 fun i_tm ->
54 NUM_EQ_CONV (mk_comb (mk_comb (eq_const, i_tm), zero_const));;
55
56 let eval_even =
57 let b0_th = prove(`EVEN (NUMERAL (BIT0 n)) <=> T`, REWRITE_TAC[ARITH_EVEN]) and
58 b1_th = prove(`EVEN (NUMERAL (BIT1 n)) <=> F`, REWRITE_TAC[ARITH_EVEN]) and
59 z_th = prove(`EVEN (NUMERAL _0) <=> T`, REWRITE_TAC[ARITH_EVEN]) in
60 fun i_tm ->
61 let m_tm = rand i_tm in
62 if m_tm = zero_const then
63 z_th
64 else
65 let b_tm, n_tm = dest_comb m_tm in
66 if fst (dest_const b_tm) = "BIT0" then
67 INST[n_tm, n_var_num] b0_th
68 else
69 INST[n_tm, n_var_num] b1_th;;
70
71 let eval_mul2 =
72 let mul2_th = prove(`2 * NUMERAL n = NUMERAL (BIT0 n)`,
73 REWRITE_TAC[ARITH_RULE `2 * a = a + a`; BIT0; NUMERAL]) in
74 fun i_tm ->
75 let n_tm = rand i_tm in
76 INST[n_tm, n_var_num] mul2_th;;
77
78 let float_pow_pos_suc_hi_th = (th_rule o prove)
79 (`float_num F n e pow j <= t /\ float_num F n e * t <= hi /\ SUC j = i
80 ==> float_num F n e pow i <= hi`,
81 STRIP_TAC THEN (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
82 REWRITE_TAC[real_pow] THEN MATCH_MP_TAC REAL_LE_TRANS THEN
83 EXISTS_TAC `float_num F n e * t` THEN ASM_REWRITE_TAC[] THEN
84 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[FLOAT_F_POS; REAL_LE_REFL] THEN
85 MATCH_MP_TAC REAL_POW_LE THEN REWRITE_TAC[FLOAT_F_POS]);;
86
87 let float_pow_pos_double_hi_th = (th_rule o prove)
88 (`float_num F n e pow j <= t /\ t * t <= hi /\ 2 * j = i
89 ==> float_num F n e pow i <= hi`,
90 STRIP_TAC THEN (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
91 ONCE_REWRITE_TAC[MULT_SYM] THEN REWRITE_TAC[GSYM REAL_POW_POW; REAL_POW_2] THEN
92 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `t * t:real` THEN ASM_REWRITE_TAC[] THEN
93 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[FLOAT_F_POS; REAL_LE_REFL] THEN
94 MATCH_MP_TAC REAL_POW_LE THEN REWRITE_TAC[FLOAT_F_POS]);;
95
96 let float_pow0_hi = (REWRITE_RULE[float_eq 1] o prove)
97 (`x pow 0 <= &1`,
98 REWRITE_TAC[real_pow; REAL_LE_REFL]);;
99
100 let float_pow1_hi = (th_rule o prove)
101 (`x pow 1 <= x`,
102 REWRITE_TAC[REAL_POW_1; REAL_LE_REFL]);;
103
104 let float_pow2_hi = (th_rule o prove)
105 (`x * x <= hi ==> x pow 2 <= hi`,
106 REWRITE_TAC[REAL_POW_2]);;
107
108 let float_pow_pos_suc_lo_th = (th_rule o prove)
109 (`float_num F n1 e1 <= float_num F n e pow j /\
110 lo <= float_num F n e * float_num F n1 e1 /\ SUC j = i
111 ==> lo <= float_num F n e pow i`,
112 STRIP_TAC THEN (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
113 REWRITE_TAC[real_pow] THEN MATCH_MP_TAC REAL_LE_TRANS THEN
114 EXISTS_TAC `float_num F n e * float_num F n1 e1` THEN ASM_REWRITE_TAC[] THEN
115 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[FLOAT_F_POS; REAL_LE_REFL]);;
116
117 let float_pow_pos_double_lo_th = (th_rule o prove)
118 (`float_num F n1 e1 <= x pow j /\ lo <= float_num F n1 e1 * float_num F n1 e1 /\ 2 * j = i
119 ==> lo <= x pow i`,
120 STRIP_TAC THEN (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
121 ONCE_REWRITE_TAC[MULT_SYM] THEN REWRITE_TAC[GSYM REAL_POW_POW] THEN
122 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `float_num F n1 e1 pow 2` THEN
123 ASM_REWRITE_TAC[REAL_POW_2] THEN
124 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[FLOAT_F_POS; REAL_LE_REFL]);;
125
126 let float_pow0_lo = (th_rule o REWRITE_RULE[float_eq 1] o prove)
127 (`&1 <= x pow 0`,
128 REWRITE_TAC[real_pow; REAL_LE_REFL]);;
129
130 let float_pow1_lo = (th_rule o prove)
131 (`x <= x pow 1`,
132 REWRITE_TAC[REAL_POW_1; REAL_LE_REFL]);;
133
134 let float_pow2_lo = (th_rule o prove)
135 (`lo <= x * x ==> lo <= x pow 2`,
136 REWRITE_TAC[REAL_POW_2]);;
137
138 let float_pow_neg_even_hi_th = (th_rule o prove)
139 (`(EVEN i <=> T) /\ float_num F n e pow i <= hi
140 ==> float_num T n e pow i <= hi`,
141 STRIP_TAC THEN
142 SUBGOAL_THEN `float_num T n e pow i = float_num F n e pow i` ASSUME_TAC THENL [
143 ASM_REWRITE_TAC[REAL_POW_EQ_EQ; FLOAT_ABS];
144 ALL_TAC
145 ] THEN
146 ASM_REWRITE_TAC[]);;
147
148 let float_pow_neg_even_lo_th = (th_rule o prove)
149 (`(EVEN i <=> T) /\ lo <= float_num F n e pow i
150 ==> lo <= float_num T n e pow i`,
151 STRIP_TAC THEN
152 SUBGOAL_THEN `float_num T n e pow i = float_num F n e pow i` ASSUME_TAC THENL [
153 ASM_REWRITE_TAC[REAL_POW_EQ_EQ; FLOAT_ABS];
154 ALL_TAC
155 ] THEN
156 ASM_REWRITE_TAC[]);;
157
158 let float_pow_neg_odd_hi_th = (th_rule o prove)
159 (`(EVEN i <=> F) /\ float_num F n1 e1 <= float_num F n e pow i
160 ==> float_num T n e pow i <= float_num T n1 e1`,
161 MP_TAC ((GSYM o SPEC `F`) FLOAT_NEG) THEN SIMP_TAC[] THEN REPEAT STRIP_TAC THEN
162 ASM_REWRITE_TAC[REAL_POW_NEG; REAL_LE_NEG2]);;
163
164 let float_pow_neg_odd_lo_th = (th_rule o prove)
165 (`(EVEN i <=> F) /\ float_num F n e pow i <= float_num F n1 e1
166 ==> float_num T n1 e1 <= float_num T n e pow i`,
167 MP_TAC ((GSYM o SPEC `F`) FLOAT_NEG) THEN SIMP_TAC[] THEN REPEAT STRIP_TAC THEN
168 ASM_REWRITE_TAC[REAL_POW_NEG; REAL_LE_NEG2]);;
169
170
171 let float_pow_pos_suc_hi pp x_tm t_th =
172 let _, n_tm, e_tm = dest_float x_tm in
173 let ltm, t_tm = dest_comb (concl t_th) in
174 let j_tm = rand (rand ltm) in
175 let suc_j = eval_suc j_tm in
176 let i_tm = rand (concl suc_j) in
177 let mul_hi = float_mul_hi pp x_tm t_tm in
178 let hi_tm = rand (concl mul_hi) in
179 let th0 = INST[n_tm, n_var_num; e_tm, e_var_num; j_tm, j_var_num;
180 t_tm, t_var_real; hi_tm, hi_var_real;
181 i_tm, i_var_num] float_pow_pos_suc_hi_th in
182 MY_PROVE_HYP t_th (MY_PROVE_HYP mul_hi (MY_PROVE_HYP suc_j th0));;
183
184 let float_pow_pos_suc_lo pp x_tm t_th =
185 let _, n_tm, e_tm = dest_float x_tm in
186 let ltm, rtm = dest_comb (concl t_th) in
187 let t_tm = rand ltm in
188 let j_tm = rand rtm in
189 let _, n1_tm, e1_tm = dest_float t_tm in
190 let suc_j = eval_suc j_tm in
191 let i_tm = rand (concl suc_j) in
192 let mul_lo = float_mul_lo pp x_tm t_tm in
193 let lo_tm = lhand (concl mul_lo) in
194 let th0 = INST[n_tm, n_var_num; e_tm, e_var_num; j_tm, j_var_num;
195 n1_tm, n1_var_num; e1_tm, e1_var_num; lo_tm, lo_var_real;
196 i_tm, i_var_num] float_pow_pos_suc_lo_th in
197 MY_PROVE_HYP t_th (MY_PROVE_HYP mul_lo (MY_PROVE_HYP suc_j th0));;
198
199 let float_pow_pos_double_hi pp x_tm t_th =
200 let _, n_tm, e_tm = dest_float x_tm in
201 let ltm, t_tm = dest_comb (concl t_th) in
202 let j_tm = rand (rand ltm) in
203 let double_j = eval_mul2 j_tm in
204 let i_tm = rand (concl double_j) in
205 let mul_hi = float_mul_hi pp t_tm t_tm in
206 let hi_tm = rand (concl mul_hi) in
207 let th0 = INST[n_tm, n_var_num; e_tm, e_var_num; j_tm, j_var_num;
208 t_tm, t_var_real; hi_tm, hi_var_real;
209 i_tm, i_var_num] float_pow_pos_double_hi_th in
210 MY_PROVE_HYP t_th (MY_PROVE_HYP mul_hi (MY_PROVE_HYP double_j th0));;
211
212 let float_pow_pos_double_lo pp x_tm t_th =
213 let ltm, rtm = dest_comb (concl t_th) in
214 let t_tm = rand ltm in
215 let j_tm = rand rtm in
216 let _, n1_tm, e1_tm = dest_float t_tm in
217 let double_j = eval_mul2 j_tm in
218 let i_tm = rand (concl double_j) in
219 let mul_lo = float_mul_lo pp t_tm t_tm in
220 let lo_tm = lhand (concl mul_lo) in
221 let th0 = INST[x_tm, x_var_real; n1_tm, n1_var_num; e1_tm, e1_var_num;
222 j_tm, j_var_num; lo_tm, lo_var_real;
223 i_tm, i_var_num] float_pow_pos_double_lo_th in
224 MY_PROVE_HYP t_th (MY_PROVE_HYP mul_lo (MY_PROVE_HYP double_j th0));;
225
226 let float_pow_pos_hi pp x_tm n =
227 let rec pow n =
228 match n with
229 | 0 -> INST[x_tm, x_var_real] float_pow0_hi
230 | 1 -> INST[x_tm, x_var_real] float_pow1_hi
231 | 2 ->
232 let mul_hi = float_mul_hi pp x_tm x_tm in
233 let hi_tm = rand (concl mul_hi) in
234 let th0 = INST[x_tm, x_var_real; hi_tm, hi_var_real] float_pow2_hi in
235 MY_PROVE_HYP mul_hi th0
236 | _ ->
237 let _ = assert (n > 2) in
238 if (n land 1) = 0 then
239 (* even *)
240 let t_th = pow (n lsr 1) in
241 float_pow_pos_double_hi pp x_tm t_th
242 else
243 (* odd *)
244 let t_th = pow (n - 1) in
245 float_pow_pos_suc_hi pp x_tm t_th
246 in
247 pow n;;
248
249 let float_pow_pos_lo pp x_tm n =
250 let rec pow n =
251 match n with
252 | 0 -> INST[x_tm, x_var_real] float_pow0_lo
253 | 1 -> INST[x_tm, x_var_real] float_pow1_lo
254 | 2 ->
255 let mul_lo = float_mul_lo pp x_tm x_tm in
256 let lo_tm = lhand (concl mul_lo) in
257 let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real] float_pow2_lo in
258 MY_PROVE_HYP mul_lo th0
259 | _ ->
260 let _ = assert (n > 2) in
261 if (n land 1) = 0 then
262 (* even *)
263 let t_th = pow (n lsr 1) in
264 float_pow_pos_double_lo pp x_tm t_th
265 else
266 (* odd *)
267 let t_th = pow (n - 1) in
268 float_pow_pos_suc_lo pp x_tm t_th
269 in
270 pow n;;
271
272 let float_pow_hi pp n x_tm =
273 match n with
274 | 0 -> INST[x_tm, x_var_real] float_pow0_hi
275 | 1 -> INST[x_tm, x_var_real] float_pow1_hi
276 | 2 ->
277 let mul_hi = float_mul_hi pp x_tm x_tm in
278 let hi_tm = rand (concl mul_hi) in
279 let th0 = INST[x_tm, x_var_real; hi_tm, hi_var_real] float_pow2_hi in
280 MY_PROVE_HYP mul_hi th0
281 | _ ->
282 let s, xn_tm, e_tm = dest_float x_tm in
283 if s = "F" then
284 float_pow_pos_hi pp x_tm n
285 else
286 let x_pos = make_float "F" xn_tm e_tm in
287 if (n land 1) = 0 then
288 (* EVEN *)
289 let hi_th = float_pow_pos_hi pp x_pos n in
290 let ltm, hi_tm = dest_comb (concl hi_th) in
291 let n_tm = rand (rand ltm) in
292 let n_even = eval_even n_tm in
293 let th0 = INST[xn_tm, n_var_num; e_tm, e_var_num; n_tm, i_var_num;
294 hi_tm, hi_var_real] float_pow_neg_even_hi_th in
295 MY_PROVE_HYP n_even (MY_PROVE_HYP hi_th th0)
296 else
297 (* ODD *)
298 let lo_th = float_pow_pos_lo pp x_pos n in
299 let ltm, rtm = dest_comb (concl lo_th) in
300 let lo_tm = rand ltm in
301 let n_tm = rand rtm in
302 let _, n1_tm, e1_tm = dest_float lo_tm in
303 let n_even = eval_even n_tm in
304 let th0 = INST[xn_tm, n_var_num; e_tm, e_var_num; n_tm, i_var_num;
305 n1_tm, n1_var_num; e1_tm, e1_var_num] float_pow_neg_odd_hi_th in
306 MY_PROVE_HYP n_even (MY_PROVE_HYP lo_th th0);;
307
308 let float_pow_lo pp n x_tm =
309 match n with
310 | 0 -> INST[x_tm, x_var_real] float_pow0_lo
311 | 1 -> INST[x_tm, x_var_real] float_pow1_lo
312 | 2 ->
313 let mul_lo = float_mul_lo pp x_tm x_tm in
314 let lo_tm = lhand (concl mul_lo) in
315 let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real] float_pow2_lo in
316 MY_PROVE_HYP mul_lo th0
317 | _ ->
318 let s, xn_tm, e_tm = dest_float x_tm in
319 if s = "F" then
320 float_pow_pos_lo pp x_tm n
321 else
322 let x_pos = make_float "F" xn_tm e_tm in
323 if (n land 1) = 0 then
324 (* EVEN *)
325 let lo_th = float_pow_pos_lo pp x_pos n in
326 let ltm, rtm = dest_comb (concl lo_th) in
327 let lo_tm = rand ltm in
328 let n_tm = rand rtm in
329 let n_even = eval_even n_tm in
330 let th0 = INST[xn_tm, n_var_num; e_tm, e_var_num; n_tm, i_var_num;
331 lo_tm, lo_var_real] float_pow_neg_even_lo_th in
332 MY_PROVE_HYP n_even (MY_PROVE_HYP lo_th th0)
333 else
334 let hi_th = float_pow_pos_hi pp x_pos n in
335 let ltm, hi_tm = dest_comb (concl hi_th) in
336 let n_tm = rand (rand ltm) in
337 let _, n1_tm, e1_tm = dest_float hi_tm in
338 let n_even = eval_even n_tm in
339 let th0 = INST[xn_tm, n_var_num; e_tm, e_var_num; n_tm, i_var_num;
340 n1_tm, n1_var_num; e1_tm, e1_var_num] float_pow_neg_odd_lo_th in
341 MY_PROVE_HYP n_even (MY_PROVE_HYP hi_th th0);;
342
343 (* ------------------------------------------------ *)
344 (* Power of an interval *)
345 (* ------------------------------------------------ *)
346
347 let float_interval_pow0 = (th_rule o PURE_REWRITE_RULE[float_eq 1] o prove)
348 (`interval_arith (x pow 0) (&1, &1)`,
349 REWRITE_TAC[real_pow; interval_arith; REAL_LE_REFL]);;
350
351 let float_interval_pow1 = (th_rule o prove)
352 (`interval_arith x (lo, hi) ==>
353 interval_arith (x pow 1) (lo, hi)`,
354 REWRITE_TAC[REAL_POW_1; interval_arith]);;
355
356 let float_interval_pow_ft = (th_rule o PURE_REWRITE_RULE[float_eq 0] o prove)
357 (`(n = 0 <=> F) /\ interval_arith x (float_num F n1 e1, float_num T n2 e2)
358 ==> interval_arith (x pow n) (&0, &0)`,
359 STRIP_TAC THEN
360 POP_ASSUM (ASSUME_TAC o MATCH_MP FLOAT_INTERVAL_FT_IMP_0) THEN
361 ASM_REWRITE_TAC[REAL_POW_ZERO; interval_arith; REAL_LE_REFL]);;
362
363 let float_interval_pow_odd = (th_rule o prove)
364 (`interval_arith x (low, high) /\
365 (EVEN n <=> F) /\
366 high pow n <= hi /\
367 lo <= low pow n
368 ==> interval_arith (x pow n) (lo, hi)`,
369 REWRITE_TAC[NOT_EVEN; interval_arith] THEN STRIP_TAC THEN
370 CONJ_TAC THENL [
371 MATCH_MP_TAC REAL_LE_TRANS THEN
372 EXISTS_TAC `low pow n` THEN ASM_REWRITE_TAC[] THEN
373 MATCH_MP_TAC REAL_POW_LE2_ODD THEN ASM_REWRITE_TAC[];
374 MATCH_MP_TAC REAL_LE_TRANS THEN
375 EXISTS_TAC `high pow n` THEN ASM_REWRITE_TAC[] THEN
376 MATCH_MP_TAC REAL_POW_LE2_ODD THEN ASM_REWRITE_TAC[]
377 ]);;
378
379 let float_interval_pow_ff = (th_rule o prove)
380 (`interval_arith x (float_num F n1 e1, float_num F n2 e2) /\
381 float_num F n2 e2 pow n <= hi /\
382 lo <= float_num F n1 e1 pow n
383 ==> interval_arith (x pow n) (lo, hi)`,
384 REWRITE_TAC[interval_arith] THEN STRIP_TAC THEN
385 CONJ_TAC THENL [
386 MATCH_MP_TAC REAL_LE_TRANS THEN
387 EXISTS_TAC `float_num F n1 e1 pow n` THEN ASM_REWRITE_TAC[] THEN
388 MATCH_MP_TAC REAL_POW_LE2 THEN
389 ASM_REWRITE_TAC[FLOAT_F_POS];
390 MATCH_MP_TAC REAL_LE_TRANS THEN
391 EXISTS_TAC `float_num F n2 e2 pow n` THEN ASM_REWRITE_TAC[] THEN
392 MATCH_MP_TAC REAL_POW_LE2 THEN ASM_REWRITE_TAC[] THEN
393 MATCH_MP_TAC REAL_LE_TRANS THEN
394 EXISTS_TAC `float_num F n1 e1` THEN
395 ASM_REWRITE_TAC[FLOAT_F_POS]
396 ]);;
397
398 let float_interval_pow_even_tt = (th_rule o prove)
399 (`interval_arith x (float_num T n1 e1, float_num T n2 e2) /\
400 (EVEN n <=> T) /\
401 float_num F n1 e1 pow n <= hi /\
402 lo <= float_num F n2 e2 pow n
403 ==> interval_arith (x pow n) (lo, hi)`,
404 MP_TAC ((GSYM o SPEC `F`) FLOAT_NEG) THEN SIMP_TAC[] THEN DISCH_TAC THEN
405 REWRITE_TAC[interval_arith] THEN STRIP_TAC THEN
406 SUBGOAL_THEN `x pow n = (--x) pow n` (fun th -> REWRITE_TAC[th]) THENL [
407 ASM_REWRITE_TAC[REAL_POW_NEG];
408 ALL_TAC
409 ] THEN
410 CONJ_TAC THENL [
411 MATCH_MP_TAC REAL_LE_TRANS THEN
412 EXISTS_TAC `float_num F n2 e2 pow n` THEN ASM_REWRITE_TAC[] THEN
413 MATCH_MP_TAC REAL_POW_LE2 THEN
414 ASM_REWRITE_TAC[FLOAT_F_POS; REAL_ARITH `a <= --b <=> b <= --a`];
415 MATCH_MP_TAC REAL_LE_TRANS THEN
416 EXISTS_TAC `float_num F n1 e1 pow n` THEN ASM_REWRITE_TAC[] THEN
417 MATCH_MP_TAC REAL_POW_LE2 THEN
418 ONCE_REWRITE_TAC[REAL_ARITH `--x <= a <=> --a <= x`] THEN
419 ASM_REWRITE_TAC[] THEN
420 MATCH_MP_TAC REAL_LE_TRANS THEN
421 EXISTS_TAC `float_num F n2 e2` THEN
422 ASM_REWRITE_TAC[FLOAT_F_POS; REAL_ARITH `a <= --b <=> b <= --a`]
423 ]);;
424
425 let float_interval_pow_even_tf = (th_rule o PURE_REWRITE_RULE[float_eq 0] o prove)
426 (`interval_arith x (float_num T n1 e1, float_num F n2 e2) /\
427 (EVEN n <=> T) /\
428 max (float_num F n1 e1) (float_num F n2 e2) = t /\
429 t pow n <= hi
430 ==> interval_arith (x pow n) (&0, hi)`,
431 MP_TAC ((GSYM o SPEC `F`) FLOAT_NEG) THEN SIMP_TAC[] THEN DISCH_TAC THEN
432 REWRITE_TAC[interval_arith; EVEN_EXISTS] THEN STRIP_TAC THEN
433 CONJ_TAC THENL [
434 ASM_REWRITE_TAC[FLOAT_0] THEN
435 ONCE_REWRITE_TAC[MULT_SYM] THEN REWRITE_TAC[GSYM REAL_POW_POW] THEN
436 REWRITE_TAC[REAL_LE_POW_2];
437 MATCH_MP_TAC REAL_LE_TRANS THEN
438 EXISTS_TAC `t pow n` THEN ASM_REWRITE_TAC[] THEN
439 ONCE_REWRITE_TAC[MULT_SYM] THEN REWRITE_TAC[GSYM REAL_POW_POW] THEN
440 REWRITE_TAC[GSYM REAL_LE_SQUARE_ABS; REAL_ABS_POW] THEN
441 MATCH_MP_TAC REAL_POW_LE2 THEN REWRITE_TAC[REAL_ABS_POS] THEN
442 ASM_ARITH_TAC
443 ]);;
444
445
446 let float_interval_pow pp n x_th =
447 let x, low, high = dest_float_interval (concl x_th) in
448 match n with
449 | 0 -> INST[x, x_var_real] float_interval_pow0
450 | 1 ->
451 let th0 = INST[x, x_var_real; low, lo_var_real; high, hi_var_real] float_interval_pow1 in
452 MY_PROVE_HYP x_th th0
453 | _ ->
454 let _ = assert (n > 1) in
455 if (n land 1) = 1 then
456 (* odd *)
457 let hi_th = float_pow_hi pp n high and
458 lo_th = float_pow_lo pp n low in
459 let hi = rand (concl hi_th) and
460 lo = lhand (concl lo_th) and
461 n_tm = rand (rand (concl lo_th)) in
462 let even_n = eval_even n_tm in
463 let th0 = INST[x, x_var_real; low, low_var_real; high, high_var_real;
464 hi, hi_var_real; lo, lo_var_real; n_tm, n_var_num] float_interval_pow_odd in
465 MY_PROVE_HYP even_n (MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th (MY_PROVE_HYP x_th th0)))
466 else
467 (* even *)
468 let s1, n1, e1 = dest_float low and
469 s2, n2, e2 = dest_float high in
470 if s1 = s2 then
471 if s1 = "F" then
472 (* FF *)
473 let hi_th = float_pow_hi pp n high and
474 lo_th = float_pow_lo pp n low in
475 let hi = rand (concl hi_th) and
476 lo = lhand (concl lo_th) and
477 n_tm = rand (rand (concl lo_th)) in
478 let th0 = INST[x, x_var_real; n1, n1_var_num; e1, e1_var_num;
479 n2, n2_var_num; e2, e2_var_num; n_tm, n_var_num;
480 lo, lo_var_real; hi, hi_var_real] float_interval_pow_ff in
481 MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th (MY_PROVE_HYP x_th th0))
482 else
483 (* TT *)
484 let hi_th = float_pow_hi pp n (make_float "F" n1 e1) and
485 lo_th = float_pow_lo pp n (make_float "F" n2 e2) in
486 let hi = rand (concl hi_th) and
487 lo = lhand (concl lo_th) and
488 n_tm = rand (rand (concl lo_th)) in
489 let even_n = eval_even n_tm in
490 let th0 = INST[x, x_var_real; n1, n1_var_num; e1, e1_var_num;
491 n2, n2_var_num; e2, e2_var_num; n_tm, n_var_num;
492 lo, lo_var_real; hi, hi_var_real] float_interval_pow_even_tt in
493 MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th (MY_PROVE_HYP even_n (MY_PROVE_HYP x_th th0)))
494 else
495 if s1 = "F" then
496 (* FT *)
497 let n_tm = mk_small_numeral n in
498 let n0 = eval_eq0 n_tm in
499 (* Should be n <> 0 *)
500 let th0 = INST[x, x_var_real; n_tm, n_var_num;
501 n1, n1_var_num; e1, e1_var_num;
502 n2, n2_var_num; e2, e2_var_num] float_interval_pow_ft in
503 MY_PROVE_HYP n0 (MY_PROVE_HYP x_th th0)
504 else
505 (* TF *)
506 let max_eq = float_max (make_float "F" n1 e1) high in
507 let t_tm = rand (concl max_eq) in
508 let hi_th = float_pow_hi pp n t_tm in
509 let ltm, hi = dest_comb (concl hi_th) in
510 let n_tm = rand (rand ltm) in
511 let even_n = eval_even n_tm in
512 let th0 = INST[x, x_var_real; n_tm, n_var_num;
513 n1, n1_var_num; e1, e1_var_num;
514 n2, n2_var_num; e2, e2_var_num;
515 t_tm, t_var_real; hi, hi_var_real] float_interval_pow_even_tf in
516 MY_PROVE_HYP hi_th (MY_PROVE_HYP max_eq (MY_PROVE_HYP even_n (MY_PROVE_HYP x_th th0)));;
517
518 end;;
519
520
521 (*
522 let mk_test p_tm =
523 let tm = mk_comb (`interval_arith z`, p_tm) in
524 REWRITE_RULE[FLOAT_NEG] (RULE (ASSUME tm));;
525
526 let i1 = mk_test `&1, &2`;;
527 let i2 = mk_test `-- &1, &2`;;
528 let i3 = mk_test `-- &3, -- &1`;;
529 let i4 = mk_test `&0, &1`;;
530 let i5 = mk_test `-- &2, &1`;;
531
532 let n = 4;;
533 float_interval_pow 4 n i1;;
534 float_interval_pow 4 n i2;;
535 float_interval_pow 4 n i3;;
536 float_interval_pow 4 n i4;;
537 float_interval_pow 4 n i5;;
538 *)