Debian Codegraph @

Formal_ineqs/arith/arith_float.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2012 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Formal floating point arithmetic *)
11 (* -------------------------------------------------------------------------- *)
12
13 (* Dependencies *)
14 needs "Formal_ineqs/arith/arith_nat.hl";;
15 needs "Formal_ineqs/arith/num_exp_theory.hl";;
16 needs "Formal_ineqs/arith/float_theory.hl";;
17 needs "Formal_ineqs/arith/interval_arith.hl";;
18 needs "Formal_ineqs/misc/misc_vars.hl";;
19
20 needs "Formal_ineqs/tests/log.hl";;
21
22 (* FLOOR_DIV_DIV *)
23 needs "Library/floor.ml";;
24
25 module type Arith_float_sig =
26 sig
27 val mk_num_exp : term -> term -> term
28 val dest_num_exp : term -> (term * term)
29 val dest_float : term -> (string * term * term)
30 val make_float : string -> term -> term -> term
31 val mk_float : int -> int -> term
32
33 (* num_exp normalization/denormalization *)
34 val normalize : term -> thm * bool
35 val denormalize : term -> thm
36
37 val lo_num_conv : int -> term -> thm
38 val hi_num_conv : int -> term -> thm
39 val num_exp_lo : int -> term -> thm
40 val num_exp_hi : int -> term -> thm
41
42 val float_lt0 : term -> thm
43 val float_gt0 : term -> thm
44 val float_lt : term -> term -> thm
45 val float_le0 : term -> thm
46 val float_ge0 : term -> thm
47 val float_le : term -> term -> thm
48 val float_min : term -> term -> thm
49 val float_max : term -> term -> thm
50 val float_min_max : term -> term -> (thm * thm)
51 val float_mul_eq : term -> term -> thm
52 val float_mul_lo : int -> term -> term -> thm
53 val float_mul_hi : int -> term -> term -> thm
54 val float_div_lo : int -> term -> term -> thm
55 val float_div_hi : int -> term -> term -> thm
56 val float_add_lo : int -> term -> term -> thm
57 val float_add_hi : int -> term -> term -> thm
58 val float_sub_lo : int -> term -> term -> thm
59 val float_sub_hi : int -> term -> term -> thm
60 val float_sqrt_lo : int -> term -> thm
61 val float_sqrt_hi : int -> term -> thm
62
63 val float_prove_le : term -> term -> bool * thm
64 val float_prove_lt : term -> term -> bool * thm
65 val float_prove_le_interval : term -> thm -> bool * thm
66 val float_prove_ge_interval : term -> thm -> bool * thm
67 val float_prove_lt_interval : term -> thm -> bool * thm
68 val float_prove_gt_interval : term -> thm -> bool * thm
69 val float_compare_interval : term -> thm -> int * thm
70
71 val init_logs : unit -> unit
72 val reset_stat : unit -> unit
73 val reset_cache : unit -> unit
74 val print_stat : unit -> unit
75
76 val dest_float_interval : term -> term * term * term
77 val mk_float_interval_small_num : int -> thm
78 val mk_float_interval_num : num -> thm
79
80 val float_lo : int -> term -> thm
81 val float_hi : int -> term -> thm
82
83 val float_interval_round : int -> thm -> thm
84
85 val float_interval_abs : thm -> thm
86 val float_interval_neg : thm -> thm
87 val float_interval_mul : int -> thm -> thm -> thm
88 val float_interval_div : int -> thm -> thm -> thm
89 val float_interval_add : int -> thm -> thm -> thm
90 val float_interval_sub : int -> thm -> thm -> thm
91 val float_interval_sqrt : int -> thm -> thm
92
93 val float_abs : term -> thm
94
95 val FLOAT_TO_NUM_CONV : term -> thm
96 end;;
97
98
99 module Arith_float : Arith_float_sig = struct
100
101 open Misc_functions;;
102 open Arith_nat;;
103 open Num_exp_theory;;
104 open Float_theory;;
105 open Interval_arith;;
106 open Misc_vars;;
107
108 prioritize_real();;
109
110 (* interval *)
111
112 let APPROX_INTERVAL' = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL) APPROX_INTERVAL;;
113
114 let interval_const = `interval_arith` and
115 num_exp_const = `num_exp`;;
116
117 let b0_const = (fst o dest_comb o lhand o concl) (Arith_num.def_array.(0));;
118 let b0_name = (fst o dest_const) b0_const;;
119 let base_const = mk_small_numeral Arith_num.arith_base;;
120
121 let NUM_REMOVE = prove(mk_eq(mk_comb(Arith_num.num_const, n_var_num), n_var_num),
122 REWRITE_TAC[Arith_num.num_def; NUMERAL]);;
123
124 (* B0 n = base * n *)
125 let b0_thm = prove(mk_eq(mk_comb(b0_const, n_var_num),
126 mk_binop mul_op_num base_const n_var_num),
127 REWRITE_TAC[Arith_num.def_array.(0)] THEN
128 TRY ARITH_TAC THEN
129 GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV) [BIT0] THEN
130 ARITH_TAC);;
131
132 let dest_num_exp tm =
133 let ltm, e_tm = dest_comb tm in
134 rand ltm, e_tm;;
135
136 let num_exp_const = `num_exp`;;
137 let mk_num_exp n_tm e_tm = mk_binop num_exp_const n_tm e_tm;;
138
139 (* float_num s n e -> "s", n, e *)
140 let dest_float tm =
141 let ltm, e_tm = dest_comb tm in
142 let ltm, n_tm = dest_comb ltm in
143 let float_tm, s_tm = dest_comb ltm in
144 if (fst o dest_const) float_tm <> "float_num" then
145 failwith "dest_float: not float"
146 else
147 (fst o dest_const) s_tm, n_tm, e_tm;;
148
149 (* "s", n, e -> float_num s n e *)
150 let make_float =
151 let float_const = `float_num` in
152 fun s n_tm e_tm ->
153 let s_tm = if s = "T" then t_const else f_const in
154 mk_comb (mk_comb (mk_comb (float_const, s_tm), n_tm), e_tm);;
155
156 (* Creates a float term with the value (n * base^e) *)
157 let mk_float =
158 let float_const = `float_num` in
159 fun n e ->
160 let n, s = if n < 0 then -n, t_const else n, f_const in
161 let n_tm = rand (Arith_nat.mk_small_numeral_array n) in
162 let e_tm = rand (Arith_nat.mk_small_numeral_array (e + Float_theory.min_exp)) in
163 mk_comb(mk_comb(mk_comb (float_const, s), n_tm), e_tm);;
164
165
166 (************************************)
167
168 let NUM_EXP_EXP' = SPEC_ALL NUM_EXP_EXP;;
169 let NUM_EXP_0' = (SPEC_ALL o REWRITE_RULE[NUMERAL]) NUM_EXP_0;;
170 let NUM_EXP_LE' = (UNDISCH_ALL o SPEC_ALL) NUM_EXP_LE;;
171 let NUM_EXP_LT' = (UNDISCH_ALL o SPEC_ALL) NUM_EXP_LT;;
172
173 (* B0 n = num_exp n bits *)
174 let normal_lemma1 = prove(mk_eq(mk_comb(b0_const, n_var_num), `num_exp n 1`),
175 REWRITE_TAC[Arith_num.def_array.(0); num_exp] THEN
176 TRY ARITH_TAC THEN
177 GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV) [BIT0] THEN
178 ARITH_TAC);;
179
180 let NORMAL_LEMMA1 = NUMERALS_TO_NUM normal_lemma1;;
181
182 let normal_lemma2 = prove(mk_eq (mk_comb (b0_const, `num_exp n e`), `num_exp n (SUC e)`),
183 REWRITE_TAC[normal_lemma1; NUM_EXP_EXP] THEN ARITH_TAC);;
184
185 let rec normalize tm =
186 if (is_comb tm) then
187 let ltm, rtm = dest_comb tm in
188 let lname = (fst o dest_const) ltm in
189 if (lname = b0_name) then
190 let lth = INST[rtm, n_var_num] NORMAL_LEMMA1 in
191 let rth, flag = normalize rtm in
192 if flag then
193 let ltm, lexp = (dest_comb o snd o dest_eq o concl) lth in
194 let ltm, rtm = dest_comb ltm in
195 let rn, rexp = (dest_comb o snd o dest_eq o concl) rth in
196 let rn = rand rn in
197 let th1 = AP_THM (AP_TERM ltm rth) lexp in
198 let th2 = INST[rexp, e1_var_num; lexp, e2_var_num; rn, n_var_num] NUM_EXP_EXP' in
199 let th3 = TRANS lth (TRANS th1 th2) in
200 let ltm, rtm = (dest_comb o snd o dest_eq o concl) th3 in
201 let add_th = raw_add_conv_hash rtm in
202 let th4 = AP_TERM ltm add_th in
203 (TRANS th3 th4, true)
204 else
205 (lth, true)
206 else
207 (REFL tm, false)
208 else
209 (REFL tm, false);;
210
211 (* Converts a raw numeral to a num_exp expression *)
212 let to_num_exp tm =
213 let x, flag = normalize tm in
214 if flag then x
215 else
216 INST[tm, n_var_num] NUM_EXP_0';;
217
218 (************************************)
219
220 let SYM_NUM_EXP_0' = SYM NUM_EXP_0';;
221 let NUM_EXP_n0 = prove(`!e. num_exp 0 e = 0`, REWRITE_TAC[num_exp; MULT_CLAUSES]);;
222 let NUM_EXP_n0' = (REWRITE_RULE[NUMERAL] o SPEC_ALL) NUM_EXP_n0;;
223
224 let NUM_EXP_DENORM = (UNDISCH_ALL o prove)
225 (mk_imp(`e = _0 <=> F`, mk_eq(`num_exp n e`, mk_comb (b0_const, `num_exp n (PRE e)`))),
226 REWRITE_TAC[] THEN ONCE_REWRITE_TAC[SYM (REWRITE_CONV[NUMERAL] `0`)] THEN
227 REWRITE_TAC[num_exp; b0_thm] THEN
228 REWRITE_TAC[ARITH_RULE (mk_eq(mk_binop mul_op_num base_const `n * a:num`,
229 mk_binop mul_op_num `n:num` (mk_binop mul_op_num base_const `a:num`)))] THEN
230 REWRITE_TAC[GSYM EXP] THEN
231 SIMP_TAC[ARITH_RULE `~(e = 0) ==> SUC (PRE e) = e`]);;
232
233 (* Converts num_exp n e to a numeral by adding e B0's *)
234 let rec denormalize tm =
235 let ltm, etm = dest_comb tm in
236 let ntm = rand ltm in
237 if (etm = zero_const) then
238 INST[ntm, n_var_num] SYM_NUM_EXP_0'
239 else
240 if ntm = zero_const then
241 INST[etm, e_var_num] NUM_EXP_n0'
242 else
243 let e_th = raw_eq0_hash_conv etm in
244 let th0' = INST[etm, e_var_num; ntm, n_var_num] NUM_EXP_DENORM in
245 let th0 = MY_PROVE_HYP e_th th0' in
246 let b0_tm, rtm = dest_comb(rand(concl th0)) in
247 let ltm, pre_tm = dest_comb rtm in
248 let pre_th = raw_pre_hash_conv pre_tm in
249 let th1 = AP_TERM ltm pre_th in
250 let th2 = denormalize (rand(concl th1)) in
251 TRANS th0 (AP_TERM b0_tm (TRANS th1 th2));;
252
253 (***************************************)
254
255 let rec comb_number tm n =
256 if (is_comb tm) then comb_number ((snd o dest_comb) tm) (n + 1) else n;;
257
258 let make_lo_thm i =
259 let th_concl = mk_binop `(<=):num->num->bool`
260 (mk_comb (Arith_num.const_array.(0), n_var_num))
261 (mk_comb (Arith_num.const_array.(i), n_var_num)) in
262 prove(th_concl,
263 REWRITE_TAC[Arith_num.def_array.(i); Arith_num.def_array.(0)] THEN
264 REWRITE_TAC[ARITH_LE; LE_REFL] THEN
265 ARITH_TAC);;
266
267 let lo_thm_array = Array.init Arith_num.arith_base make_lo_thm;;
268 let lo_thm_table = Hashtbl.create Arith_num.arith_base;;
269
270 for i = 0 to Arith_num.arith_base - 1 do
271 Hashtbl.add lo_thm_table Arith_num.const_array.(i) lo_thm_array.(i);
272 done;;
273
274 let make_lo_thm2 i =
275 let th_concl = mk_imp (`n <= m:num`,
276 mk_binop `(<=):num->num->bool`
277 (mk_comb (Arith_num.const_array.(0), n_var_num))
278 (mk_comb (Arith_num.const_array.(i), m_var_num))) in
279 (UNDISCH_ALL o prove) (th_concl,
280 REWRITE_TAC[Arith_num.def_array.(i); Arith_num.def_array.(0); ARITH_LE] THEN
281 ARITH_TAC);;
282
283 let lo_thm2_array = Array.init Arith_num.arith_base make_lo_thm2;;
284 let lo_thm2_table = Hashtbl.create Arith_num.arith_base;;
285
286 for i = 0 to Arith_num.arith_base - 1 do
287 Hashtbl.add lo_thm2_table Arith_num.const_array.(i) lo_thm2_array.(i);
288 done;;
289
290
291 let make_hi_thm i =
292 let th_concl = mk_imp (`n < m:num`,
293 mk_binop `(<):num->num->bool`
294 (mk_comb (Arith_num.const_array.(i), n_var_num))
295 (mk_comb (Arith_num.const_array.(0), m_var_num))) in
296 (UNDISCH_ALL o prove) (th_concl,
297 REWRITE_TAC[Arith_num.def_array.(i); Arith_num.def_array.(0); ARITH_LT] THEN
298 ARITH_TAC);;
299
300 let hi_thm_array = Array.init Arith_num.arith_base make_hi_thm;;
301 let hi_thm_table = Hashtbl.create Arith_num.arith_base;;
302
303 for i = 0 to Arith_num.arith_base - 1 do
304 Hashtbl.add hi_thm_table Arith_num.const_array.(i) hi_thm_array.(i);
305 done;;
306
307 (***************************************)
308
309 let LE_REFL' = SPEC_ALL LE_REFL;;
310 let LE_TRANS' = (UNDISCH_ALL o SPEC_ALL o REWRITE_RULE[GSYM IMP_IMP]) LE_TRANS;;
311
312 let lo_num_conv p tm =
313 let n = comb_number tm 0 in
314 if (n <= p) then
315 INST[tm, n_var_num] LE_REFL'
316 else
317 let rec lo_bound n tm =
318 let btm, rtm = dest_comb tm in
319 let th0 = INST[rtm, n_var_num] (Hashtbl.find lo_thm_table btm) in
320 if n > 1 then
321 let rth = lo_bound (n - 1) rtm in
322 let xtm = rand (rator (concl rth)) in
323 let th1' = INST[xtm, n_var_num; rtm, m_var_num] (Hashtbl.find lo_thm2_table btm) in
324 let th1 = MY_PROVE_HYP rth th1' in
325 th1
326 else
327 th0 in
328
329 lo_bound (n - p) tm;;
330
331 let N_LT_SUC = ARITH_RULE `n < SUC n`;;
332 let LT_IMP_LE' = (UNDISCH_ALL o SPEC_ALL) LT_IMP_LE;;
333 let N_LT_SUC = ARITH_RULE `n < SUC n`;;
334 let LT_LE_TRANS = (UNDISCH_ALL o ARITH_RULE) `n < e ==> e <= m ==> n < m:num`;;
335
336 (* Generates a theorem |- n <= m such that m contains at most p non-zero digits *)
337 let hi_num_conv p tm =
338 let n = comb_number tm 0 in
339 if (n <= p) then
340 INST[tm, n_var_num] LE_REFL'
341 else
342 let k = n - p in
343
344 let rec check_b0s n tm =
345 let btm, rtm = dest_comb tm in
346 if ((fst o dest_const) btm = b0_name) then
347 if n > 1 then check_b0s (n - 1) rtm else true
348 else
349 false in
350
351 if (check_b0s k tm) then
352 INST[tm, n_var_num] LE_REFL'
353 else
354 let rec hi_bound n tm =
355 if n > 0 then
356 let btm, rtm = dest_comb tm in
357 let r_th = hi_bound (n - 1) rtm in
358 let xtm = rand (concl r_th) in
359 let th0 = INST[rtm, n_var_num; xtm, m_var_num] (Hashtbl.find hi_thm_table btm) in
360 MY_PROVE_HYP r_th th0
361 else
362 let th0 = INST[tm, n_var_num] N_LT_SUC in
363 let ltm, suc_tm = dest_comb (concl th0) in
364 let suc_th = raw_suc_conv_hash suc_tm in
365 EQ_MP (AP_TERM ltm suc_th) th0 in
366
367 let th = hi_bound k tm in
368 let m_tm, l_tm = dest_comb (concl th) in
369 MY_PROVE_HYP th (INST[rand m_tm, m_var_num; l_tm, n_var_num] LT_IMP_LE');;
370
371 (* Generates a theorem |- n < m such that m contains at most p non-zero digits *)
372 let hi_lt_num_conv p tm =
373 let n = comb_number tm 0 in
374 if (n <= p) then
375 let th0 = INST[tm, n_var_num] N_LT_SUC in
376 let ltm, rtm = dest_comb(concl th0) in
377 let suc_th = raw_suc_conv_hash rtm in
378 EQ_MP (AP_TERM ltm suc_th) th0
379 else
380 let k = n - p in
381
382 let rec check_b0s n tm =
383 let btm, rtm = dest_comb tm in
384 if ((fst o dest_const) btm = b0_name) then
385 if n > 1 then check_b0s (n - 1) rtm else true
386 else
387 false in
388
389 if (check_b0s k tm) then
390 let th0 = INST[tm, n_var_num] N_LT_SUC in
391 let ltm, rtm = dest_comb (concl th0) in
392 let suc_th = raw_suc_conv_hash rtm in
393 let suc_tm = rand(concl suc_th) in
394 let th1 = hi_num_conv p suc_tm in
395 let th2 = EQ_MP (AP_TERM ltm suc_th) th0 in
396 let th = INST[tm, n_var_num; suc_tm, e_var_num; rand(concl th1), m_var_num] LT_LE_TRANS in
397 MY_PROVE_HYP th1 (MY_PROVE_HYP th2 th)
398
399 else
400 let rec hi_bound n tm =
401 if n > 0 then
402 let btm, rtm = dest_comb tm in
403 let r_th = hi_bound (n - 1) rtm in
404 let xtm = rand (concl r_th) in
405 let th0 = INST[rtm, n_var_num; xtm, m_var_num] (Hashtbl.find hi_thm_table btm) in
406 MY_PROVE_HYP r_th th0
407 else
408 let th0 = INST[tm, n_var_num] N_LT_SUC in
409 let ltm, suc_tm = dest_comb (concl th0) in
410 let suc_th = raw_suc_conv_hash suc_tm in
411 EQ_MP (AP_TERM ltm suc_th) th0 in
412 hi_bound k tm;;
413
414 (*****************************************)
415
416 let num_exp_lo p tm =
417 let ltm, e_tm = dest_comb tm in
418 let n_tm = rand ltm in
419 let n_th = lo_num_conv p n_tm in
420 let m_tm = rand (rator (concl n_th)) in
421 let m_norm, flag = normalize m_tm in
422
423 let th0' = INST[m_tm, m_var_num; n_tm, n_var_num; e_tm, e_var_num] NUM_EXP_LE' in
424 let th0 = MY_PROVE_HYP n_th th0' in
425 if flag then
426 let th1 = AP_THM (AP_TERM (rator ltm) m_norm) e_tm in
427 let m_tm, me_tm = (dest_comb o rand o concl) m_norm in
428 let th2 = INST[me_tm, e1_var_num; e_tm, e2_var_num; rand m_tm, n_var_num] NUM_EXP_EXP' in
429 let th3 = TRANS th1 th2 in
430 let ltm, rtm = (dest_comb o rand o concl) th3 in
431 let th_add = raw_add_conv_hash rtm in
432 let th4 = TRANS th3 (AP_TERM ltm th_add) in
433 EQ_MP (AP_THM (AP_TERM le_op_num th4) tm) th0
434 else
435 th0;;
436
437 let num_exp_hi p tm =
438 let ltm, e_tm = dest_comb tm in
439 let n_tm = rand ltm in
440 let n_th = hi_num_conv p n_tm in
441 let m_tm = rand (concl n_th) in
442 let m_norm, flag = normalize m_tm in
443
444 let th0' = INST[m_tm, n_var_num; n_tm, m_var_num; e_tm, e_var_num] NUM_EXP_LE' in
445 let th0 = MY_PROVE_HYP n_th th0' in
446 if flag then
447 let th1 = AP_THM (AP_TERM (rator ltm) m_norm) e_tm in
448 let m_tm, me_tm = (dest_comb o rand o concl) m_norm in
449 let th2 = INST[me_tm, e1_var_num; e_tm, e2_var_num; rand m_tm, n_var_num] NUM_EXP_EXP' in
450 let th3 = TRANS th1 th2 in
451 let ltm, rtm = (dest_comb o rand o concl) th3 in
452 let th_add = raw_add_conv_hash rtm in
453 let th4 = TRANS th3 (AP_TERM ltm th_add) in
454 EQ_MP (AP_TERM (rator (concl th0)) th4) th0
455 else
456 th0;;
457
458 let num_exp_hi_lt p tm =
459 let ltm, e_tm = dest_comb tm in
460 let n_tm = rand ltm in
461 let n_th = hi_lt_num_conv p n_tm in
462 let m_tm = rand (concl n_th) in
463 let m_norm, flag = normalize m_tm in
464
465 let th0' = INST[m_tm, n_var_num; n_tm, m_var_num; e_tm, e_var_num] NUM_EXP_LT' in
466 let th0 = MY_PROVE_HYP n_th th0' in
467 if flag then
468 let th1 = AP_THM (AP_TERM (rator ltm) m_norm) e_tm in
469 let m_tm, me_tm = (dest_comb o rand o concl) m_norm in
470 let th2 = INST[me_tm, e1_var_num; e_tm, e2_var_num; rand m_tm, n_var_num] NUM_EXP_EXP' in
471 let th3 = TRANS th1 th2 in
472 let ltm, rtm = (dest_comb o rand o concl) th3 in
473 let th_add = raw_add_conv_hash rtm in
474 let th4 = TRANS th3 (AP_TERM ltm th_add) in
475 EQ_MP (AP_TERM (rator (concl th0)) th4) th0
476 else
477 th0;;
478
479 (***************************************)
480 (* num_exp_lt, num_exp_le *)
481
482 let transform = UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL;;
483
484 let NUM_EXP_LT1_EQ' = transform NUM_EXP_LT1_EQ and
485 NUM_EXP_LT2_EQ' = transform NUM_EXP_LT2_EQ;;
486
487 let NUM_EXP_LE1_EQ' = transform NUM_EXP_LE1_EQ and
488 NUM_EXP_LE2_EQ' = transform NUM_EXP_LE2_EQ;;
489
490 let num_exp_lt tm1 tm2 =
491 let n1_tm, e1_tm = dest_num_exp tm1 in
492 let n2_tm, e2_tm = dest_num_exp tm2 in
493 let sub_th, le_th = raw_sub_and_le_hash_conv e1_tm e2_tm in
494 let r_tm = rand(concl sub_th) in
495 if (rand(concl le_th) = e1_tm) then
496 let x_expr = mk_num_exp n1_tm r_tm in
497 let x_th = denormalize x_expr in
498 let x_tm = rand(concl x_th) in
499
500 let th0 = INST[e2_tm, e2_var_num; e1_tm, e1_var_num;
501 r_tm, r_var_num; x_tm, x_var_num;
502 n1_tm, n1_var_num; n2_tm, n2_var_num] NUM_EXP_LT1_EQ' in
503 let th1 = MY_PROVE_HYP x_th (MY_PROVE_HYP sub_th (MY_PROVE_HYP le_th th0)) in
504 let lt_th = raw_lt_hash_conv (rand(concl th1)) in
505 TRANS th1 lt_th
506 else
507 let x_expr = mk_num_exp n2_tm r_tm in
508 let x_th = denormalize x_expr in
509 let x_tm = rand(concl x_th) in
510
511 let th0 = INST[e2_tm, e2_var_num; e1_tm, e1_var_num;
512 r_tm, r_var_num; x_tm, x_var_num;
513 n1_tm, n1_var_num; n2_tm, n2_var_num] NUM_EXP_LT2_EQ' in
514 let th1 = MY_PROVE_HYP x_th (MY_PROVE_HYP sub_th (MY_PROVE_HYP le_th th0)) in
515 let lt_th = raw_lt_hash_conv (rand(concl th1)) in
516 TRANS th1 lt_th;;
517
518
519 let num_exp_le tm1 tm2 =
520 let n1_tm, e1_tm = dest_num_exp tm1 in
521 let n2_tm, e2_tm = dest_num_exp tm2 in
522 let sub_th, le_th = raw_sub_and_le_hash_conv e1_tm e2_tm in
523 let r_tm = rand(concl sub_th) in
524 if (rand(concl le_th) = e1_tm) then
525 let x_expr = mk_num_exp n1_tm r_tm in
526 let x_th = denormalize x_expr in
527 let x_tm = rand(concl x_th) in
528
529 let th0 = INST[e2_tm, e2_var_num; e1_tm, e1_var_num;
530 r_tm, r_var_num; x_tm, x_var_num;
531 n1_tm, n1_var_num; n2_tm, n2_var_num] NUM_EXP_LE1_EQ' in
532 let th1 = MY_PROVE_HYP x_th (MY_PROVE_HYP sub_th (MY_PROVE_HYP le_th th0)) in
533 let le_th = raw_le_hash_conv (rand(concl th1)) in
534 TRANS th1 le_th
535 else
536 let x_expr = mk_num_exp n2_tm r_tm in
537 let x_th = denormalize x_expr in
538 let x_tm = rand(concl x_th) in
539
540 let th0 = INST[e2_tm, e2_var_num; e1_tm, e1_var_num;
541 r_tm, r_var_num; x_tm, x_var_num;
542 n1_tm, n1_var_num; n2_tm, n2_var_num] NUM_EXP_LE2_EQ' in
543 let th1 = MY_PROVE_HYP x_th (MY_PROVE_HYP sub_th (MY_PROVE_HYP le_th th0)) in
544 let le_th = raw_le_hash_conv (rand(concl th1)) in
545 TRANS th1 le_th;;
546
547 (***************************************)
548 (* num_exp_mul *)
549
550 let NUM_EXP_MUL' = SPEC_ALL NUM_EXP_MUL;;
551
552 let num_exp_mul tm1 tm2 =
553 let n1_tm, e1_tm = dest_comb tm1 in
554 let n1_tm = rand n1_tm in
555 let n2_tm, e2_tm = dest_comb tm2 in
556 let n2_tm = rand n2_tm in
557 let th0 = INST[n1_tm, n1_var_num; e1_tm, e1_var_num;
558 n2_tm, n2_var_num; e2_tm, e2_var_num] NUM_EXP_MUL' in
559 let ltm, tm_add = dest_comb (rand (concl th0)) in
560 let tm_mul = rand ltm in
561 let th_mul = raw_mul_conv_hash tm_mul in
562 let th_add = raw_add_conv_hash tm_add in
563 TRANS th0 (MK_COMB (AP_TERM (rator ltm) th_mul, th_add));;
564
565
566 (**********************************)
567 (* num_exp_add *)
568
569 let NUM_EXP_ADD' = (UNDISCH_ALL o SPEC_ALL) NUM_EXP_ADD;;
570 let ADD_COMM = ARITH_RULE `m + n = n + m:num`;;
571
572 let num_exp_add tm1 tm2 =
573 let n1_tm, e1_tm = dest_comb tm1 in
574 let n1_tm = rand n1_tm in
575 let n2_tm, e2_tm = dest_comb tm2 in
576 let n2_tm = rand n2_tm in
577 let e_sub, e_le = raw_sub_and_le_hash_conv e1_tm e2_tm in
578
579 let flag = (rand(concl e_le) = e2_tm) in
580
581 let th0' =
582 if flag then
583 INST[n1_tm, n1_var_num; e1_tm, e1_var_num;
584 n2_tm, n2_var_num; e2_tm, e2_var_num] NUM_EXP_ADD'
585 else
586 INST[n2_tm, n1_var_num; e2_tm, e1_var_num;
587 n1_tm, n2_var_num; e1_tm, e2_var_num] NUM_EXP_ADD' in
588
589 let th0 = MY_PROVE_HYP e_le th0' in
590 let ltm, e0_tm = dest_comb(rand(concl th0)) in
591 let exp_tm, add_tm = dest_comb ltm in
592 let ltm, d_tm = dest_comb add_tm in
593 let th1 = AP_TERM (rator d_tm) e_sub in
594 let th2 = denormalize (rand(concl th1)) in
595 let th3 = AP_TERM ltm (TRANS th1 th2) in
596 let th4 = raw_add_conv_hash (rand(concl th3)) in
597 let th5 = AP_THM (AP_TERM exp_tm (TRANS th3 th4)) e0_tm in
598 let th = TRANS th0 th5 in
599 if flag then th else
600 TRANS (INST[tm1, m_var_num; tm2, n_var_num] ADD_COMM) th;;
601
602 (****************************************)
603 (* num_exp_sub *)
604
605 let NUM_EXP_SUB1' = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL) NUM_EXP_SUB1 and
606 NUM_EXP_SUB2' = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL) NUM_EXP_SUB2 and
607 NUM_EXP_LE1' = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL) NUM_EXP_LE1 and
608 NUM_EXP_LE2' = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL) NUM_EXP_LE2;;
609
610 (* Returns two theorems: |- tm1 - tm2 = tm, |- tm2 <= tm1 or
611 |- tm2 - tm1 = tm, |- tm1 <= tm2 *)
612 let num_exp_sub tm1 tm2 =
613 let n1_tm, e1_tm = dest_num_exp tm1 in
614 let n2_tm, e2_tm = dest_num_exp tm2 in
615 let e_sub, e_le = raw_sub_and_le_hash_conv e1_tm e2_tm in
616
617 if rand(concl e_le) = e1_tm then
618 (* e2 <= e1 *)
619 let e1_sub_e2 = rand(concl e_sub) in
620 let a0 = mk_num_exp n1_tm e1_sub_e2 in
621 let b = n2_tm in
622 let a_th = denormalize a0 in
623 let a = rand(concl a_th) in
624
625 let th_sub, th_le = raw_sub_and_le_hash_conv a b in
626 if rand(concl th_le) = a then
627 (* b <= a *)
628 let a_sub_b = TRANS (AP_THM (AP_TERM sub_op_num a_th) b) th_sub in
629 let b_le_a = EQ_MP (SYM (AP_TERM (rator(concl th_le)) a_th)) th_le in
630 let th0 = AP_THM (AP_TERM num_exp_const a_sub_b) e2_tm in
631
632 let inst = INST[n1_tm, n1_var_num; e1_tm, e1_var_num;
633 n2_tm, n2_var_num; e2_tm, e2_var_num; e1_sub_e2, r_var_num] in
634 let th1_sub = inst NUM_EXP_SUB1' in
635 let th1_le = inst NUM_EXP_LE1' in
636 let th2_sub = MY_PROVE_HYP e_sub (MY_PROVE_HYP e_le th1_sub) in
637 let th2_le = MY_PROVE_HYP e_sub (MY_PROVE_HYP b_le_a (MY_PROVE_HYP e_le th1_le)) in
638 TRANS th2_sub th0, th2_le
639
640 else
641 (* a <= b *)
642 let b_sub_a = TRANS (AP_TERM (rator(lhand(concl th_sub))) a_th) th_sub in
643 let a_le_b = EQ_MP (SYM (AP_THM (AP_TERM le_op_num a_th) b)) th_le in
644 let th0 = AP_THM (AP_TERM num_exp_const b_sub_a) e2_tm in
645 let inst = INST[n2_tm, n1_var_num; e2_tm, e1_var_num;
646 n1_tm, n2_var_num; e1_tm, e2_var_num; e1_sub_e2, r_var_num] in
647 let th1_sub = inst NUM_EXP_SUB2' in
648 let th1_le = inst NUM_EXP_LE2' in
649 let th2_sub = MY_PROVE_HYP e_sub (MY_PROVE_HYP e_le th1_sub) in
650 let th2_le = MY_PROVE_HYP e_sub (MY_PROVE_HYP a_le_b (MY_PROVE_HYP e_le th1_le)) in
651 TRANS th2_sub th0, th2_le
652
653 else
654 (* e1 <= e2 *)
655 let e2_sub_e1 = rand(concl e_sub) in
656 let b0 = mk_num_exp n2_tm e2_sub_e1 in
657 let a = n1_tm in
658 let b_th = denormalize b0 in
659 let b = rand(concl b_th) in
660
661 let th_sub, th_le = raw_sub_and_le_hash_conv a b in
662 if rand(concl th_le) = a then
663 (* b <= a *)
664 let a_sub_b = TRANS (AP_TERM (rator(lhand(concl th_sub))) b_th) th_sub in
665 let b_le_a = EQ_MP (SYM (AP_THM (AP_TERM le_op_num b_th) a)) th_le in
666 let th0 = AP_THM (AP_TERM num_exp_const a_sub_b) e1_tm in
667 let inst = INST[n1_tm, n1_var_num; e1_tm, e1_var_num;
668 n2_tm, n2_var_num; e2_tm, e2_var_num; e2_sub_e1, r_var_num] in
669 let th1_sub = inst NUM_EXP_SUB2' in
670 let th1_le = inst NUM_EXP_LE2' in
671 let th2_sub = MY_PROVE_HYP e_sub (MY_PROVE_HYP e_le th1_sub) in
672 let th2_le = MY_PROVE_HYP e_sub (MY_PROVE_HYP b_le_a (MY_PROVE_HYP e_le th1_le)) in
673 TRANS th2_sub th0, th2_le
674
675 else
676 (* a <= b *)
677 let b_sub_a = TRANS (AP_THM (AP_TERM sub_op_num b_th) a) th_sub in
678 let a_le_b = EQ_MP (SYM (AP_TERM (rator(concl th_le)) b_th)) th_le in
679 let th0 = AP_THM (AP_TERM num_exp_const b_sub_a) e1_tm in
680 let inst = INST[n2_tm, n1_var_num; e2_tm, e1_var_num;
681 n1_tm, n2_var_num; e1_tm, e2_var_num; e2_sub_e1, r_var_num] in
682 let th1_sub = inst NUM_EXP_SUB1' in
683 let th1_le = inst NUM_EXP_LE1' in
684 let th2_sub = MY_PROVE_HYP e_sub (MY_PROVE_HYP e_le th1_sub) in
685 let th2_le = MY_PROVE_HYP e_sub (MY_PROVE_HYP a_le_b (MY_PROVE_HYP e_le th1_le)) in
686 TRANS th2_sub th0, th2_le;;
687
688
689 (*************************************)
690 (* division *)
691
692 let NUM_EXP_DIV1' = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o
693 PURE_ONCE_REWRITE_RULE[ARITH_RULE `~(x = 0) <=> (x = 0 <=> F)`] o
694 REWRITE_RULE[GSYM IMP_IMP]) NUM_EXP_DIV1;;
695 let NUM_EXP_DIV2' = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o
696 PURE_ONCE_REWRITE_RULE[ARITH_RULE `~(x = 0) <=> (x = 0 <=> F)`] o
697 REWRITE_RULE[GSYM IMP_IMP]) NUM_EXP_DIV2;;
698
699 let num_exp_div tm1 tm2 =
700 let n1_tm, e1_tm = dest_comb tm1 in
701 let n1_tm = rand n1_tm in
702 let n2_tm, e2_tm = dest_comb tm2 in
703 let n2_tm = rand n2_tm in
704 let e_sub, e_le = raw_sub_and_le_hash_conv e1_tm e2_tm in
705
706 let inst = INST[n1_tm, n1_var_num; e1_tm, e1_var_num;
707 n2_tm, n2_var_num; e2_tm, e2_var_num] in
708
709 let n2_not_0 = raw_eq0_hash_conv n2_tm in
710 if ((fst o dest_const o rand o concl) n2_not_0 = "T") then
711 failwith "num_exp_div: n2 = 0"
712 else
713 if (rand(concl e_le) = e1_tm) then
714 let th0' = inst NUM_EXP_DIV1' in
715 let th0 = MY_PROVE_HYP n2_not_0 (MY_PROVE_HYP e_le th0') in
716
717 let ltm, rtm = dest_comb(rand(concl th0)) in
718 let div_tm, rtm2 = dest_comb ltm in
719 let num_exp_tm = rator rtm2 in
720
721 let th1 = AP_THM (AP_TERM div_tm (AP_TERM num_exp_tm e_sub)) rtm in
722 let ltm, rtm = dest_comb(rand(concl th1)) in
723 let tm1 = rand ltm in
724
725 let th2 = AP_THM (AP_TERM div_tm (denormalize tm1)) rtm in
726 let th3 = raw_div_hash_conv (rand(concl th2)) in
727 let th = TRANS th0 (TRANS th1 (TRANS th2 th3)) in
728 TRANS th (INST[rand(concl th), n_var_num] NUM_EXP_0')
729
730 else
731 let th0' = inst NUM_EXP_DIV2' in
732 let th0 = MY_PROVE_HYP n2_not_0 (MY_PROVE_HYP e_le th0') in
733
734 let ltm, rtm = dest_comb(rand(concl th0)) in
735 let num_exp_tm = rator rtm in
736 let th1 = AP_TERM ltm (AP_TERM num_exp_tm e_sub) in
737
738 let ltm, rtm = dest_comb(rand(concl th1)) in
739 let th2 = AP_TERM ltm (denormalize rtm) in
740 let th3 = raw_div_hash_conv (rand(concl th2)) in
741 let th = TRANS th0 (TRANS th1 (TRANS th2 th3)) in
742 TRANS th (INST[rand(concl th), n_var_num] NUM_EXP_0');;
743
744
745 (*****************************)
746 (* Computes a lower bound for (op tm1 tm2) with p significant digits *)
747 let num_exp_op_lo p op tm1 tm2 =
748 let op_th = op tm1 tm2 in
749 let rtm = rand (concl op_th) in
750 let lo_th = num_exp_lo p rtm in
751 let ltm = rator (concl lo_th) in
752 let th0 = AP_TERM ltm op_th in
753 EQ_MP (SYM th0) lo_th;;
754
755 (* Computes an upper bound for (op tm1 tm2) with p significant digits *)
756 let num_exp_op_hi p op tm1 tm2 =
757 let op_th = op tm1 tm2 in
758 let rtm = rand (concl op_th) in
759 let hi_th = num_exp_hi p rtm in
760 let tm = rand (concl hi_th) in
761 let th0 = AP_THM (AP_TERM le_op_num op_th) tm in
762 EQ_MP (SYM th0) hi_th;;
763
764 (* Computes a strict upper bound for (op tm1 tm2) with p significant digits *)
765 let num_exp_op_hi_lt p op tm1 tm2 =
766 let op_th = op tm1 tm2 in
767 let rtm = rand (concl op_th) in
768 let hi_lt_th = num_exp_hi_lt p rtm in
769 let tm = rand (concl hi_lt_th) in
770 let th0 = AP_THM (AP_TERM lt_op_num op_th) tm in
771 EQ_MP (SYM th0) hi_lt_th;;
772
773 (******************************************)
774 (* float *)
775
776 let mod_plus = new_definition `mod_plus s1 s2 = (~(s1 /\ s2) /\ (s1 \/ s2))`;;
777
778 (********************)
779 (* Float operations *)
780 (********************)
781
782 module Float_ops = struct
783
784 (**********************************)
785
786 (* FLOAT_LT *)
787
788 let FLOAT_LT_FF = prove(`float_num F n1 e1 < float_num F n2 e2 <=> num_exp n1 e1 < num_exp n2 e2`,
789 REWRITE_TAC[float; GSYM REAL_OF_NUM_LT; REAL_MUL_LID; real_div] THEN
790 MATCH_MP_TAC REAL_LT_RMUL_EQ THEN
791 MATCH_MP_TAC REAL_LT_INV THEN
792 REWRITE_TAC[REAL_OF_NUM_LT; LT_NZ; NUM_EXP_EQ_0] THEN
793 ARITH_TAC);;
794
795 let FLOAT_LT_TT = prove(`float_num T n1 e1 < float_num T n2 e2 <=> num_exp n2 e2 < num_exp n1 e1`,
796 REWRITE_TAC[FLOAT_NEG_T; REAL_ARITH `--a < --b <=> b < a`] THEN
797 REWRITE_TAC[FLOAT_LT_FF]);;
798
799 let FLOAT_LT_FT = prove(`float_num F n1 e1 < float_num T n2 e2 <=> F`,
800 MP_TAC (SPECL [`n2:num`; `e2:num`] FLOAT_T_NEG) THEN
801 MP_TAC (SPECL [`n1:num`; `e1:num`] FLOAT_F_POS) THEN
802 REAL_ARITH_TAC);;
803
804 let FLOAT_LT_TF_00 = (PURE_REWRITE_RULE[NUMERAL] o prove)
805 (`float_num T 0 e1 < float_num F 0 e2 <=> F`,
806 MP_TAC (SPECL [`T`; `0`; `e1:num`] FLOAT_EQ_0) THEN
807 MP_TAC (SPECL [`F`; `0`; `e2:num`] FLOAT_EQ_0) THEN
808 REWRITE_TAC[] THEN
809 REPLICATE_TAC 2 (DISCH_THEN (fun th -> REWRITE_TAC[th])) THEN
810 REAL_ARITH_TAC);;
811
812 let FLOAT_LT_TF_1 = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o prove)
813 (`(n1 = 0 <=> F) ==> (float_num T n1 e1 < float_num F n2 e2 <=> T)`,
814 DISCH_TAC THEN
815 MATCH_MP_TAC (REAL_ARITH `a < &0 /\ &0 <= b ==> (a < b <=> T)`) THEN
816 REWRITE_TAC[FLOAT_F_POS] THEN
817 MATCH_MP_TAC (REAL_ARITH `~(a = &0) /\ a <= &0 ==> a < &0`) THEN
818 ASM_REWRITE_TAC[FLOAT_T_NEG; FLOAT_EQ_0]);;
819
820 let FLOAT_LT_TF_2 = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o prove)
821 (`(n2 = 0 <=> F) ==> (float_num T n1 e1 < float_num F n2 e2 <=> T)`,
822 DISCH_TAC THEN
823 MATCH_MP_TAC (REAL_ARITH `a <= &0 /\ &0 < b ==> (a < b <=> T)`) THEN
824 REWRITE_TAC[FLOAT_T_NEG] THEN
825 MATCH_MP_TAC (REAL_ARITH `~(a = &0) /\ &0 <= a ==> &0 < a`) THEN
826 ASM_REWRITE_TAC[FLOAT_F_POS; FLOAT_EQ_0]);;
827
828 let FLOAT_F_LT_0 = prove(`float_num F n e < &0 <=> F`,
829 MP_TAC (SPEC_ALL FLOAT_F_POS) THEN
830 REAL_ARITH_TAC);;
831
832 let FLOAT_T_LT_0 = (CONV_RULE (RAND_CONV (REWRITE_CONV[NUMERAL])) o prove)
833 (`float_num T n e < &0 <=> (0 < n)`,
834 REWRITE_TAC[REAL_ARITH `a < &0 <=> a <= &0 /\ ~(a = &0)`] THEN
835 REWRITE_TAC[FLOAT_T_NEG; FLOAT_EQ_0] THEN
836 ARITH_TAC);;
837
838 let FLOAT_F_GT_0 = (CONV_RULE (RAND_CONV (REWRITE_CONV[NUMERAL])) o prove)
839 (`&0 < float_num F n e <=> 0 < n`,
840 REWRITE_TAC[REAL_ARITH `&0 < a <=> &0 <= a /\ ~(a = &0)`] THEN
841 REWRITE_TAC[FLOAT_F_POS; FLOAT_EQ_0] THEN
842 ARITH_TAC);;
843
844 let FLOAT_T_GT_0 = prove(`&0 < float_num T n e <=> F`,
845 MP_TAC (SPEC_ALL FLOAT_T_NEG) THEN
846 REAL_ARITH_TAC);;
847
848
849 (* float_lt0, float_gt0 *)
850
851 let float_lt0 f1 =
852 let s, n_tm, e_tm = dest_float f1 in
853 let inst = INST[n_tm, n_var_num; e_tm, e_var_num] in
854 if s = "F" then
855 inst FLOAT_F_LT_0
856 else
857 let gt_th = raw_gt0_hash_conv n_tm in
858 TRANS (inst FLOAT_T_LT_0) gt_th;;
859
860 let float_gt0 f1 =
861 let s, n_tm, e_tm = dest_float f1 in
862 let inst = INST[n_tm, n_var_num; e_tm, e_var_num] in
863 if s = "F" then
864 let gt_th = raw_gt0_hash_conv n_tm in
865 TRANS (inst FLOAT_F_GT_0) gt_th
866 else
867 inst FLOAT_T_GT_0;;
868
869 (* float_lt *)
870 let float_lt f1 f2 =
871 let s1, n1, e1 = dest_float f1 in
872 let s2, n2, e2 = dest_float f2 in
873 let inst = INST[n1, n1_var_num; e1, e1_var_num;
874 n2, n2_var_num; e2, e2_var_num] in
875 if s1 = "F" then
876 if s2 = "F" then
877 (* FF *)
878 let th0 = inst FLOAT_LT_FF in
879 let ltm, tm2 = dest_comb (rand (concl th0)) in
880 let lt_th = num_exp_lt (rand ltm) tm2 in
881 TRANS th0 lt_th
882 else
883 (* FT *)
884 inst FLOAT_LT_FT
885 else
886 if s2 = "F" then
887 (* TF *)
888 if (is_const n1 && is_const n2) then
889 (* n1 = _0 and n2 = _0 *)
890 inst FLOAT_LT_TF_00
891 else
892 let n1_0 = raw_eq0_hash_conv n1 in
893 if (fst o dest_const o rand o concl) n1_0 = "F" then
894 (* n1 <> _0 *)
895 MY_PROVE_HYP n1_0 (inst FLOAT_LT_TF_1)
896 else
897 let n2_0 = raw_eq0_hash_conv n2 in
898 if (fst o dest_const o rand o concl) n2_0 = "F" then
899 (* n2 <> _0 *)
900 MY_PROVE_HYP n2_0 (inst FLOAT_LT_TF_2)
901 else
902 failwith "float_lt: D0 _0 exception"
903 else
904 (* TT *)
905 let th0 = inst FLOAT_LT_TT in
906 let ltm, tm2 = dest_comb (rand (concl th0)) in
907 let lt_th = num_exp_lt (rand ltm) tm2 in
908 TRANS th0 lt_th;;
909
910 (**********************************)
911 (* FLOAT_LE *)
912
913 let FLOAT_LE_FF = prove(`float_num F n1 e1 <= float_num F n2 e2 <=> num_exp n1 e1 <= num_exp n2 e2`,
914 REWRITE_TAC[float; GSYM REAL_OF_NUM_LE; REAL_MUL_LID; real_div] THEN
915 MATCH_MP_TAC REAL_LE_RMUL_EQ THEN
916 MATCH_MP_TAC REAL_LT_INV THEN
917 REWRITE_TAC[REAL_OF_NUM_LT; LT_NZ; NUM_EXP_EQ_0] THEN
918 ARITH_TAC);;
919
920 let FLOAT_LE_TT = prove(`float_num T n1 e1 <= float_num T n2 e2 <=> num_exp n2 e2 <= num_exp n1 e1`,
921 REWRITE_TAC[FLOAT_NEG_T; REAL_ARITH `--a <= --b <=> b <= a`] THEN
922 REWRITE_TAC[FLOAT_LE_FF]);;
923
924 let FLOAT_LE_TF = prove(`float_num T n1 e1 <= float_num F n2 e2 <=> T`,
925 MP_TAC (SPECL [`n1:num`; `e1:num`] FLOAT_T_NEG) THEN
926 MP_TAC (SPECL [`n2:num`; `e2:num`] FLOAT_F_POS) THEN
927 REAL_ARITH_TAC);;
928
929 let FLOAT_LE_FT = prove(`float_num F n1 e1 <= float_num T n2 e2 <=> n1 = 0 /\ n2 = 0`,
930 REWRITE_TAC[REAL_LE_LT; FLOAT_LT_FT] THEN EQ_TAC THENL
931 [
932 DISCH_TAC THEN SUBGOAL_THEN `float_num F n1 e1 = &0 /\ float_num T n2 e2 = &0` MP_TAC THENL
933 [
934 MP_TAC (SPECL [`n2:num`; `e2:num`] FLOAT_T_NEG) THEN
935 MP_TAC (SPECL [`n1:num`; `e1:num`] FLOAT_F_POS) THEN
936 ASM_REWRITE_TAC[] THEN REAL_ARITH_TAC;
937 ALL_TAC
938 ] THEN
939 REWRITE_TAC[FLOAT_EQ_0];
940 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
941 REWRITE_TAC[float; NUM_EXP_n0; real_div; REAL_MUL_LZERO; REAL_MUL_RZERO]
942 ]);;
943
944 let FLOAT_LE_FT_00 = (PURE_REWRITE_RULE[NUMERAL] o prove)
945 (`float_num F 0 e1 <= float_num T 0 e2 <=> T`, REWRITE_TAC[FLOAT_LE_FT]);;
946
947 let FLOAT_LE_FT_1 = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o prove)
948 (`(n1 = 0 <=> F) ==> (float_num F n1 e1 <= float_num T n2 e2 <=> F)`,
949 DISCH_TAC THEN ASM_REWRITE_TAC[FLOAT_LE_FT]);;
950
951 let FLOAT_LE_FT_2 = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o prove)
952 (`(n2 = 0 <=> F) ==> (float_num F n1 e1 <= float_num T n2 e2 <=> F)`,
953 DISCH_TAC THEN ASM_REWRITE_TAC[FLOAT_LE_FT]);;
954
955 let FLOAT_F_LE_0 = (CONV_RULE (RAND_CONV (REWRITE_CONV[NUMERAL])) o prove)
956 (`float_num F n e <= &0 <=> n = 0`,
957 REWRITE_TAC[GSYM (SPEC `F` FLOAT_EQ_0)] THEN
958 MP_TAC (SPEC_ALL FLOAT_F_POS) THEN
959 REAL_ARITH_TAC);;
960
961 let FLOAT_T_LE_0 = prove(`float_num T n e <= &0 <=> T`, REWRITE_TAC[FLOAT_T_NEG]);;
962
963 let FLOAT_F_GE_0 = prove(`&0 <= float_num F n e <=> T`, REWRITE_TAC[FLOAT_F_POS]);;
964
965 let FLOAT_T_GE_0 = (CONV_RULE (RAND_CONV (REWRITE_CONV[NUMERAL])) o prove)
966 (`&0 <= float_num T n e <=> n = 0`,
967 REWRITE_TAC[GSYM (SPEC `T` FLOAT_EQ_0)] THEN
968 MP_TAC (SPEC_ALL FLOAT_T_NEG) THEN
969 REAL_ARITH_TAC);;
970
971 (* float_le0, float_ge0 *)
972 let float_le0 f1 =
973 let s, n_tm, e_tm = dest_float f1 in
974 let inst = INST[n_tm, n_var_num; e_tm, e_var_num] in
975 if s = "T" then
976 inst FLOAT_T_LE_0
977 else
978 let eq_th = raw_eq0_hash_conv n_tm in
979 TRANS (inst FLOAT_F_LE_0) eq_th;;
980
981 let float_ge0 f1 =
982 let s, n_tm, e_tm = dest_float f1 in
983 let inst = INST[n_tm, n_var_num; e_tm, e_var_num] in
984 if s = "T" then
985 let eq_th = raw_eq0_hash_conv n_tm in
986 TRANS (inst FLOAT_T_GE_0) eq_th
987 else
988 inst FLOAT_F_GE_0;;
989
990 (* float_le *)
991 let float_le f1 f2 =
992 let s1, n1, e1 = dest_float f1 in
993 let s2, n2, e2 = dest_float f2 in
994 let inst = INST[n1, n1_var_num; e1, e1_var_num;
995 n2, n2_var_num; e2, e2_var_num] in
996 if s2 = "F" then
997 if s1 = "F" then
998 (* FF *)
999 let th0 = inst FLOAT_LE_FF in
1000 let ltm, tm2 = dest_comb (rand (concl th0)) in
1001 let le_th = num_exp_le (rand ltm) tm2 in
1002 TRANS th0 le_th
1003 else
1004 (* TF *)
1005 inst FLOAT_LE_TF
1006 else
1007 if s1 = "F" then
1008 (* FT *)
1009 if (is_const n1 && is_const n2) then
1010 (* n1 = _0 and n2 = _0 *)
1011 inst FLOAT_LE_FT_00
1012 else
1013 let n1_0 = raw_eq0_hash_conv n1 in
1014 if (fst o dest_const o rand o concl) n1_0 = "F" then
1015 (* n1 <> _0 *)
1016 MY_PROVE_HYP n1_0 (inst FLOAT_LE_FT_1)
1017 else
1018 let n2_0 = raw_eq0_hash_conv n2 in
1019 if (fst o dest_const o rand o concl) n2_0 = "F" then
1020 (* n2 <> _0 *)
1021 MY_PROVE_HYP n2_0 (inst FLOAT_LE_FT_2)
1022 else
1023 failwith "float_lt: D0 _0 exception"
1024 else
1025 (* TT *)
1026 let th0 = inst FLOAT_LE_TT in
1027 let ltm, tm2 = dest_comb (rand (concl th0)) in
1028 let le_th = num_exp_le (rand ltm) tm2 in
1029 TRANS th0 le_th;;
1030
1031
1032 (*************************************)
1033 (* float_max, float_min *)
1034
1035 let FLOAT_MIN_1 = (UNDISCH_ALL o prove)(`(f1 <= f2 <=> T) ==> min f1 f2 = f1`, REAL_ARITH_TAC);;
1036 let FLOAT_MIN_2 = (UNDISCH_ALL o prove)(`(f1 <= f2 <=> F) ==> min f1 f2 = f2`, REAL_ARITH_TAC);;
1037
1038 let FLOAT_MAX_1 = (UNDISCH_ALL o prove)(`(f1 <= f2 <=> T) ==> max f1 f2 = f2`, REAL_ARITH_TAC);;
1039 let FLOAT_MAX_2 = (UNDISCH_ALL o prove)(`(f1 <= f2 <=> F) ==> max f1 f2 = f1`, REAL_ARITH_TAC);;
1040
1041 let float_min f1 f2 =
1042 let inst = INST[f1, f1_var_real; f2, f2_var_real] in
1043 let le_th = float_le f1 f2 in
1044 let th0 =
1045 if (fst o dest_const o rand o concl) le_th = "T" then
1046 inst FLOAT_MIN_1
1047 else
1048 inst FLOAT_MIN_2 in
1049 MY_PROVE_HYP le_th th0;;
1050
1051 let float_max f1 f2 =
1052 let inst = INST[f1, f1_var_real; f2, f2_var_real] in
1053 let le_th = float_le f1 f2 in
1054 let th0 =
1055 if (fst o dest_const o rand o concl) le_th = "T" then
1056 inst FLOAT_MAX_1
1057 else
1058 inst FLOAT_MAX_2 in
1059 MY_PROVE_HYP le_th th0;;
1060
1061 let float_min_max f1 f2 =
1062 let inst = INST[f1, f1_var_real; f2, f2_var_real] in
1063 let le_th = float_le f1 f2 in
1064 let th_min, th_max =
1065 if (fst o dest_const o rand o concl) le_th = "T" then
1066 inst FLOAT_MIN_1, inst FLOAT_MAX_1
1067 else
1068 inst FLOAT_MIN_2, inst FLOAT_MAX_2 in
1069 MY_PROVE_HYP le_th th_min, MY_PROVE_HYP le_th th_max;;
1070
1071
1072 (*************************************)
1073 (* FLOAT_MUL *)
1074
1075 let FLOAT_MUL = prove(`!s1 s2. min_exp <= e /\ num_exp n1 e1 * num_exp n2 e2 = num_exp n e
1076 ==> float_num s1 n1 e1 * float_num s2 n2 e2 =
1077 float_num (mod_plus s1 s2) n (e - min_exp)`,
1078 REPEAT STRIP_TAC THEN
1079 REWRITE_TAC[float] THEN
1080 ONCE_REWRITE_TAC[REAL_ARITH `(a * b / c) * (d * e / f) = (a * d) * (b * e) / c / f`] THEN
1081
1082 SUBGOAL_THEN `(if s1 then -- &1 else &1) * (if s2 then -- &1 else &1) = if mod_plus s1 s2 then -- &1 else &1` MP_TAC THENL
1083 [
1084 REWRITE_TAC[mod_plus] THEN
1085 COND_CASES_TAC THEN COND_CASES_TAC THEN
1086 REWRITE_TAC[REAL_ARITH `-- &1 * -- &1 = &1`; REAL_MUL_LID; REAL_MUL_RID];
1087 ALL_TAC
1088 ] THEN
1089
1090 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
1091 REWRITE_TAC[real_div] THEN
1092 REWRITE_TAC[GSYM REAL_MUL_ASSOC] THEN
1093 REWRITE_TAC[REAL_EQ_MUL_LCANCEL] THEN
1094 DISJ2_TAC THEN
1095
1096 MP_TAC (SPECL[`n:num`; `e:num`; `min_exp`] NUM_EXP_SUB_lemma) THEN
1097 ASM_REWRITE_TAC[] THEN
1098 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
1099 REWRITE_TAC[REAL_MUL_ASSOC] THEN
1100 ASM_REWRITE_TAC[REAL_OF_NUM_MUL]);;
1101
1102 let FLOAT_MUL_FF = prove(`min_exp <= e /\ e - min_exp = r /\ num_exp n1 e1 * num_exp n2 e2 = num_exp n e ==>
1103 float_num F n1 e1 * float_num F n2 e2 = float_num F n r`,
1104 SIMP_TAC[FLOAT_MUL; mod_plus]);;
1105 let FLOAT_MUL_FT = prove(`min_exp <= e /\ e - min_exp = r /\ num_exp n1 e1 * num_exp n2 e2 = num_exp n e ==>
1106 float_num F n1 e1 * float_num T n2 e2 = float_num T n r`,
1107 SIMP_TAC[FLOAT_MUL; mod_plus]);;
1108 let FLOAT_MUL_TF = prove(`min_exp <= e /\ e - min_exp = r /\ num_exp n1 e1 * num_exp n2 e2 = num_exp n e ==>
1109 float_num T n1 e1 * float_num F n2 e2 = float_num T n r`,
1110 SIMP_TAC[FLOAT_MUL; mod_plus]);;
1111 let FLOAT_MUL_TT = prove(`min_exp <= e /\ e - min_exp = r /\ num_exp n1 e1 * num_exp n2 e2 = num_exp n e ==>
1112 float_num T n1 e1 * float_num T n2 e2 = float_num F n r`,
1113 SIMP_TAC[FLOAT_MUL; mod_plus]);;
1114
1115
1116 let FLOAT_MUL_0x_hi, FLOAT_MUL_0x_lo, FLOAT_MUL_x0_hi, FLOAT_MUL_x0_lo =
1117 let mul_0x_hi = `(n1 = 0 <=> T) ==> float_num s1 n1 e1 * f2 <= float_num F 0 min_exp` in
1118 let mul_0x_lo = `(n1 = 0 <=> T) ==> float_num F 0 min_exp <= float_num s1 n1 e1 * f2` in
1119 let mul_x0_hi = `(n2 = 0 <=> T) ==> f1 * float_num s2 n2 e2 <= float_num F 0 min_exp` in
1120 let mul_x0_lo = `(n2 = 0 <=> T) ==> float_num F 0 min_exp <= f1 * float_num s2 n2 e2` in
1121 let proof = MP_TAC (GEN_ALL (SPECL [`s:bool`; `0`] FLOAT_EQ_0)) THEN
1122 SIMP_TAC[REAL_MUL_LZERO; REAL_MUL_RZERO; REAL_LE_REFL] in
1123 prove(mul_0x_hi, proof), prove(mul_0x_lo, proof),
1124 prove(mul_x0_hi, proof), prove(mul_x0_lo, proof);;
1125
1126
1127 let FLOAT_MUL_FF_hi, FLOAT_MUL_FF_lo =
1128 let ff_hi = `min_exp <= e /\ e - min_exp = r /\ num_exp n1 e1 * num_exp n2 e2 <= num_exp n e
1129 ==> float_num F n1 e1 * float_num F n2 e2 <= float_num F n r` in
1130 let ff_lo = `min_exp <= e /\ e - min_exp = r /\ num_exp n e <= num_exp n1 e1 * num_exp n2 e2
1131 ==> float_num F n r <= float_num F n1 e1 * float_num F n2 e2` in
1132 let proof =
1133 REPEAT STRIP_TAC THEN
1134 POP_ASSUM MP_TAC THEN
1135 POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN
1136 REWRITE_TAC[GSYM REAL_OF_NUM_LE; GSYM REAL_OF_NUM_MUL] THEN
1137 DISCH_TAC THEN
1138 MAP_EVERY ABBREV_TAC [`z = &(num_exp n e)`; `x = &(num_exp n1 e1)`; `y = &(num_exp n2 e2)`] THEN
1139 ASM_REWRITE_TAC[float; REAL_MUL_LID] THEN
1140 REWRITE_TAC[REAL_ARITH `a / b * c / d = (a * c) / b / d`] THEN
1141 REWRITE_TAC[real_div] THEN
1142 REWRITE_TAC[REAL_MUL_ASSOC] THEN
1143 MATCH_MP_TAC REAL_LE_RMUL THEN
1144 REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS] THEN
1145
1146 MP_TAC (SPECL [`n:num`; `e:num`; `min_exp`] NUM_EXP_SUB_lemma) THEN
1147 ASM_REWRITE_TAC[] THEN
1148 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
1149 MATCH_MP_TAC REAL_LE_RMUL THEN
1150 ASM_REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS] in
1151 prove(ff_hi, proof), prove(ff_lo, proof);;
1152
1153 let FLOAT_MUL_TT_hi, FLOAT_MUL_TT_lo =
1154 let tt_hi = `min_exp <= e /\ e - min_exp = r /\ num_exp n1 e1 * num_exp n2 e2 <= num_exp n e
1155 ==> float_num T n1 e1 * float_num T n2 e2 <= float_num F n r` in
1156 let tt_lo = `min_exp <= e /\ e - min_exp = r /\ num_exp n e <= num_exp n1 e1 * num_exp n2 e2
1157 ==> float_num F n r <= float_num T n1 e1 * float_num T n2 e2` in
1158 let proof =
1159 REWRITE_TAC[FLOAT_NEG_T] THEN
1160 REWRITE_TAC[REAL_ARITH `--a * --b = a * b`] THEN
1161 REWRITE_TAC[FLOAT_MUL_FF_hi; FLOAT_MUL_FF_lo] in
1162 prove(tt_hi, proof), prove(tt_lo, proof);;
1163
1164 let FLOAT_MUL_FT_hi, FLOAT_MUL_FT_lo =
1165 let ft_hi = `min_exp <= e /\ e - min_exp = r /\ num_exp n e <= num_exp n1 e1 * num_exp n2 e2
1166 ==> float_num F n1 e1 * float_num T n2 e2 <= float_num T n r` in
1167 let ft_lo = `min_exp <= e /\ e - min_exp = r /\ num_exp n1 e1 * num_exp n2 e2 <= num_exp n e
1168 ==> float_num T n r <= float_num F n1 e1 * float_num T n2 e2` in
1169 let proof =
1170 REWRITE_TAC[FLOAT_NEG_T] THEN
1171 REWRITE_TAC[REAL_ARITH `a * --b <= --c <=> c <= a * b`] THEN
1172 REWRITE_TAC[REAL_ARITH `--c <= a * --b <=> a * b <= c`] THEN
1173 REWRITE_TAC[FLOAT_MUL_FF_hi; FLOAT_MUL_FF_lo] in
1174 prove(ft_hi, proof), prove(ft_lo, proof);;
1175
1176 let FLOAT_MUL_TF_hi, FLOAT_MUL_TF_lo =
1177 let ft_hi = `min_exp <= e /\ e - min_exp = r /\ num_exp n e <= num_exp n1 e1 * num_exp n2 e2
1178 ==> float_num T n1 e1 * float_num F n2 e2 <= float_num T n r` in
1179 let ft_lo = `min_exp <= e /\ e - min_exp = r /\ num_exp n1 e1 * num_exp n2 e2 <= num_exp n e
1180 ==> float_num T n r <= float_num T n1 e1 * float_num F n2 e2` in
1181 let proof =
1182 REWRITE_TAC[FLOAT_NEG_T] THEN
1183 REWRITE_TAC[REAL_ARITH `--a * b <= --c <=> c <= a * b`] THEN
1184 REWRITE_TAC[REAL_ARITH `--c <= --a * b <=> a * b <= c`] THEN
1185 REWRITE_TAC[FLOAT_MUL_FF_hi; FLOAT_MUL_FF_lo] in
1186 prove(ft_hi, proof), prove(ft_lo, proof);;
1187
1188
1189 (*********************************************)
1190 (* float_mul_lo, float_mul_hi *)
1191
1192 let transform = UNDISCH_ALL o NUMERALS_TO_NUM o PURE_REWRITE_RULE[min_exp_def; GSYM IMP_IMP];;
1193 let FLOAT_MUL_FF_hi' = transform FLOAT_MUL_FF_hi and
1194 FLOAT_MUL_FF_lo' = transform FLOAT_MUL_FF_lo and
1195 FLOAT_MUL_TT_hi' = transform FLOAT_MUL_TT_hi and
1196 FLOAT_MUL_TT_lo' = transform FLOAT_MUL_TT_lo and
1197 FLOAT_MUL_FT_hi' = transform FLOAT_MUL_FT_hi and
1198 FLOAT_MUL_FT_lo' = transform FLOAT_MUL_FT_lo and
1199 FLOAT_MUL_TF_hi' = transform FLOAT_MUL_TF_hi and
1200 FLOAT_MUL_TF_lo' = transform FLOAT_MUL_TF_lo and
1201 FLOAT_MUL_0x_hi' = transform FLOAT_MUL_0x_hi and
1202 FLOAT_MUL_0x_lo' = transform FLOAT_MUL_0x_lo and
1203 FLOAT_MUL_x0_hi' = transform FLOAT_MUL_x0_hi and
1204 FLOAT_MUL_x0_lo' = transform FLOAT_MUL_x0_lo;;
1205
1206 let FLOAT_MUL_FF' = transform FLOAT_MUL_FF and
1207 FLOAT_MUL_TT' = transform FLOAT_MUL_TT and
1208 FLOAT_MUL_FT' = transform FLOAT_MUL_FT and
1209 FLOAT_MUL_TF' = transform FLOAT_MUL_TF;;
1210
1211 let float_mul_eq f1 f2 =
1212 let s1, n1, e1 = dest_float f1 and
1213 s2, n2, e2 = dest_float f2 in
1214 let flag = s1 = s2 in
1215 let num_exp1 = mk_num_exp n1 e1 and
1216 num_exp2 = mk_num_exp n2 e2 in
1217
1218 let mul_th = num_exp_mul num_exp1 num_exp2 in
1219 let n_tm, e_tm = dest_num_exp (rand (concl mul_th)) in
1220
1221 let sub_th, le_th = raw_sub_and_le_hash_conv e_tm min_exp_num_const in
1222 if (rand(concl le_th) <> e_tm) then
1223 failwith "float_mul_eq: underflow"
1224 else
1225 let r_tm = rand(concl sub_th) in
1226 let inst = INST[e_tm, e_var_num; r_tm, r_var_num; n_tm, n_var_num;
1227 n1, n1_var_num; e1, e1_var_num; n2, n2_var_num; e2, e2_var_num] in
1228 let th0 = inst
1229 (if flag then
1230 if s1 = "F" then FLOAT_MUL_FF' else FLOAT_MUL_TT'
1231 else
1232 if s1 = "F" then FLOAT_MUL_FT' else FLOAT_MUL_TF') in
1233 MY_PROVE_HYP sub_th (MY_PROVE_HYP mul_th (MY_PROVE_HYP le_th th0));;
1234
1235
1236 let float_mul_lo pp f1 f2 =
1237 let s1, n1, e1 = dest_float f1 and
1238 s2, n2, e2 = dest_float f2 in
1239 (* Multiplication by zero *)
1240 let n1_eq0_th = raw_eq0_hash_conv n1 in
1241 if (rand o concl) n1_eq0_th = t_const then
1242 (MY_PROVE_HYP n1_eq0_th o
1243 INST[e1, e1_var_num; f2, f2_var_real; n1, n1_var_num;
1244 (if s1 = "T" then t_const else f_const), s1_var_bool]) FLOAT_MUL_0x_lo'
1245 else
1246 let n2_eq0_th = raw_eq0_hash_conv n2 in
1247 if (rand o concl) n2_eq0_th = t_const then
1248 (MY_PROVE_HYP n2_eq0_th o
1249 INST[e2, e2_var_num; f1, f1_var_real; n2, n2_var_num;
1250 (if s2 = "T" then t_const else f_const), s2_var_bool]) FLOAT_MUL_x0_lo'
1251 else
1252 let flag = s1 = s2 in
1253 let num_exp1 = mk_num_exp n1 e1 and
1254 num_exp2 = mk_num_exp n2 e2 in
1255
1256 let mul_th, n_tm, e_tm =
1257 if flag then
1258 let th = num_exp_op_lo pp num_exp_mul num_exp1 num_exp2 in
1259 let n_tm, e_tm = dest_num_exp (lhand (concl th)) in
1260 th, n_tm, e_tm
1261 else
1262 let th = num_exp_op_hi pp num_exp_mul num_exp1 num_exp2 in
1263 let n_tm, e_tm = dest_num_exp (rand (concl th)) in
1264 th, n_tm, e_tm in
1265
1266 let sub_th, le_th = raw_sub_and_le_hash_conv e_tm min_exp_num_const in
1267 if (rand(concl le_th) <> e_tm) then
1268 failwith "float_mul_lo: underflow"
1269 else
1270 let r_tm = rand(concl sub_th) in
1271 let inst = INST[e_tm, e_var_num; r_tm, r_var_num; n_tm, n_var_num;
1272 n1, n1_var_num; e1, e1_var_num; n2, n2_var_num; e2, e2_var_num] in
1273 let th0 = inst
1274 (if flag then
1275 if s1 = "F" then FLOAT_MUL_FF_lo' else FLOAT_MUL_TT_lo'
1276 else
1277 if s1 = "F" then FLOAT_MUL_FT_lo' else FLOAT_MUL_TF_lo') in
1278 MY_PROVE_HYP sub_th (MY_PROVE_HYP mul_th (MY_PROVE_HYP le_th th0));;
1279
1280
1281 let float_mul_hi pp f1 f2 =
1282 let s1, n1, e1 = dest_float f1 and
1283 s2, n2, e2 = dest_float f2 in
1284 (* Multiplication by zero *)
1285 let n1_eq0_th = raw_eq0_hash_conv n1 in
1286 if (rand o concl) n1_eq0_th = t_const then
1287 (MY_PROVE_HYP n1_eq0_th o
1288 INST[e1, e1_var_num; f2, f2_var_real; n1, n1_var_num;
1289 (if s1 = "T" then t_const else f_const), s1_var_bool]) FLOAT_MUL_0x_hi'
1290 else
1291 let n2_eq0_th = raw_eq0_hash_conv n2 in
1292 if (rand o concl) n2_eq0_th = t_const then
1293 (MY_PROVE_HYP n2_eq0_th o
1294 INST[e2, e2_var_num; f1, f1_var_real; n2, n2_var_num;
1295 (if s2 = "T" then t_const else f_const), s2_var_bool]) FLOAT_MUL_x0_hi'
1296 else
1297 let flag = s1 = s2 in
1298 let num_exp1 = mk_num_exp n1 e1 and
1299 num_exp2 = mk_num_exp n2 e2 in
1300
1301 let mul_th, n_tm, e_tm =
1302 if flag then
1303 let th = num_exp_op_hi pp num_exp_mul num_exp1 num_exp2 in
1304 let n_tm, e_tm = dest_num_exp (rand (concl th)) in
1305 th, n_tm, e_tm
1306 else
1307 let th = num_exp_op_lo pp num_exp_mul num_exp1 num_exp2 in
1308 let n_tm, e_tm = dest_num_exp (lhand (concl th)) in
1309 th, n_tm, e_tm in
1310
1311 let sub_th, le_th = raw_sub_and_le_hash_conv e_tm min_exp_num_const in
1312 if (rand(concl le_th) <> e_tm) then
1313 failwith "float_mul_hi: underflow"
1314 else
1315 let r_tm = rand(concl sub_th) in
1316 let inst = INST[e_tm, e_var_num; r_tm, r_var_num; n_tm, n_var_num;
1317 n1, n1_var_num; e1, e1_var_num; n2, n2_var_num; e2, e2_var_num] in
1318 let th0 = inst
1319 (if flag then
1320 if s1 = "F" then FLOAT_MUL_FF_hi' else FLOAT_MUL_TT_hi'
1321 else
1322 if s1 = "F" then FLOAT_MUL_FT_hi' else FLOAT_MUL_TF_hi') in
1323 MY_PROVE_HYP sub_th (MY_PROVE_HYP mul_th (MY_PROVE_HYP le_th th0));;
1324
1325
1326
1327 (*********************************************)
1328 (* FLOAT_DIV *)
1329
1330 let DIV_lemma = prove(`!x y. ~(y = 0) ==> &(x DIV y) <= &x / &y /\ &x / &y <= &(x DIV y + 1)`,
1331 REPEAT GEN_TAC THEN DISCH_TAC THEN
1332 MP_TAC (SPECL [`y:num`; `x:num`] FLOOR_DIV_DIV) THEN
1333 ASM_REWRITE_TAC[GSYM REAL_OF_NUM_ADD] THEN
1334 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
1335 SIMP_TAC[FLOOR; REAL_LT_IMP_LE]);;
1336
1337 let FLOAT_DIV_FF = prove(`e2 + k <= min_exp + e + e1 /\ ~(n2 = 0) /\
1338 num_exp n1 k DIV num_exp n2 0 = num_exp n e
1339 ==> float_num F n ((min_exp + e + e1) - (e2 + k)) <= float_num F n1 e1 / float_num F n2 e2`,
1340 MAP_EVERY ABBREV_TAC [`z = num_exp n e`; `x = num_exp n1 k`; `y = num_exp n2 0`] THEN
1341 REPEAT STRIP_TAC THEN
1342 REWRITE_TAC[float; REAL_MUL_LID] THEN
1343 REWRITE_TAC[real_div; REAL_INV_MUL; REAL_INV_INV] THEN
1344 REWRITE_TAC[REAL_ARITH `(a * b) * c * d = (b * d) * (a * c)`] THEN
1345 SUBGOAL_THEN `~(&(num_exp 1 min_exp) = &0)` ASSUME_TAC THENL
1346 [
1347 REWRITE_TAC[num_exp; REAL_OF_NUM_EQ; MULT_CLAUSES; EXP_EQ_0] THEN
1348 ARITH_TAC;
1349 ALL_TAC
1350 ] THEN
1351
1352 ASM_SIMP_TAC[REAL_MUL_LINV; REAL_MUL_LID] THEN
1353
1354 ASM_SIMP_TAC[NUM_EXP_SUB_lemma] THEN
1355 SUBGOAL_THEN `&(num_exp n1 e1) * inv(&(num_exp n2 e2)) = (&x / &y) * &(num_exp 1 e1) * inv(&(num_exp 1 (e2 + k)))` MP_TAC THENL
1356 [
1357 EXPAND_TAC "x" THEN EXPAND_TAC "y" THEN
1358 REWRITE_TAC[real_div] THEN
1359 REWRITE_TAC[num_exp; GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_POW] THEN
1360 REWRITE_TAC[REAL_MUL_LID; REAL_INV_MUL; REAL_INV_1; real_pow; REAL_MUL_RID] THEN
1361 REWRITE_TAC[REAL_POW_ADD; REAL_INV_MUL] THEN
1362 REWRITE_TAC[REAL_ARITH `((a * b) * c) * d * e * f = (b * f) * (a * c * d * e)`] THEN
1363
1364 SUBGOAL_THEN (mk_comb(`(~)`, mk_eq(mk_binop `pow` (mk_comb (`&`, base_const)) `k:num`, `&0`))) ASSUME_TAC THENL
1365 [
1366 REWRITE_TAC[REAL_POW_EQ_0] THEN
1367 REAL_ARITH_TAC;
1368 ALL_TAC
1369 ] THEN
1370
1371 ASM_SIMP_TAC[REAL_MUL_RINV; REAL_MUL_LID] THEN
1372 REAL_ARITH_TAC;
1373 ALL_TAC
1374 ] THEN
1375
1376 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
1377 ONCE_REWRITE_TAC[REAL_ARITH `(a * b) * c = (a * c) * b`] THEN
1378 REWRITE_TAC[REAL_MUL_ASSOC] THEN
1379 MATCH_MP_TAC REAL_LE_RMUL THEN
1380 REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS] THEN
1381 ONCE_REWRITE_TAC[NUM_EXP_SUM1] THEN
1382 REWRITE_TAC[NUM_EXP_SUM] THEN
1383 REWRITE_TAC[GSYM REAL_OF_NUM_MUL] THEN
1384 ASM_REWRITE_TAC[REAL_ARITH `(a * b * c) * d = (d * a) * b * c`] THEN
1385 ASM_SIMP_TAC[REAL_MUL_LINV; REAL_MUL_LID] THEN
1386 MATCH_MP_TAC REAL_LE_RMUL THEN
1387 REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS] THEN
1388 MP_TAC (SPEC_ALL DIV_lemma) THEN
1389 ANTS_TAC THENL
1390 [
1391 EXPAND_TAC "y" THEN
1392 REWRITE_TAC[num_exp; MULT_EQ_0; DE_MORGAN_THM] THEN
1393 ASM_REWRITE_TAC[EXP] THEN
1394 ARITH_TAC;
1395 ALL_TAC
1396 ] THEN
1397
1398 ASM_SIMP_TAC[]);;
1399
1400 let FLOAT_DIV_0x_lo = prove(`(n1 = 0 <=> T) ==> float_num F 0 min_exp <= float_num s1 n1 e1 / f2`,
1401 SIMP_TAC[real_div; FLOAT_MUL_0x_lo]);;
1402
1403 let FLOAT_DIV_0x_hi = prove(`(n1 = 0 <=> T) ==> float_num s1 n1 e1 / f2 <= float_num F 0 min_exp`,
1404 SIMP_TAC[real_div; FLOAT_MUL_0x_hi]);;
1405
1406 let FLOAT_DIV_FF_lo = prove(`e2 + k = r1 /\ min_exp + e + e1 = r2 /\ r2 - r1 = r /\
1407 r1 <= r2 /\ ~(n2 = 0) /\
1408 num_exp n e <= num_exp n1 k DIV num_exp n2 0
1409 ==> float_num F n r <= float_num F n1 e1 / float_num F n2 e2`,
1410 MAP_EVERY ABBREV_TAC [`z = num_exp n e`; `x = num_exp n1 k`; `y = num_exp n2 0`] THEN
1411 REPEAT STRIP_TAC THEN
1412 REPLICATE_TAC 3 (POP_ASSUM MP_TAC) THEN
1413 REPLICATE_TAC 3 (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
1414 REPEAT STRIP_TAC THEN
1415 REWRITE_TAC[float; REAL_MUL_LID] THEN
1416 REWRITE_TAC[real_div; REAL_INV_MUL; REAL_INV_INV] THEN
1417 REWRITE_TAC[REAL_ARITH `(a * b) * c * d = (b * d) * (a * c)`] THEN
1418 SUBGOAL_THEN `~(&(num_exp 1 min_exp) = &0)` ASSUME_TAC THENL
1419 [
1420 REWRITE_TAC[num_exp; REAL_OF_NUM_EQ; MULT_CLAUSES; EXP_EQ_0] THEN
1421 ARITH_TAC;
1422 ALL_TAC
1423 ] THEN
1424
1425 ASM_SIMP_TAC[REAL_MUL_LINV; REAL_MUL_LID] THEN
1426
1427 ASM_SIMP_TAC[NUM_EXP_SUB_lemma] THEN
1428 SUBGOAL_THEN `&(num_exp n1 e1) * inv(&(num_exp n2 e2)) = (&x / &y) * &(num_exp 1 e1) * inv(&(num_exp 1 (e2 + k)))` MP_TAC THENL
1429 [
1430 EXPAND_TAC "x" THEN EXPAND_TAC "y" THEN
1431 REWRITE_TAC[real_div] THEN
1432 REWRITE_TAC[num_exp; GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_POW] THEN
1433 REWRITE_TAC[REAL_MUL_LID; REAL_INV_MUL; REAL_INV_1; real_pow; REAL_MUL_RID] THEN
1434 REWRITE_TAC[REAL_POW_ADD; REAL_INV_MUL] THEN
1435 REWRITE_TAC[REAL_ARITH `((a * b) * c) * d * e * f = (b * f) * (a * c * d * e)`] THEN
1436 SUBGOAL_THEN
1437 (mk_comb(`(~)`, mk_eq(mk_binop `pow` (mk_comb (`&`, base_const)) `k:num`, `&0`))) ASSUME_TAC THENL
1438 [
1439 REWRITE_TAC[REAL_POW_EQ_0] THEN
1440 REAL_ARITH_TAC;
1441 ALL_TAC
1442 ] THEN
1443
1444 ASM_SIMP_TAC[REAL_MUL_RINV; REAL_MUL_LID] THEN
1445 REAL_ARITH_TAC;
1446 ALL_TAC
1447 ] THEN
1448
1449 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
1450 ONCE_REWRITE_TAC[REAL_ARITH `(a * b) * c = (a * c) * b`] THEN
1451 REWRITE_TAC[REAL_MUL_ASSOC] THEN
1452 MATCH_MP_TAC REAL_LE_RMUL THEN
1453 REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS] THEN
1454 ONCE_REWRITE_TAC[NUM_EXP_SUM1] THEN
1455 REWRITE_TAC[NUM_EXP_SUM] THEN
1456 REWRITE_TAC[GSYM REAL_OF_NUM_MUL] THEN
1457 ASM_REWRITE_TAC[REAL_ARITH `(a * b * c) * d = (d * a) * b * c`] THEN
1458 ASM_SIMP_TAC[REAL_MUL_LINV; REAL_MUL_LID] THEN
1459 MATCH_MP_TAC REAL_LE_RMUL THEN
1460 REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS] THEN
1461 MP_TAC (SPEC_ALL DIV_lemma) THEN
1462 ANTS_TAC THENL
1463 [
1464 EXPAND_TAC "y" THEN
1465 REWRITE_TAC[num_exp; MULT_EQ_0; DE_MORGAN_THM] THEN
1466 ASM_REWRITE_TAC[EXP] THEN
1467 ARITH_TAC;
1468 ALL_TAC
1469 ] THEN
1470
1471 STRIP_TAC THEN
1472 MATCH_MP_TAC REAL_LE_TRANS THEN
1473 EXISTS_TAC `&(x DIV y)` THEN
1474 ASM_REWRITE_TAC[REAL_OF_NUM_LE]);;
1475
1476 let FLOAT_DIV_FF_hi = prove(`e2 + k = r1 /\ min_exp + e + e1 = r2 /\ r2 - r1 = r /\
1477 r1 <= r2 /\ ~(n2 = 0) /\
1478 num_exp n1 k DIV num_exp n2 0 < num_exp n e
1479 ==> float_num F n1 e1 / float_num F n2 e2 <= float_num F n r`,
1480 MAP_EVERY ABBREV_TAC [`z = num_exp n e`; `x = num_exp n1 k`; `y = num_exp n2 0`] THEN
1481 REPEAT STRIP_TAC THEN
1482 REPLICATE_TAC 3 (POP_ASSUM MP_TAC) THEN
1483 REPLICATE_TAC 3 (POP_ASSUM (fun th -> REWRITE_TAC[SYM th])) THEN
1484 REPEAT STRIP_TAC THEN
1485 REWRITE_TAC[float; REAL_MUL_LID] THEN
1486 REWRITE_TAC[real_div; REAL_INV_MUL; REAL_INV_INV] THEN
1487 REWRITE_TAC[REAL_ARITH `(a * b) * c * d = (b * d) * (a * c)`] THEN
1488 SUBGOAL_THEN `~(&(num_exp 1 min_exp) = &0)` ASSUME_TAC THENL
1489 [
1490 REWRITE_TAC[num_exp; REAL_OF_NUM_EQ; MULT_CLAUSES; EXP_EQ_0] THEN
1491 ARITH_TAC;
1492 ALL_TAC
1493 ] THEN
1494
1495 ASM_SIMP_TAC[REAL_MUL_LINV; REAL_MUL_LID] THEN
1496
1497 ASM_SIMP_TAC[NUM_EXP_SUB_lemma] THEN
1498 SUBGOAL_THEN `&(num_exp n1 e1) * inv(&(num_exp n2 e2)) = (&x / &y) * &(num_exp 1 e1) * inv(&(num_exp 1 (e2 + k)))` MP_TAC THENL
1499 [
1500 EXPAND_TAC "x" THEN EXPAND_TAC "y" THEN
1501 REWRITE_TAC[real_div] THEN
1502 REWRITE_TAC[num_exp; GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_POW] THEN
1503 REWRITE_TAC[REAL_MUL_LID; REAL_INV_MUL; REAL_INV_1; real_pow; REAL_MUL_RID] THEN
1504 REWRITE_TAC[REAL_POW_ADD; REAL_INV_MUL] THEN
1505 REWRITE_TAC[REAL_ARITH `((a * b) * c) * d * e * f = (b * f) * (a * c * d * e)`] THEN
1506 SUBGOAL_THEN
1507 (mk_comb(`(~)`, mk_eq(mk_binop `pow` (mk_comb (`&`, base_const)) `k:num`, `&0`))) ASSUME_TAC THENL
1508 [
1509 REWRITE_TAC[REAL_POW_EQ_0] THEN
1510 REAL_ARITH_TAC;
1511 ALL_TAC
1512 ] THEN
1513
1514 ASM_SIMP_TAC[REAL_MUL_RINV; REAL_MUL_LID] THEN
1515 REAL_ARITH_TAC;
1516 ALL_TAC
1517 ] THEN
1518
1519 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
1520 ONCE_REWRITE_TAC[REAL_ARITH `(a * b) * c = (a * c) * b`] THEN
1521 REWRITE_TAC[REAL_MUL_ASSOC] THEN
1522 MATCH_MP_TAC REAL_LE_RMUL THEN
1523 REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS] THEN
1524 ONCE_REWRITE_TAC[NUM_EXP_SUM1] THEN
1525 REWRITE_TAC[NUM_EXP_SUM] THEN
1526 REWRITE_TAC[GSYM REAL_OF_NUM_MUL] THEN
1527 ASM_REWRITE_TAC[REAL_ARITH `(a * b * c) * d = (d * a) * b * c`] THEN
1528 ASM_SIMP_TAC[REAL_MUL_LINV; REAL_MUL_LID] THEN
1529 MATCH_MP_TAC REAL_LE_RMUL THEN
1530 REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS] THEN
1531 MP_TAC (SPEC_ALL DIV_lemma) THEN
1532 ANTS_TAC THENL
1533 [
1534 EXPAND_TAC "y" THEN
1535 REWRITE_TAC[num_exp; MULT_EQ_0; DE_MORGAN_THM] THEN
1536 ASM_REWRITE_TAC[EXP] THEN
1537 ARITH_TAC;
1538 ALL_TAC
1539 ] THEN
1540
1541 STRIP_TAC THEN
1542 MATCH_MP_TAC REAL_LE_TRANS THEN
1543 EXISTS_TAC `&(x DIV y + 1)` THEN
1544 ASM_REWRITE_TAC[REAL_OF_NUM_LE] THEN
1545 UNDISCH_TAC `x DIV y < z` THEN
1546 ARITH_TAC);;
1547
1548 let FLOAT_DIV_TT_lo = prove(`e2 + k = r1 /\ min_exp + e + e1 = r2 /\ r2 - r1 = r /\
1549 r1 <= r2 /\ ~(n2 = 0) /\
1550 num_exp n e <= num_exp n1 k DIV num_exp n2 0
1551 ==> float_num F n r <= float_num T n1 e1 / float_num T n2 e2`,
1552 REWRITE_TAC[FLOAT_NEG_T] THEN
1553 REWRITE_TAC[real_div; REAL_INV_NEG; REAL_NEG_MUL2] THEN
1554 REWRITE_TAC[GSYM real_div] THEN
1555 REWRITE_TAC[FLOAT_DIV_FF_lo]);;
1556
1557 let FLOAT_DIV_TT_hi = prove(`e2 + k = r1 /\ min_exp + e + e1 = r2 /\
1558 r2 - r1 = r /\ r1 <= r2 /\ ~(n2 = 0) /\
1559 num_exp n1 k DIV num_exp n2 0 < num_exp n e
1560 ==> float_num T n1 e1 / float_num T n2 e2 <= float_num F n r`,
1561 REWRITE_TAC[FLOAT_NEG_T] THEN
1562 REWRITE_TAC[real_div; REAL_INV_NEG; REAL_NEG_MUL2] THEN
1563 REWRITE_TAC[GSYM real_div] THEN
1564 REWRITE_TAC[FLOAT_DIV_FF_hi]);;
1565
1566
1567 let FLOAT_DIV_FT_lo = prove(`e2 + k = r1 /\ min_exp + e + e1 = r2 /\
1568 r2 - r1 = r /\ r1 <= r2 /\ ~(n2 = 0) /\
1569 num_exp n1 k DIV num_exp n2 0 < num_exp n e
1570 ==> float_num T n r <= float_num F n1 e1 / float_num T n2 e2`,
1571 REWRITE_TAC[FLOAT_NEG_T] THEN
1572 REWRITE_TAC[real_div; REAL_INV_NEG] THEN
1573 REWRITE_TAC[REAL_ARITH `--a <= b * --c <=> b * c <= a`] THEN
1574 REWRITE_TAC[GSYM real_div] THEN
1575 REWRITE_TAC[FLOAT_DIV_FF_hi]);;
1576
1577 let FLOAT_DIV_FT_hi = prove(`e2 + k = r1 /\ min_exp + e + e1 = r2 /\
1578 r2 - r1 = r /\ r1 <= r2 /\ ~(n2 = 0) /\
1579 num_exp n e <= num_exp n1 k DIV num_exp n2 0
1580 ==> float_num F n1 e1 / float_num T n2 e2 <= float_num T n r`,
1581 REWRITE_TAC[FLOAT_NEG_T] THEN
1582 REWRITE_TAC[real_div; REAL_INV_NEG] THEN
1583 REWRITE_TAC[REAL_ARITH `a * --b <= --c <=> c <= a * b`] THEN
1584 REWRITE_TAC[GSYM real_div] THEN
1585 REWRITE_TAC[FLOAT_DIV_FF_lo]);;
1586
1587
1588 let FLOAT_DIV_TF_lo = prove(`e2 + k = r1 /\ min_exp + e + e1 = r2 /\
1589 r2 - r1 = r /\ r1 <= r2 /\ ~(n2 = 0) /\
1590 num_exp n1 k DIV num_exp n2 0 < num_exp n e
1591 ==> float_num T n r <= float_num T n1 e1 / float_num F n2 e2`,
1592 REWRITE_TAC[FLOAT_NEG_T] THEN
1593 REWRITE_TAC[real_div; REAL_INV_NEG] THEN
1594 REWRITE_TAC[REAL_ARITH `--a <= --b * c <=> b * c <= a`] THEN
1595 REWRITE_TAC[GSYM real_div] THEN
1596 REWRITE_TAC[FLOAT_DIV_FF_hi]);;
1597
1598 let FLOAT_DIV_TF_hi = prove(`e2 + k = r1 /\ min_exp + e + e1 = r2 /\
1599 r2 - r1 = r /\ r1 <= r2 /\ ~(n2 = 0) /\
1600 num_exp n e <= num_exp n1 k DIV num_exp n2 0
1601 ==> float_num T n1 e1 / float_num F n2 e2 <= float_num T n r`,
1602 REWRITE_TAC[FLOAT_NEG_T] THEN
1603 REWRITE_TAC[real_div; REAL_INV_NEG] THEN
1604 REWRITE_TAC[REAL_ARITH `--a * b <= --c <=> c <= a * b`] THEN
1605 REWRITE_TAC[GSYM real_div] THEN
1606 REWRITE_TAC[FLOAT_DIV_FF_lo]);;
1607
1608
1609 (******************************************)
1610 (* float_div_lo, float_div_hi *)
1611
1612 let transform = UNDISCH_ALL o PURE_REWRITE_RULE[TAUT `~P <=> (P <=> F)`] o
1613 NUMERALS_TO_NUM o PURE_REWRITE_RULE[GSYM IMP_IMP; min_exp_def];;
1614
1615 let FLOAT_DIV_FF_hi' = transform FLOAT_DIV_FF_hi and
1616 FLOAT_DIV_FF_lo' = transform FLOAT_DIV_FF_lo and
1617 FLOAT_DIV_TT_hi' = transform FLOAT_DIV_TT_hi and
1618 FLOAT_DIV_TT_lo' = transform FLOAT_DIV_TT_lo and
1619 FLOAT_DIV_FT_hi' = transform FLOAT_DIV_FT_hi and
1620 FLOAT_DIV_FT_lo' = transform FLOAT_DIV_FT_lo and
1621 FLOAT_DIV_TF_hi' = transform FLOAT_DIV_TF_hi and
1622 FLOAT_DIV_TF_lo' = transform FLOAT_DIV_TF_lo and
1623 FLOAT_DIV_0x_hi' = transform FLOAT_DIV_0x_hi and
1624 FLOAT_DIV_0x_lo' = transform FLOAT_DIV_0x_lo;;
1625
1626 let float_div_lo pp f1 f2 =
1627 let s1, n1, e1 = dest_float f1 and
1628 s2, n2, e2 = dest_float f2 in
1629 let n1_eq0_th = raw_eq0_hash_conv n1 in
1630 if (rand o concl) n1_eq0_th = t_const then
1631 (MY_PROVE_HYP n1_eq0_th o
1632 INST[e1, e1_var_num; f2, f2_var_real; n1, n1_var_num;
1633 (if s1 = "T" then t_const else f_const), s1_var_bool]) FLOAT_DIV_0x_lo'
1634 else
1635 let flag = s1 = s2 in
1636
1637 let k_tm = rand (mk_small_numeral_array (2 * pp)) in
1638 let num_exp1 = mk_num_exp n1 k_tm and
1639 num_exp2 = mk_num_exp n2 zero_const in
1640 let div_th, n_tm, e_tm =
1641 if flag then
1642 let th = num_exp_op_lo pp num_exp_div num_exp1 num_exp2 in
1643 let n_tm, e_tm = dest_num_exp (lhand(concl th)) in
1644 th, n_tm, e_tm
1645 else
1646 let th = num_exp_op_hi_lt pp num_exp_div num_exp1 num_exp2 in
1647 let n_tm, e_tm = dest_num_exp (rand(concl th)) in
1648 th, n_tm, e_tm in
1649
1650 let r1_th = raw_add_conv_hash (mk_binop add_op_num e2 k_tm) in
1651 let r1_tm = rand(concl r1_th) in
1652 let e_plus_e1 = raw_add_conv_hash (mk_binop add_op_num e_tm e1) in
1653 let ltm, rtm = dest_comb(concl e_plus_e1) in
1654 let r2_th' = raw_add_conv_hash (mk_binop add_op_num min_exp_num_const rtm) in
1655 let r2_th = TRANS (AP_TERM (mk_comb (add_op_num, min_exp_num_const)) e_plus_e1) r2_th' in
1656 let r2_tm = rand(concl r2_th) in
1657 let sub_th, le_th = raw_sub_and_le_hash_conv r2_tm r1_tm in
1658 if rand(concl le_th) <> r2_tm then
1659 failwith "float_div_lo: underflow"
1660 else
1661 let r_tm = rand(concl sub_th) in
1662 let n2_not_zero = raw_eq0_hash_conv n2 in
1663 let inst = INST[r1_tm, r1_var_num; r2_tm, r2_var_num;
1664 n1, n1_var_num; e1, e1_var_num;
1665 e_tm, e_var_num; k_tm, k_var_num;
1666 n2, n2_var_num; e2, e2_var_num;
1667 n_tm, n_var_num; r_tm, r_var_num] in
1668 let th0 = inst
1669 (if flag then
1670 if s1 = "F" then FLOAT_DIV_FF_lo' else FLOAT_DIV_TT_lo'
1671 else
1672 if s1 = "F" then FLOAT_DIV_FT_lo' else FLOAT_DIV_TF_lo') in
1673 let th1 = MY_PROVE_HYP n2_not_zero (MY_PROVE_HYP div_th (MY_PROVE_HYP le_th th0)) in
1674 MY_PROVE_HYP sub_th (MY_PROVE_HYP r2_th (MY_PROVE_HYP r1_th th1));;
1675
1676
1677 let float_div_hi pp f1 f2 =
1678 let s1, n1, e1 = dest_float f1 and
1679 s2, n2, e2 = dest_float f2 in
1680 let n1_eq0_th = raw_eq0_hash_conv n1 in
1681 if (rand o concl) n1_eq0_th = t_const then
1682 (MY_PROVE_HYP n1_eq0_th o
1683 INST[e1, e1_var_num; f2, f2_var_real; n1, n1_var_num;
1684 (if s1 = "T" then t_const else f_const), s1_var_bool]) FLOAT_DIV_0x_hi'
1685 else
1686 let flag = s1 = s2 in
1687
1688 let k_tm = rand (mk_small_numeral_array (2 * pp)) in
1689 let num_exp1 = mk_num_exp n1 k_tm and
1690 num_exp2 = mk_num_exp n2 zero_const in
1691 let div_th, n_tm, e_tm =
1692 if flag then
1693 let th = num_exp_op_hi_lt pp num_exp_div num_exp1 num_exp2 in
1694 let n_tm, e_tm = dest_num_exp (rand(concl th)) in
1695 th, n_tm, e_tm
1696 else
1697 let th = num_exp_op_lo pp num_exp_div num_exp1 num_exp2 in
1698 let n_tm, e_tm = dest_num_exp (lhand(concl th)) in
1699 th, n_tm, e_tm in
1700
1701 let r1_th = raw_add_conv_hash (mk_binop add_op_num e2 k_tm) in
1702 let r1_tm = rand(concl r1_th) in
1703 let e_plus_e1 = raw_add_conv_hash (mk_binop add_op_num e_tm e1) in
1704 let ltm, rtm = dest_comb(concl e_plus_e1) in
1705 let r2_th' = raw_add_conv_hash (mk_binop add_op_num min_exp_num_const rtm) in
1706 let r2_th = TRANS (AP_TERM (mk_comb (add_op_num, min_exp_num_const)) e_plus_e1) r2_th' in
1707 let r2_tm = rand(concl r2_th) in
1708 let sub_th, le_th = raw_sub_and_le_hash_conv r2_tm r1_tm in
1709 if rand(concl le_th) <> r2_tm then
1710 failwith "float_div_hi: underflow"
1711 else
1712 let r_tm = rand(concl sub_th) in
1713 let n2_not_zero = raw_eq0_hash_conv n2 in
1714 let inst = INST[r1_tm, r1_var_num; r2_tm, r2_var_num;
1715 n1, n1_var_num; e1, e1_var_num;
1716 e_tm, e_var_num; k_tm, k_var_num;
1717 n2, n2_var_num; e2, e2_var_num;
1718 n_tm, n_var_num; r_tm, r_var_num] in
1719 let th0 = inst
1720 (if flag then
1721 if s1 = "F" then FLOAT_DIV_FF_hi' else FLOAT_DIV_TT_hi'
1722 else
1723 if s1 = "F" then FLOAT_DIV_FT_hi' else FLOAT_DIV_TF_hi') in
1724 let th1 = MY_PROVE_HYP n2_not_zero (MY_PROVE_HYP div_th (MY_PROVE_HYP le_th th0)) in
1725 MY_PROVE_HYP sub_th (MY_PROVE_HYP r2_th (MY_PROVE_HYP r1_th th1));;
1726
1727
1728 (***********************************)
1729 (* FLOAT_ADD *)
1730
1731 let FLOAT_ADD_FF = prove(`num_exp n1 e1 + num_exp n2 e2 = num_exp n e
1732 ==> float_num F n1 e1 + float_num F n2 e2 = float_num F n e`,
1733 REPEAT STRIP_TAC THEN
1734 REWRITE_TAC[float; REAL_MUL_LID] THEN
1735 REWRITE_TAC[REAL_ARITH `a / b + c / b = (a + c) / b`] THEN
1736 ASM_REWRITE_TAC[REAL_OF_NUM_ADD]);;
1737
1738 let FLOAT_ADD_TT = prove(`num_exp n1 e1 + num_exp n2 e2 = num_exp n e
1739 ==> float_num T n1 e1 + float_num T n2 e2 = float_num T n e`,
1740 REWRITE_TAC[FLOAT_NEG_T; REAL_ARITH `--a + --b = --c <=> a + b = c`] THEN
1741 REWRITE_TAC[FLOAT_ADD_FF]);;
1742
1743 let FLOAT_ADD_FF_lo = prove(`num_exp n e <= num_exp n1 e1 + num_exp n2 e2
1744 ==> float_num F n e <= float_num F n1 e1 + float_num F n2 e2`,
1745 REWRITE_TAC[GSYM REAL_OF_NUM_LE; GSYM REAL_OF_NUM_ADD] THEN
1746 REPEAT STRIP_TAC THEN
1747 MAP_EVERY ABBREV_TAC [`z = &(num_exp n e)`; `x = &(num_exp n1 e1)`; `y = &(num_exp n2 e2)`] THEN
1748 ASM_REWRITE_TAC[float; REAL_MUL_LID] THEN
1749 REWRITE_TAC[REAL_ARITH `a / b + c / b = (a + c) / b`] THEN
1750 REWRITE_TAC[real_div] THEN
1751 MATCH_MP_TAC REAL_LE_RMUL THEN
1752 ASM_REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS]);;
1753
1754 let FLOAT_ADD_FF_hi = prove(`num_exp n1 e1 + num_exp n2 e2 <= num_exp n e
1755 ==> float_num F n1 e1 + float_num F n2 e2 <= float_num F n e`,
1756 REWRITE_TAC[GSYM REAL_OF_NUM_LE; GSYM REAL_OF_NUM_ADD] THEN
1757 REPEAT STRIP_TAC THEN
1758 MAP_EVERY ABBREV_TAC [`z = &(num_exp n e)`; `x = &(num_exp n1 e1)`; `y = &(num_exp n2 e2)`] THEN
1759 ASM_REWRITE_TAC[float; REAL_MUL_LID] THEN
1760 REWRITE_TAC[REAL_ARITH `a / b + c / b = (a + c) / b`] THEN
1761 REWRITE_TAC[real_div] THEN
1762 MATCH_MP_TAC REAL_LE_RMUL THEN
1763 ASM_REWRITE_TAC[REAL_LE_INV_EQ; REAL_POS]);;
1764
1765 let FLOAT_ADD_TT_lo = prove(`num_exp n1 e1 + num_exp n2 e2 <= num_exp n e
1766 ==> float_num T n e <= float_num T n1 e1 + float_num T n2 e2`,
1767 REWRITE_TAC[FLOAT_NEG_T; REAL_ARITH `--a <= --b + --c <=> b + c <= a`] THEN
1768 REWRITE_TAC[FLOAT_ADD_FF_hi]);;
1769
1770 let FLOAT_ADD_TT_hi = prove(`num_exp n e <= num_exp n1 e1 + num_exp n2 e2
1771 ==> float_num T n1 e1 + float_num T n2 e2 <= float_num T n e`,
1772 REWRITE_TAC[FLOAT_NEG_T; REAL_ARITH `--b + --c <= --a <=> a <= b + c`] THEN
1773 REWRITE_TAC[FLOAT_ADD_FF_lo]);;
1774
1775 let FLOAT_ADD_FT_F_lo = prove(`num_exp n2 e2 <= num_exp n1 e1 ==>
1776 num_exp n e <= num_exp n1 e1 - num_exp n2 e2
1777 ==> float_num F n e <= float_num F n1 e1 + float_num T n2 e2`,
1778 MAP_EVERY ABBREV_TAC[`z = num_exp n e`; `x = num_exp n1 e1`; `y = num_exp n2 e2`] THEN
1779 ASM_REWRITE_TAC[FLOAT_NEG_T; float; REAL_MUL_LID] THEN
1780 DISCH_TAC THEN
1781 ASM_SIMP_TAC[GSYM REAL_OF_NUM_LE; GSYM REAL_OF_NUM_SUB] THEN
1782 REWRITE_TAC[num_exp; min_exp_def; MULT_CLAUSES; GSYM REAL_OF_NUM_POW] THEN
1783 REAL_ARITH_TAC);;
1784
1785 let FLOAT_ADD_FT_T_lo = prove(`num_exp n1 e1 <= num_exp n2 e2 ==>
1786 num_exp n2 e2 - num_exp n1 e1 <= num_exp n e
1787 ==> float_num T n e <= float_num F n1 e1 + float_num T n2 e2`,
1788 MAP_EVERY ABBREV_TAC[`z = num_exp n e`; `x = num_exp n1 e1`; `y = num_exp n2 e2`] THEN
1789 ASM_REWRITE_TAC[FLOAT_NEG_T; float; REAL_MUL_LID] THEN
1790 DISCH_TAC THEN
1791 ASM_SIMP_TAC[GSYM REAL_OF_NUM_LE; GSYM REAL_OF_NUM_SUB] THEN
1792 REWRITE_TAC[num_exp; min_exp_def; MULT_CLAUSES; GSYM REAL_OF_NUM_POW] THEN
1793 REAL_ARITH_TAC);;
1794
1795 let FLOAT_ADD_FT_F_hi = prove(`num_exp n2 e2 <= num_exp n1 e1 ==>
1796 num_exp n1 e1 - num_exp n2 e2 <= num_exp n e
1797 ==> float_num F n1 e1 + float_num T n2 e2 <= float_num F n e`,
1798 REWRITE_TAC[FLOAT_NEG_T; REAL_ARITH `a + --b <= c <=> --c <= b + --a`] THEN
1799 REWRITE_TAC[GSYM FLOAT_NEG_T; FLOAT_ADD_FT_T_lo]);;
1800
1801 let FLOAT_ADD_FT_T_hi = prove(`num_exp n1 e1 <= num_exp n2 e2 ==>
1802 num_exp n e <= num_exp n2 e2 - num_exp n1 e1
1803 ==> float_num F n1 e1 + float_num T n2 e2 <= float_num T n e`,
1804 REWRITE_TAC[FLOAT_NEG_T; REAL_ARITH `a + --b <= --c <=> c <= b + --a`] THEN
1805 REWRITE_TAC[GSYM FLOAT_NEG_T; FLOAT_ADD_FT_F_lo]);;
1806
1807
1808 (******************************************)
1809 (* float_add_lo, float_add_hi *)
1810
1811 let REAL_ADD_COMM = CONJUNCT1 REAL_ADD_AC;;
1812
1813 let transform = UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o NUMERALS_TO_NUM;;
1814 let FLOAT_ADD_FF_hi' = transform FLOAT_ADD_FF_hi and
1815 FLOAT_ADD_FF_lo' = transform FLOAT_ADD_FF_lo and
1816 FLOAT_ADD_TT_hi' = transform FLOAT_ADD_TT_hi and
1817 FLOAT_ADD_TT_lo' = transform FLOAT_ADD_TT_lo and
1818 FLOAT_ADD_FT_F_lo' = transform FLOAT_ADD_FT_F_lo and
1819 FLOAT_ADD_FT_T_lo' = transform FLOAT_ADD_FT_T_lo and
1820 FLOAT_ADD_FT_F_hi' = transform FLOAT_ADD_FT_F_hi and
1821 FLOAT_ADD_FT_T_hi' = transform FLOAT_ADD_FT_T_hi;;
1822
1823 let float_add_lo pp f1 f2 =
1824 let s1, n1, e1 = dest_float f1 in
1825 let s2, n2, e2 = dest_float f2 in
1826 if s1 = s2 then
1827 let num_exp1 = mk_num_exp n1 e1 in
1828 let num_exp2 = mk_num_exp n2 e2 in
1829
1830 if s1 = "F" then
1831 (* F + F *)
1832 let add_th = num_exp_op_lo pp num_exp_add num_exp1 num_exp2 in
1833 let n_tm, e_tm = dest_num_exp (lhand(concl add_th)) in
1834 let th0 = INST[e_tm, e_var_num; n_tm, n_var_num; n1, n1_var_num;
1835 e1, e1_var_num; n2, n2_var_num; e2, e2_var_num] FLOAT_ADD_FF_lo' in
1836 MY_PROVE_HYP add_th th0
1837 else
1838 (* T + T *)
1839 let add_th = num_exp_op_hi pp num_exp_add num_exp1 num_exp2 in
1840 let n_tm, e_tm = dest_num_exp (rand(concl add_th)) in
1841 let th0 = INST[e_tm, e_var_num; n_tm, n_var_num; n1, n1_var_num;
1842 e1, e1_var_num; n2, n2_var_num; e2, e2_var_num] FLOAT_ADD_TT_lo' in
1843 MY_PROVE_HYP add_th th0
1844 else
1845 (* F + T or T + F *)
1846 let th0, n1, e1, n2, e2 =
1847 if s1 = "T" then
1848 INST[f2, m_var_real; f1, n_var_real] REAL_ADD_COMM, n2, e2, n1, e1
1849 else
1850 REFL(mk_binop add_op_real f1 f2), n1, e1, n2, e2 in
1851
1852 let num_exp1 = mk_num_exp n1 e1 in
1853 let num_exp2 = mk_num_exp n2 e2 in
1854
1855 let sub_th, le_th = num_exp_sub num_exp1 num_exp2 in
1856 let sub_tm = rand(concl sub_th) in
1857
1858 if rand(concl le_th) = num_exp1 then
1859 let lo_th = num_exp_lo pp sub_tm in
1860 let n_tm, e_tm = dest_num_exp (lhand(concl lo_th)) in
1861 let lo_sub_th = EQ_MP (AP_TERM (rator(concl lo_th)) (SYM sub_th)) lo_th in
1862
1863 let th1 = INST[n1, n1_var_num; e1, e1_var_num; n2, n2_var_num; e2, e2_var_num;
1864 n_tm, n_var_num; e_tm, e_var_num] FLOAT_ADD_FT_F_lo' in
1865 let th2 = MY_PROVE_HYP lo_sub_th (MY_PROVE_HYP le_th th1) in
1866 EQ_MP (AP_TERM (rator(concl th2)) th0) th2
1867
1868 else
1869 let hi_th = num_exp_hi pp sub_tm in
1870 let n_tm, e_tm = dest_num_exp(rand(concl hi_th)) in
1871 let hi_sub_th = EQ_MP (SYM (AP_THM (AP_TERM le_op_num sub_th) (rand(concl hi_th)))) hi_th in
1872
1873 let th1 = INST[n1, n1_var_num; e1, e1_var_num; n2, n2_var_num; e2, e2_var_num;
1874 n_tm, n_var_num; e_tm, e_var_num] FLOAT_ADD_FT_T_lo' in
1875 let th2 = MY_PROVE_HYP hi_sub_th (MY_PROVE_HYP le_th th1) in
1876 EQ_MP (AP_TERM (rator(concl th2)) th0) th2;;
1877
1878
1879 let float_add_hi pp f1 f2 =
1880 let s1, n1, e1 = dest_float f1 in
1881 let s2, n2, e2 = dest_float f2 in
1882 if s1 = s2 then
1883 let num_exp1 = mk_num_exp n1 e1 in
1884 let num_exp2 = mk_num_exp n2 e2 in
1885
1886 if s1 = "F" then
1887 (* F + F *)
1888 let add_th = num_exp_op_hi pp num_exp_add num_exp1 num_exp2 in
1889 let n_tm, e_tm = dest_num_exp (rand(concl add_th)) in
1890 let th0 = INST[e_tm, e_var_num; n_tm, n_var_num; n1, n1_var_num;
1891 e1, e1_var_num; n2, n2_var_num; e2, e2_var_num] FLOAT_ADD_FF_hi' in
1892 MY_PROVE_HYP add_th th0
1893 else
1894 (* T + T *)
1895 let add_th = num_exp_op_lo pp num_exp_add num_exp1 num_exp2 in
1896 let n_tm, e_tm = dest_num_exp (lhand(concl add_th)) in
1897 let th0 = INST[e_tm, e_var_num; n_tm, n_var_num; n1, n1_var_num;
1898 e1, e1_var_num; n2, n2_var_num; e2, e2_var_num] FLOAT_ADD_TT_hi' in
1899 MY_PROVE_HYP add_th th0
1900 else
1901 (* F + T or T + F *)
1902 let th0, n1, e1, n2, e2 =
1903 if s1 = "T" then
1904 INST[f2, m_var_real; f1, n_var_real] REAL_ADD_COMM, n2, e2, n1, e1
1905 else
1906 REFL(mk_binop add_op_real f1 f2), n1, e1, n2, e2 in
1907
1908 let num_exp1 = mk_num_exp n1 e1 in
1909 let num_exp2 = mk_num_exp n2 e2 in
1910
1911 let sub_th, le_th = num_exp_sub num_exp1 num_exp2 in
1912 let sub_tm = rand(concl sub_th) in
1913
1914 if rand(concl le_th) = num_exp1 then
1915 let hi_th = num_exp_hi pp sub_tm in
1916 let n_tm, e_tm = dest_num_exp (rand(concl hi_th)) in
1917 let hi_sub_th = EQ_MP (SYM (AP_THM (AP_TERM le_op_num sub_th) (rand(concl hi_th)))) hi_th in
1918
1919 let th1 = INST[n1, n1_var_num; e1, e1_var_num; n2, n2_var_num; e2, e2_var_num;
1920 n_tm, n_var_num; e_tm, e_var_num] FLOAT_ADD_FT_F_hi' in
1921 let th2 = MY_PROVE_HYP hi_sub_th (MY_PROVE_HYP le_th th1) in
1922 EQ_MP (AP_THM (AP_TERM le_op_real th0) (rand(concl th2))) th2
1923
1924 else
1925 let lo_th = num_exp_lo pp sub_tm in
1926 let n_tm, e_tm = dest_num_exp(lhand(concl lo_th)) in
1927 let lo_sub_th = EQ_MP (AP_TERM (rator(concl lo_th)) (SYM sub_th)) lo_th in
1928
1929 let th1 = INST[n1, n1_var_num; e1, e1_var_num; n2, n2_var_num; e2, e2_var_num;
1930 n_tm, n_var_num; e_tm, e_var_num] FLOAT_ADD_FT_T_hi' in
1931 let th2 = MY_PROVE_HYP lo_sub_th (MY_PROVE_HYP le_th th1) in
1932 EQ_MP (AP_THM (AP_TERM le_op_real th0) (rand(concl th2))) th2;;
1933
1934
1935 (******************************************)
1936 (* float_sub_lo, float_sub_hi *)
1937
1938 let FLOAT_SUB_F_EQ_ADD = (SYM o prove)(`f1 - float_num F n2 e2 = f1 + float_num T n2 e2`,
1939 REWRITE_TAC[FLOAT_NEG_T] THEN REAL_ARITH_TAC);;
1940
1941 let FLOAT_SUB_T_EQ_ADD = (SYM o prove)(`f1 - float_num T n2 e2 = f1 + float_num F n2 e2`,
1942 REWRITE_TAC[FLOAT_NEG_T] THEN REAL_ARITH_TAC);;
1943
1944 let float_sub_lo pp f1 f2 =
1945 let s2, n2, e2 = dest_float f2 in
1946 let th0 =
1947 INST[f1, f1_var_real; n2, n2_var_num; e2, e2_var_num]
1948 (if s2 = "F" then FLOAT_SUB_F_EQ_ADD else FLOAT_SUB_T_EQ_ADD) in
1949 let ltm,f2_tm = dest_comb(lhand(concl th0)) in
1950 let f1_tm = rand ltm in
1951 let lo_th = float_add_lo pp f1_tm f2_tm in
1952 EQ_MP (AP_TERM (rator(concl lo_th)) th0) lo_th;;
1953
1954
1955 let float_sub_hi pp f1 f2 =
1956 let s2, n2, e2 = dest_float f2 in
1957 let th0 =
1958 INST[f1, f1_var_real; n2, n2_var_num; e2, e2_var_num]
1959 (if s2 = "F" then FLOAT_SUB_F_EQ_ADD else FLOAT_SUB_T_EQ_ADD) in
1960 let ltm, f2_tm = dest_comb(lhand(concl th0)) in
1961 let f1_tm = rand ltm in
1962 let hi_th = float_add_hi pp f1_tm f2_tm in
1963 EQ_MP (AP_THM (AP_TERM le_op_real th0) (rand(concl hi_th))) hi_th;;
1964
1965
1966 (*******************************************)
1967 (* FLOAT_SQRT *)
1968
1969 (* float_num F m e = float_num F (B0 m) (PRE e) *)
1970 let FLOAT_PRE_EXP = prove(mk_imp(`~(e = 0) /\ PRE e = e1`,
1971 mk_eq(`float_num F m e`,
1972 mk_comb(mk_comb(`float_num F`, mk_comb(b0_const, m_var_num)), `e1:num`))),
1973 STRIP_TAC THEN POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN
1974 REWRITE_TAC[float; REAL_MUL_LID; real_div; REAL_EQ_MUL_RCANCEL] THEN
1975 DISJ1_TAC THEN
1976 REWRITE_TAC[num_exp; b0_thm; REAL_OF_NUM_EQ] THEN
1977 SUBGOAL_THEN `e = SUC (PRE e)` MP_TAC THENL
1978 [
1979 POP_ASSUM MP_TAC THEN ARITH_TAC;
1980 ALL_TAC
1981 ] THEN
1982 DISCH_THEN (fun th -> CONV_TAC (LAND_CONV (ONCE_REWRITE_CONV[th]))) THEN
1983 REWRITE_TAC[EXP] THEN
1984 ARITH_TAC);;
1985
1986 let DIV2_EVEN_lemma = prove(`!n. EVEN n ==> 2 * (n DIV 2) = n`,
1987 GEN_TAC THEN
1988 REWRITE_TAC[EVEN_EXISTS] THEN
1989 STRIP_TAC THEN
1990 ASM_REWRITE_TAC[] THEN
1991 MATCH_MP_TAC (ARITH_RULE `x = y ==> 2 * x = 2 * y`) THEN
1992 MATCH_MP_TAC DIV_MULT THEN
1993 ARITH_TAC);;
1994
1995 let FLOAT_SQRT_EVEN_lo = prove(`f1 * f1 = f2 /\ f2 <= x /\
1996 num_exp m (2 * p) = x /\ f1 = num_exp n1 e1
1997 /\ EVEN e /\ e DIV 2 = e2 /\
1998 e1 + e2 + (min_exp DIV 2) = r /\
1999 p <= r /\ r - p = r2
2000 ==> float_num F n1 r2 <= sqrt (float_num F m e)`,
2001 STRIP_TAC THEN
2002 UNDISCH_TAC `f2 <= x:num` THEN
2003 UNDISCH_TAC `num_exp m (2 * p) = x` THEN
2004 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2005 UNDISCH_TAC `f1 * f1 = f2:num` THEN
2006 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2007 UNDISCH_TAC `e1 + e2 + min_exp DIV 2 = r` THEN
2008 UNDISCH_TAC `e DIV 2 = e2` THEN
2009 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2010 REPEAT (POP_ASSUM MP_TAC) THEN
2011 REWRITE_TAC[num_exp; float; REAL_MUL_LID; GSYM REAL_OF_NUM_MUL] THEN
2012 REPEAT STRIP_TAC THEN
2013 UNDISCH_TAC `r - p = r2:num` THEN
2014 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2015
2016 MATCH_MP_TAC REAL_LE_RSQRT THEN
2017 REWRITE_TAC[GSYM REAL_OF_NUM_POW; REAL_POW_DIV] THEN
2018 REWRITE_TAC[REAL_POW_2; real_div; REAL_INV_MUL] THEN
2019 REWRITE_TAC[REAL_MUL_ASSOC] THEN
2020 MATCH_MP_TAC REAL_LE_RMUL THEN
2021 CONJ_TAC THENL
2022 [
2023 REWRITE_TAC[REAL_ARITH `(((a * b) * a) * b) * c = (a * a) * (b * b) * c:real`] THEN
2024 REWRITE_TAC[GSYM REAL_POW_ADD] THEN
2025 REWRITE_TAC[ARITH_RULE `r - p + r - p = 2 * r - 2 * p`] THEN
2026 MP_TAC (SPECL[mk_comb(amp_op_real, base_const); `2 * r`; `2 * p`] REAL_DIV_POW2) THEN
2027 ANTS_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN
2028 ASM_SIMP_TAC[ARITH_RULE `p <= r ==> 2 * p <= 2 * r`] THEN
2029 DISCH_THEN (fun th -> REWRITE_TAC[SYM th; real_div]) THEN
2030
2031 SUBGOAL_THEN `2 * r = (e1 + e1) + min_exp + e` (fun th -> REWRITE_TAC[th]) THENL
2032 [
2033 EXPAND_TAC "r" THEN
2034 REWRITE_TAC[ARITH_RULE `2 * (e1 + b + c) = (e1 + e1) + 2 * c + 2 * b`] THEN
2035 MATCH_MP_TAC (ARITH_RULE `b1 = b2 /\ c1 = c2 ==> a + b1 + c1 = a + b2 + c2:num`) THEN
2036 SUBGOAL_THEN `EVEN min_exp` ASSUME_TAC THENL
2037 [
2038 REWRITE_TAC[min_exp_def] THEN ARITH_TAC;
2039 ALL_TAC
2040 ] THEN
2041 ASM_SIMP_TAC[DIV2_EVEN_lemma];
2042 ALL_TAC
2043 ] THEN
2044
2045 REWRITE_TAC[REAL_POW_ADD] THEN
2046 REWRITE_TAC[REAL_ARITH `(n * n) * (((e * e) * x * y) * z) * u = (n * e) * (n * e) * (x * u) * z * y:real`] THEN
2047 SUBGOAL_THEN `~(&(num_exp 1 min_exp) = &0)` MP_TAC THENL
2048 [
2049 REWRITE_TAC[REAL_OF_NUM_EQ; NUM_EXP_EQ_0] THEN ARITH_TAC;
2050 ALL_TAC
2051 ] THEN
2052 REWRITE_TAC[num_exp; REAL_MUL_LID; GSYM REAL_OF_NUM_POW; GSYM REAL_OF_NUM_MUL] THEN
2053 DISCH_THEN (fun th -> SIMP_TAC[th; REAL_MUL_RINV; REAL_MUL_LID]) THEN
2054 FIRST_X_ASSUM (MP_TAC o check(fun th -> (fst o dest_var o lhand o concl) th = "f1")) THEN
2055 REWRITE_TAC[GSYM REAL_OF_NUM_EQ; GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_POW] THEN
2056 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2057
2058 REWRITE_TAC[REAL_MUL_ASSOC] THEN
2059 MATCH_MP_TAC REAL_LE_RMUL THEN
2060 CONJ_TAC THENL
2061 [
2062 SUBGOAL_THEN `!x y z. &0 < x /\ y <= z * x ==> y * inv x <= z` MP_TAC THENL
2063 [
2064 REPEAT STRIP_TAC THEN
2065 MP_TAC (SPECL [`y * inv x`; `z:real`; `x:real`] REAL_LE_RMUL_EQ) THEN
2066 ASM_REWRITE_TAC[] THEN
2067 DISCH_THEN (fun th -> REWRITE_TAC[SYM th; GSYM REAL_MUL_ASSOC]) THEN
2068 ASM_SIMP_TAC[REAL_ARITH `&0 < x ==> ~(x = &0)`; REAL_MUL_LINV; REAL_MUL_RID];
2069 ALL_TAC
2070 ] THEN
2071
2072 DISCH_THEN (MP_TAC o SPECL[`&(num_exp 1 (2 * p))`; `&(f1 * f1)`; `&m`]) THEN
2073 REWRITE_TAC[num_exp; GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_POW; REAL_MUL_LID] THEN
2074 DISCH_THEN MATCH_MP_TAC THEN
2075 ASM_REWRITE_TAC[REAL_OF_NUM_MUL; REAL_OF_NUM_POW; REAL_OF_NUM_LE] THEN
2076 REWRITE_TAC[REAL_OF_NUM_LT; EXP_LT_0] THEN
2077 ARITH_TAC;
2078 ALL_TAC
2079 ] THEN
2080
2081 MATCH_MP_TAC REAL_POW_LE THEN
2082 ARITH_TAC;
2083 ALL_TAC
2084 ] THEN
2085
2086 MATCH_MP_TAC REAL_LE_INV THEN
2087 MATCH_MP_TAC REAL_POW_LE THEN
2088 ARITH_TAC);;
2089
2090
2091 let FLOAT_SQRT_EVEN_hi = prove(`f1 * f1 = f2 /\ x <= f2 /\
2092 num_exp m (2 * p) = x /\ f1 = num_exp n1 e1
2093 /\ EVEN e /\ e DIV 2 = e2 /\
2094 e1 + e2 + (min_exp DIV 2) = r /\
2095 p <= r /\ r - p = r2
2096 ==> sqrt (float_num F m e) <= float_num F n1 r2`,
2097 STRIP_TAC THEN
2098 UNDISCH_TAC `x <= f2:num` THEN
2099 UNDISCH_TAC `num_exp m (2 * p) = x` THEN
2100 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2101 UNDISCH_TAC `f1 * f1 = f2:num` THEN
2102 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2103 UNDISCH_TAC `e1 + e2 + min_exp DIV 2 = r` THEN
2104 UNDISCH_TAC `e DIV 2 = e2` THEN
2105 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2106 REPEAT (POP_ASSUM MP_TAC) THEN
2107 REWRITE_TAC[num_exp; float; REAL_MUL_LID; GSYM REAL_OF_NUM_MUL] THEN
2108 REPEAT STRIP_TAC THEN
2109 UNDISCH_TAC `r - p = r2:num` THEN
2110 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2111
2112 MATCH_MP_TAC REAL_LE_LSQRT THEN
2113 REPEAT CONJ_TAC THENL
2114 [
2115 REWRITE_TAC[REAL_OF_NUM_MUL; real_div] THEN
2116 MATCH_MP_TAC REAL_LE_MUL THEN
2117 REWRITE_TAC[REAL_POS] THEN
2118 MATCH_MP_TAC REAL_LE_INV THEN
2119 REWRITE_TAC[REAL_POS];
2120 ALL_TAC
2121 ] THEN
2122
2123 REWRITE_TAC[GSYM REAL_OF_NUM_POW; REAL_POW_DIV] THEN
2124 REWRITE_TAC[REAL_POW_2; real_div; REAL_INV_MUL] THEN
2125 REWRITE_TAC[REAL_MUL_ASSOC] THEN
2126 MATCH_MP_TAC REAL_LE_RMUL THEN
2127 CONJ_TAC THENL
2128 [
2129 REWRITE_TAC[REAL_ARITH `(((a * b) * a) * b) * c = (a * a) * (b * b) * c:real`] THEN
2130 REWRITE_TAC[GSYM REAL_POW_ADD] THEN
2131 REWRITE_TAC[ARITH_RULE `r - p + r - p = 2 * r - 2 * p`] THEN
2132 MP_TAC (SPECL[mk_comb(amp_op_real, base_const); `2 * r`; `2 * p`] REAL_DIV_POW2) THEN
2133 ANTS_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN
2134 ASM_SIMP_TAC[ARITH_RULE `p <= r ==> 2 * p <= 2 * r`] THEN
2135 DISCH_THEN (fun th -> REWRITE_TAC[SYM th; real_div]) THEN
2136
2137 SUBGOAL_THEN `2 * r = (e1 + e1) + min_exp + e` (fun th -> REWRITE_TAC[th]) THENL
2138 [
2139 EXPAND_TAC "r" THEN
2140 REWRITE_TAC[ARITH_RULE `2 * (e1 + b + c) = (e1 + e1) + 2 * c + 2 * b`] THEN
2141 MATCH_MP_TAC (ARITH_RULE `b1 = b2 /\ c1 = c2 ==> a + b1 + c1 = a + b2 + c2:num`) THEN
2142 SUBGOAL_THEN `EVEN min_exp` ASSUME_TAC THENL
2143 [
2144 REWRITE_TAC[min_exp_def] THEN ARITH_TAC;
2145 ALL_TAC
2146 ] THEN
2147 ASM_SIMP_TAC[DIV2_EVEN_lemma];
2148 ALL_TAC
2149 ] THEN
2150
2151 REWRITE_TAC[REAL_POW_ADD] THEN
2152 REWRITE_TAC[REAL_ARITH `(n * n) * (((e * e) * x * y) * z) * u = (n * e) * (n * e) * (x * u) * z * y:real`] THEN
2153 SUBGOAL_THEN `~(&(num_exp 1 min_exp) = &0)` MP_TAC THENL
2154 [
2155 REWRITE_TAC[REAL_OF_NUM_EQ; NUM_EXP_EQ_0] THEN ARITH_TAC;
2156 ALL_TAC
2157 ] THEN
2158 REWRITE_TAC[num_exp; REAL_MUL_LID; GSYM REAL_OF_NUM_POW; GSYM REAL_OF_NUM_MUL] THEN
2159 DISCH_THEN (fun th -> SIMP_TAC[th; REAL_MUL_RINV; REAL_MUL_LID]) THEN
2160 FIRST_X_ASSUM (MP_TAC o check(fun th -> (fst o dest_var o lhand o concl) th = "f1")) THEN
2161 REWRITE_TAC[GSYM REAL_OF_NUM_EQ; GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_POW] THEN
2162 DISCH_THEN (fun th -> REWRITE_TAC[SYM th]) THEN
2163
2164 REWRITE_TAC[REAL_MUL_ASSOC] THEN
2165 MATCH_MP_TAC REAL_LE_RMUL THEN
2166 CONJ_TAC THENL
2167 [
2168 SUBGOAL_THEN `!x y z. &0 < x /\ z * x <= y ==> z <= y * inv x` MP_TAC THENL
2169 [
2170 REPEAT STRIP_TAC THEN
2171 MP_TAC (SPECL [`z:real`; `y * inv x`; `x:real`] REAL_LE_RMUL_EQ) THEN
2172 ASM_REWRITE_TAC[] THEN
2173 DISCH_THEN (fun th -> REWRITE_TAC[SYM th; GSYM REAL_MUL_ASSOC]) THEN
2174 ASM_SIMP_TAC[REAL_ARITH `&0 < x ==> ~(x = &0)`; REAL_MUL_LINV; REAL_MUL_RID];
2175 ALL_TAC
2176 ] THEN
2177
2178 DISCH_THEN (MP_TAC o SPECL[`&(num_exp 1 (2 * p))`; `&(f1 * f1)`; `&m`]) THEN
2179 REWRITE_TAC[num_exp; GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_POW; REAL_MUL_LID] THEN
2180 DISCH_THEN MATCH_MP_TAC THEN
2181 ASM_REWRITE_TAC[REAL_OF_NUM_MUL; REAL_OF_NUM_POW; REAL_OF_NUM_LE] THEN
2182 REWRITE_TAC[REAL_OF_NUM_LT; EXP_LT_0] THEN
2183 ARITH_TAC;
2184 ALL_TAC
2185 ] THEN
2186
2187 MATCH_MP_TAC REAL_POW_LE THEN
2188 ARITH_TAC;
2189 ALL_TAC
2190 ] THEN
2191
2192 MATCH_MP_TAC REAL_LE_INV THEN
2193 MATCH_MP_TAC REAL_POW_LE THEN
2194 ARITH_TAC);;
2195
2196
2197 (******************)
2198 let transform = UNDISCH_ALL o
2199 PURE_ONCE_REWRITE_RULE[TAUT `EVEN e <=> (EVEN e <=> T)`] o
2200 NUMERALS_TO_NUM o
2201 CONV_RULE (DEPTH_CONV NUM_DIV_CONV) o
2202 REWRITE_RULE[GSYM IMP_IMP; min_exp_def];;
2203
2204 let FLOAT_SQRT_EVEN_lo' = transform FLOAT_SQRT_EVEN_lo and
2205 FLOAT_SQRT_EVEN_hi' = transform FLOAT_SQRT_EVEN_hi and
2206 FLOAT_PRE_EXP' = (UNDISCH_ALL o
2207 PURE_ONCE_REWRITE_RULE[TAUT `~(e = _0) <=> ((e = _0) <=> F)`] o
2208 REWRITE_RULE[GSYM IMP_IMP; NUMERAL]) FLOAT_PRE_EXP;;
2209
2210 let even_const = `EVEN` and
2211 pre_const = `PRE` and
2212 two_num = rand(mk_small_numeral_array 2) and
2213 min_exp_div2 = rand(mk_small_numeral_array (min_exp / 2)) and
2214 f2_var_num = `f2:num` and
2215 f1_var_num = `f1:num` and
2216 p_var_num = `p:num`;;
2217
2218 open Big_int;;
2219
2220 (* Returns the list of digits of the given Big_int n in the base b *)
2221 let rec get_big_int_digits b n =
2222 let bb = big_int_of_int b in
2223 if le_big_int n zero_big_int then []
2224 else
2225 let q, r = quomod_big_int n bb in
2226 r :: get_big_int_digits b q;;
2227
2228 (* [1;2;3] -> 123 (base = 10) *)
2229 let rec big_int_from_list b list =
2230 let rec proc acc list =
2231 match list with
2232 [] -> acc
2233 | h::t -> proc (add_big_int h (mult_int_big_int b acc)) t in
2234 proc zero_big_int list;;
2235
2236 (* Returns n first elements of the list *)
2237 let rec take n list =
2238 match list with
2239 x :: xs -> if n > 0 then x :: take (n - 1) xs else []
2240 | [] -> [];;
2241
2242 (* Returns an integer number that contains at most pp significant digits
2243 in the given base b *)
2244 let big_int_round_lo base pp n =
2245 let digits = rev (get_big_int_digits base n) in
2246 let n_digits = length digits in
2247 if n_digits <= pp then
2248 n
2249 else
2250 let m = big_int_from_list base (take pp digits) in
2251 mult_big_int (power_int_positive_int base (n_digits - pp)) m;;
2252
2253 let big_int_round_hi base pp n =
2254 let digits = rev (get_big_int_digits base n) in
2255 let n_digits = length digits in
2256 if n_digits <= pp then n
2257 else
2258 let l1, l2 = chop_list pp digits in
2259 if forall (eq_big_int zero_big_int) l2 then n
2260 else
2261 let m = succ_big_int (big_int_from_list base l1) in
2262 mult_big_int (power_int_positive_int base (n_digits - pp)) m;;
2263
2264
2265 (******************)
2266 let rec float_sqrt_lo pp tm =
2267 let s, m_tm, e_tm = dest_float tm in
2268 let p_tm = rand (mk_small_numeral_array pp) in
2269 if s <> "F" then
2270 failwith "float_sqrt_lo: negative argument"
2271 else
2272 let even_th = raw_even_hash_conv (mk_comb (even_const, e_tm)) in
2273 if (fst o dest_const o rand o concl) even_th <> "T" then
2274 (* ODD e *)
2275 let pre_e = raw_pre_hash_conv (mk_comb (pre_const, e_tm)) in
2276 let e_neq_0 = raw_eq0_hash_conv e_tm in
2277 let e1_tm = rand (concl pre_e) in
2278 let th0 = INST[e1_tm, e1_var_num; e_tm, e_var_num; m_tm, m_var_num] FLOAT_PRE_EXP' in
2279 let th1 = MY_PROVE_HYP pre_e (MY_PROVE_HYP e_neq_0 th0) in
2280 let th2 = float_sqrt_lo pp (rand(concl th1)) in
2281 let ltm, rtm = dest_comb (concl th2) in
2282 EQ_MP (SYM (AP_TERM ltm (AP_TERM (rator rtm) th1))) th2
2283 else
2284 (* EVEN e *)
2285 let p2_tm = mk_binop mul_op_num two_num p_tm in
2286 let p2_th = raw_mul_conv_hash p2_tm in
2287 let f1_1 = AP_TERM (mk_comb(num_exp_const, m_tm)) p2_th in
2288 let f1_2 = TRANS f1_1 (denormalize (rand (concl f1_1))) in
2289
2290 let x_tm = rand(concl f1_2) in
2291 let x = raw_dest_hash x_tm in
2292 let f1' = Big_int.sqrt_big_int (big_int_of_num x) in
2293 let f1 = num_of_big_int (big_int_round_lo Arith_num.arith_base pp f1') in
2294 let f1_tm = rand(mk_numeral_array f1) in
2295 let f1_num_exp = to_num_exp f1_tm in
2296
2297 let n1_tm, e1_tm = dest_num_exp (rand (concl f1_num_exp)) in
2298 let f1f1_eq_f2 = raw_mul_conv_hash (mk_binop mul_op_num f1_tm f1_tm) in
2299 let f2_tm = rand(concl f1f1_eq_f2) in
2300 let f2_le_x = EQT_ELIM (raw_le_hash_conv (mk_binop le_op_num f2_tm x_tm)) in
2301
2302 let e_div2_eq_e2 = raw_div_hash_conv (mk_binop div_op_num e_tm two_num) in
2303 let e2_tm = rand(concl e_div2_eq_e2) in
2304 let r_th1 = raw_add_conv_hash (mk_binop add_op_num e2_tm min_exp_div2) in
2305 let r_th2 = AP_TERM (mk_comb(add_op_num, e1_tm)) r_th1 in
2306 let r_th = TRANS r_th2 (raw_add_conv_hash (rand (concl r_th2))) in
2307
2308 let r_tm = rand(concl r_th) in
2309 let r_sub_p, p_le_r = raw_sub_and_le_hash_conv p_tm r_tm in
2310 let r2_tm = rand(concl r_sub_p) in
2311 if (rand(concl p_le_r) <> r_tm) then
2312 failwith "float_sqrt_lo: underflow"
2313 else
2314 let th0 = INST[f2_tm, f2_var_num; x_tm, x_var_num; p_tm, p_var_num; r_tm, r_var_num;
2315 f1_tm, f1_var_num; n1_tm, n1_var_num; e1_tm, e1_var_num; e2_tm, e2_var_num;
2316 e_tm, e_var_num; m_tm, m_var_num; r2_tm, r2_var_num]
2317 FLOAT_SQRT_EVEN_lo' in
2318 MY_PROVE_HYP f1_2 (
2319 MY_PROVE_HYP e_div2_eq_e2 (
2320 MY_PROVE_HYP r_sub_p (
2321 MY_PROVE_HYP r_th (
2322 MY_PROVE_HYP f1f1_eq_f2 (
2323 MY_PROVE_HYP f1_num_exp (
2324 MY_PROVE_HYP even_th (
2325 MY_PROVE_HYP f2_le_x (
2326 MY_PROVE_HYP p_le_r th0
2327 ))))))));;
2328
2329
2330 let rec float_sqrt_hi pp tm =
2331 let s, m_tm, e_tm = dest_float tm in
2332 let p_tm = rand (mk_small_numeral_array pp) in
2333 if s <> "F" then
2334 failwith "float_sqrt_lo: negative argument"
2335 else
2336 let even_th = raw_even_hash_conv (mk_comb (even_const, e_tm)) in
2337 if (fst o dest_const o rand o concl) even_th <> "T" then
2338 (* ODD e *)
2339 let pre_e = raw_pre_hash_conv (mk_comb (pre_const, e_tm)) in
2340 let e_neq_0 = raw_eq0_hash_conv e_tm in
2341 let e1_tm = rand (concl pre_e) in
2342 let th0 = INST[e1_tm, e1_var_num; e_tm, e_var_num; m_tm, m_var_num] FLOAT_PRE_EXP' in
2343 let th1 = MY_PROVE_HYP pre_e (MY_PROVE_HYP e_neq_0 th0) in
2344 let th2 = float_sqrt_hi pp (rand(concl th1)) in
2345 let ltm, rtm = dest_comb (concl th2) in
2346 let ltm2, rtm2 = dest_comb ltm in
2347 let th3 = AP_THM (AP_TERM ltm2 (AP_TERM (rator rtm2) th1)) rtm in
2348 EQ_MP (SYM th3) th2
2349 else
2350 (* EVEN e *)
2351 let p2_tm = mk_binop mul_op_num two_num p_tm in
2352 let p2_th = raw_mul_conv_hash p2_tm in
2353 let f1_1 = AP_TERM (mk_comb(num_exp_const, m_tm)) p2_th in
2354 let f1_2 = TRANS f1_1 (denormalize (rand (concl f1_1))) in
2355
2356 let x_tm = rand(concl f1_2) in
2357 let x = raw_dest_hash x_tm in
2358 let x' = big_int_of_num x in
2359 let f1' = sqrt_big_int x' in
2360 let f1 = (num_of_big_int o big_int_round_hi Arith_num.arith_base pp)
2361 (if eq_big_int (mult_big_int f1' f1') x' then f1' else succ_big_int f1') in
2362
2363 let f1_tm = rand(mk_numeral_array f1) in
2364 let f1_num_exp = to_num_exp f1_tm in
2365
2366 let n1_tm, e1_tm = dest_num_exp (rand (concl f1_num_exp)) in
2367 let f1f1_eq_f2 = raw_mul_conv_hash (mk_binop mul_op_num f1_tm f1_tm) in
2368 let f2_tm = rand(concl f1f1_eq_f2) in
2369 let x_le_f2 = EQT_ELIM (raw_le_hash_conv (mk_binop le_op_num x_tm f2_tm)) in
2370
2371 let e_div2_eq_e2 = raw_div_hash_conv (mk_binop div_op_num e_tm two_num) in
2372 let e2_tm = rand(concl e_div2_eq_e2) in
2373 let r_th1 = raw_add_conv_hash (mk_binop add_op_num e2_tm min_exp_div2) in
2374 let r_th2 = AP_TERM (mk_comb(add_op_num, e1_tm)) r_th1 in
2375 let r_th = TRANS r_th2 (raw_add_conv_hash (rand (concl r_th2))) in
2376
2377 let r_tm = rand(concl r_th) in
2378 let r_sub_p, p_le_r = raw_sub_and_le_hash_conv p_tm r_tm in
2379 let r2_tm = rand(concl r_sub_p) in
2380 if (rand(concl p_le_r) <> r_tm) then
2381 failwith "float_sqrt_lo: underflow"
2382 else
2383 let th0 = INST[f2_tm, f2_var_num; x_tm, x_var_num; p_tm, p_var_num; r_tm, r_var_num;
2384 f1_tm, f1_var_num; n1_tm, n1_var_num; e1_tm, e1_var_num; e2_tm, e2_var_num;
2385 e_tm, e_var_num; m_tm, m_var_num; r2_tm, r2_var_num]
2386 FLOAT_SQRT_EVEN_hi' in
2387 MY_PROVE_HYP f1_2 (
2388 MY_PROVE_HYP e_div2_eq_e2 (
2389 MY_PROVE_HYP r_sub_p (
2390 MY_PROVE_HYP r_th (
2391 MY_PROVE_HYP f1f1_eq_f2 (
2392 MY_PROVE_HYP f1_num_exp (
2393 MY_PROVE_HYP even_th (
2394 MY_PROVE_HYP x_le_f2 (
2395 MY_PROVE_HYP p_le_r th0
2396 ))))))));;
2397
2398 end;; (* Float_ops module *)
2399
2400 (************************************)
2401 (* Cached floating point operations *)
2402 (************************************)
2403
2404 let init_logs () =
2405 if !Arith_options.float_log then
2406 begin
2407 Log.open_log "mul_lo";
2408 Log.open_log "mul_hi";
2409 Log.open_log "div_lo";
2410 Log.open_log "div_hi";
2411 Log.open_log "add_lo";
2412 Log.open_log "add_hi";
2413 Log.open_log "sub_lo";
2414 Log.open_log "sub_hi"
2415 end;;
2416
2417 let float_to_log_string tm =
2418 let s, n_tm, e_tm = dest_float tm in
2419 let n = (if s = "T" then minus_num else I) (raw_dest_hash n_tm) in
2420 let e = raw_dest_hash e_tm -/ Num.num_of_int Float_theory.min_exp in
2421 string_of_num n ^ "," ^ string_of_num e;;
2422
2423 let log_binop name pp tm1 tm2 =
2424 let str1 = float_to_log_string tm1 and
2425 str2 = float_to_log_string tm2 in
2426 let str = string_of_int pp ^ ":" ^ str1 ^ ";" ^ str2 in
2427 Log.append_to_log name str;;
2428
2429 (* Counters for collecting stats *)
2430 let lt0_c = ref 0 and
2431 gt0_c = ref 0 and
2432 lt_c = ref 0 and
2433 le0_c = ref 0 and
2434 ge0_c = ref 0 and
2435 le_c = ref 0 and
2436 min_c = ref 0 and
2437 max_c = ref 0 and
2438 min_max_c = ref 0 and
2439 mul_lo_c = ref 0 and
2440 mul_hi_c = ref 0 and
2441 div_lo_c = ref 0 and
2442 div_hi_c = ref 0 and
2443 add_lo_c = ref 0 and
2444 add_hi_c = ref 0 and
2445 sub_lo_c = ref 0 and
2446 sub_hi_c = ref 0 and
2447 sqrt_lo_c = ref 0 and
2448 sqrt_hi_c = ref 0;;
2449
2450 (* Hash tables *)
2451 let cache_size = if !Arith_options.float_cached then !Arith_options.init_cache_size else 1;;
2452
2453 let my_add h key v =
2454 if Hashtbl.length h >= !Arith_options.max_cache_size then
2455 Hashtbl.clear h
2456 (* let _ = Hashtbl.clear h in
2457 print_string "Clearing a float hash table" *)
2458 else
2459 ();
2460 Hashtbl.add h key v;;
2461
2462 let mul_table = Hashtbl.create cache_size and
2463 div_table = Hashtbl.create cache_size and
2464 add_table = Hashtbl.create cache_size and
2465 sub_table = Hashtbl.create cache_size and
2466 sqrt_table = Hashtbl.create cache_size and
2467 le_table = Hashtbl.create cache_size and
2468 max_table = Hashtbl.create cache_size;;
2469
2470 let reset_cache () =
2471 Hashtbl.clear mul_table;
2472 Hashtbl.clear div_table;
2473 Hashtbl.clear add_table;
2474 Hashtbl.clear sub_table;
2475 Hashtbl.clear sqrt_table;
2476 Hashtbl.clear le_table;
2477 Hashtbl.clear max_table;;
2478
2479 let reset_stat () =
2480 lt0_c := 0;
2481 gt0_c := 0;
2482 lt_c := 0;
2483 le0_c := 0;
2484 ge0_c := 0;
2485 le_c := 0;
2486 min_c := 0;
2487 max_c := 0;
2488 min_max_c := 0;
2489 mul_lo_c := 0;
2490 mul_hi_c := 0;
2491 div_lo_c := 0;
2492 div_hi_c := 0;
2493 add_lo_c := 0;
2494 add_hi_c := 0;
2495 sub_lo_c := 0;
2496 sub_hi_c := 0;
2497 sqrt_lo_c := 0;
2498 sqrt_hi_c := 0;;
2499
2500 let print_stat () =
2501 let len = Hashtbl.length in
2502 let cmp_str1 = sprintf "lt0 = %d\ngt0 = %d\nlt = %d\n" !lt0_c !gt0_c !lt_c and
2503 cmp_str2 = sprintf "le0 = %d\nge0 = %d\n" !le0_c !ge0_c and
2504 cmp_str3 = sprintf "min = %d\nmin_max = %d\n" !min_c !min_max_c and
2505 le_str = sprintf "le = %d (le_hash = %d)\n" !le_c (len le_table) and
2506 max_str = sprintf "max = %d (max_hash = %d)\n" !max_c (len max_table) and
2507 mul_str = sprintf "mul_lo = %d, mul_hi = %d (mul_hash = %d)\n" !mul_lo_c !mul_hi_c (len mul_table) and
2508 div_str = sprintf "div_lo = %d, div_hi = %d (div_hash = %d)\n" !div_lo_c !div_hi_c (len div_table) and
2509 add_str = sprintf "add_lo = %d, add_hi = %d (add_hash = %d)\n" !add_lo_c !add_hi_c (len add_table) and
2510 sub_str = sprintf "sub_lo = %d, sub_hi = %d (sub_hash = %d)\n" !sub_lo_c !sub_hi_c (len sub_table) and
2511 sqrt_str = sprintf "sqrt_lo = %d, sqrt_hi = %d (sqrt_hash = %d)\n" !sqrt_lo_c !sqrt_hi_c (len sqrt_table) in
2512 print_string (cmp_str1 ^ cmp_str2 ^ cmp_str3 ^
2513 le_str ^ max_str ^ mul_str ^ div_str ^ add_str ^ sub_str ^ sqrt_str);;
2514
2515
2516 (* lt0 *)
2517 let float_lt0 =
2518 if !Arith_options.float_cached then
2519 fun tm ->
2520 let _ = lt0_c := !lt0_c + 1 in
2521 Float_ops.float_lt0 tm
2522 else
2523 Float_ops.float_lt0;;
2524
2525 (* gt0 *)
2526 let float_gt0 =
2527 if !Arith_options.float_cached then
2528 fun tm ->
2529 let _ = gt0_c := !gt0_c + 1 in
2530 Float_ops.float_gt0 tm
2531 else
2532 Float_ops.float_gt0;;
2533
2534 (* lt *)
2535 let float_lt =
2536 if !Arith_options.float_cached then
2537 fun tm1 tm2 ->
2538 let _ = lt_c := !lt_c + 1 in
2539 Float_ops.float_lt tm1 tm2
2540 else
2541 Float_ops.float_lt;;
2542
2543 (* le0 *)
2544 let float_le0 =
2545 if !Arith_options.float_cached then
2546 fun tm ->
2547 let _ = le0_c := !le0_c + 1 in
2548 Float_ops.float_le0 tm
2549 else
2550 Float_ops.float_le0;;
2551
2552 (* ge0 *)
2553 let float_ge0 =
2554 if !Arith_options.float_cached then
2555 fun tm ->
2556 let _ = ge0_c := !ge0_c + 1 in
2557 Float_ops.float_ge0 tm
2558 else
2559 Float_ops.float_ge0;;
2560
2561 (* min *)
2562 let float_min =
2563 if !Arith_options.float_cached then
2564 fun tm1 tm2 ->
2565 let _ = min_c := !min_c + 1 in
2566 Float_ops.float_min tm1 tm2
2567 else
2568 Float_ops.float_min;;
2569
2570 (* min_max *)
2571 let float_min_max =
2572 if !Arith_options.float_cached then
2573 fun tm1 tm2 ->
2574 let _ = min_max_c := !min_max_c + 1 in
2575 Float_ops.float_min_max tm1 tm2
2576 else
2577 Float_ops.float_min_max;;
2578
2579
2580 (***************)
2581 let float_hash tm =
2582 let s, n_tm, e_tm = dest_float tm in
2583 s ^ (Arith_cache.num_tm_hash n_tm) ^ "e" ^ (Arith_cache.num_tm_hash e_tm);;
2584
2585 let float_op_hash pp tm1 tm2 =
2586 string_of_int pp ^ float_hash tm1 ^ "x" ^ float_hash tm2;;
2587
2588 let float_op_hash1 pp tm =
2589 string_of_int pp ^ float_hash tm;;
2590
2591
2592 (* le *)
2593 let float_le =
2594 if !Arith_options.float_cached then
2595 fun tm1 tm2 ->
2596 let _ = le_c := !le_c + 1 in
2597 let hash = float_op_hash 0 tm1 tm2 in
2598 try
2599 Hashtbl.find le_table hash
2600 with Not_found ->
2601 let result = Float_ops.float_le tm1 tm2 in
2602 let _ = my_add le_table hash result in
2603 result
2604 else
2605 Float_ops.float_le;;
2606
2607 (* max *)
2608 let float_max =
2609 if !Arith_options.float_cached then
2610 fun tm1 tm2 ->
2611 let _ = max_c := !max_c + 1 in
2612 let hash = float_op_hash 0 tm1 tm2 in
2613 try
2614 Hashtbl.find max_table hash
2615 with Not_found ->
2616 let result = Float_ops.float_max tm1 tm2 in
2617 let _ = my_add max_table hash result in
2618 result
2619 else
2620 Float_ops.float_max;;
2621
2622 (* mul_eq *)
2623 let float_mul_eq = Float_ops.float_mul_eq;;
2624
2625 (* mul_lo *)
2626 let float_mul_lo =
2627 if !Arith_options.float_cached then
2628 fun pp tm1 tm2 ->
2629 let _ = mul_lo_c := !mul_lo_c + 1 in
2630 let hash = "lo" ^ float_op_hash pp tm1 tm2 in
2631 try
2632 Hashtbl.find mul_table hash
2633 with Not_found ->
2634 let result = Float_ops.float_mul_lo pp tm1 tm2 in
2635 let _ = my_add mul_table hash result in
2636 let _ = if !Arith_options.float_log then log_binop "mul_lo" pp tm1 tm2 in
2637 result
2638 else
2639 if !Arith_options.float_log then
2640 fun pp tm1 tm2 ->
2641 let _ = log_binop "mul_lo" pp tm1 tm2 in
2642 Float_ops.float_mul_lo pp tm1 tm2
2643 else
2644 Float_ops.float_mul_lo;;
2645
2646 (* mul_hi *)
2647 let float_mul_hi =
2648 if !Arith_options.float_cached then
2649 fun pp tm1 tm2 ->
2650 let _ = mul_hi_c := !mul_hi_c + 1 in
2651 let hash = "hi" ^ float_op_hash pp tm1 tm2 in
2652 try
2653 Hashtbl.find mul_table hash
2654 with Not_found ->
2655 let result = Float_ops.float_mul_hi pp tm1 tm2 in
2656 let _ = my_add mul_table hash result in
2657 let _ = if !Arith_options.float_log then log_binop "mul_hi" pp tm1 tm2 in
2658 result
2659 else
2660 if !Arith_options.float_log then
2661 fun pp tm1 tm2 ->
2662 let _ = log_binop "mul_hi" pp tm1 tm2 in
2663 Float_ops.float_mul_hi pp tm1 tm2
2664 else
2665 Float_ops.float_mul_hi;;
2666
2667 (* div_lo *)
2668 let float_div_lo =
2669 if !Arith_options.float_cached then
2670 fun pp tm1 tm2 ->
2671 let _ = div_lo_c := !div_lo_c + 1 in
2672 let hash = "lo" ^ float_op_hash pp tm1 tm2 in
2673 try
2674 Hashtbl.find div_table hash
2675 with Not_found ->
2676 let result = Float_ops.float_div_lo pp tm1 tm2 in
2677 let _ = my_add div_table hash result in
2678 let _ = if !Arith_options.float_log then log_binop "div_lo" pp tm1 tm2 in
2679 result
2680 else
2681 if !Arith_options.float_log then
2682 fun pp tm1 tm2 ->
2683 let _ = log_binop "div_lo" pp tm1 tm2 in
2684 Float_ops.float_div_lo pp tm1 tm2
2685 else
2686 Float_ops.float_div_lo;;
2687
2688 (* div_hi *)
2689 let float_div_hi =
2690 if !Arith_options.float_cached then
2691 fun pp tm1 tm2 ->
2692 let _ = div_hi_c := !div_hi_c + 1 in
2693 let hash = "hi" ^ float_op_hash pp tm1 tm2 in
2694 try
2695 Hashtbl.find div_table hash
2696 with Not_found ->
2697 let result = Float_ops.float_div_hi pp tm1 tm2 in
2698 let _ = my_add div_table hash result in
2699 let _ = if !Arith_options.float_log then log_binop "div_hi" pp tm1 tm2 in
2700 result
2701 else
2702 if !Arith_options.float_log then
2703 fun pp tm1 tm2 ->
2704 let _ = log_binop "div_hi" pp tm1 tm2 in
2705 Float_ops.float_div_hi pp tm1 tm2
2706 else
2707 Float_ops.float_div_hi;;
2708
2709 (* add_lo *)
2710 let float_add_lo =
2711 if !Arith_options.float_cached then
2712 fun pp tm1 tm2 ->
2713 let _ = add_lo_c := !add_lo_c + 1 in
2714 let hash = "lo" ^ float_op_hash pp tm1 tm2 in
2715 try
2716 Hashtbl.find add_table hash
2717 with Not_found ->
2718 let result = Float_ops.float_add_lo pp tm1 tm2 in
2719 let _ = my_add add_table hash result in
2720 let _ = if !Arith_options.float_log then log_binop "add_lo" pp tm1 tm2 in
2721 result
2722 else
2723 if !Arith_options.float_log then
2724 fun pp tm1 tm2 ->
2725 let _ = log_binop "add_lo" pp tm1 tm2 in
2726 Float_ops.float_add_lo pp tm1 tm2
2727 else
2728 Float_ops.float_add_lo;;
2729
2730 (* add_hi *)
2731 let float_add_hi =
2732 if !Arith_options.float_cached then
2733 fun pp tm1 tm2 ->
2734 let _ = add_hi_c := !add_hi_c + 1 in
2735 let hash = "hi" ^ float_op_hash pp tm1 tm2 in
2736 try
2737 Hashtbl.find add_table hash
2738 with Not_found ->
2739 let result = Float_ops.float_add_hi pp tm1 tm2 in
2740 let _ = my_add add_table hash result in
2741 let _ = if !Arith_options.float_log then log_binop "add_hi" pp tm1 tm2 in
2742 result
2743 else
2744 if !Arith_options.float_log then
2745 fun pp tm1 tm2 ->
2746 let _ = log_binop "add_hi" pp tm1 tm2 in
2747 Float_ops.float_add_hi pp tm1 tm2
2748 else
2749 Float_ops.float_add_hi;;
2750
2751 (* sub_lo *)
2752 let float_sub_lo =
2753 if !Arith_options.float_cached then
2754 fun pp tm1 tm2 ->
2755 let _ = sub_lo_c := !sub_lo_c + 1 in
2756 let hash = "lo" ^ float_op_hash pp tm1 tm2 in
2757 try
2758 Hashtbl.find sub_table hash
2759 with Not_found ->
2760 let result = Float_ops.float_sub_lo pp tm1 tm2 in
2761 let _ = my_add sub_table hash result in
2762 let _ = if !Arith_options.float_log then log_binop "sub_lo" pp tm1 tm2 in
2763 result
2764 else
2765 if !Arith_options.float_log then
2766 fun pp tm1 tm2 ->
2767 let _ = log_binop "sub_lo" pp tm1 tm2 in
2768 Float_ops.float_sub_lo pp tm1 tm2
2769 else
2770 Float_ops.float_sub_lo;;
2771
2772 (* sub_hi *)
2773 let float_sub_hi =
2774 if !Arith_options.float_cached then
2775 fun pp tm1 tm2 ->
2776 let _ = sub_hi_c := !sub_hi_c + 1 in
2777 let hash = "hi" ^ float_op_hash pp tm1 tm2 in
2778 try
2779 Hashtbl.find sub_table hash
2780 with Not_found ->
2781 let result = Float_ops.float_sub_hi pp tm1 tm2 in
2782 let _ = my_add sub_table hash result in
2783 let _ = if !Arith_options.float_log then log_binop "sub_hi" pp tm1 tm2 in
2784 result
2785 else
2786 if !Arith_options.float_log then
2787 fun pp tm1 tm2 ->
2788 let _ = log_binop "sub_hi" pp tm1 tm2 in
2789 Float_ops.float_sub_hi pp tm1 tm2
2790 else
2791 Float_ops.float_sub_hi;;
2792
2793 (* sqrt_lo *)
2794 let float_sqrt_lo =
2795 if !Arith_options.float_cached then
2796 fun pp tm ->
2797 let _ = sqrt_lo_c := !sqrt_lo_c + 1 in
2798 let hash = "lo" ^ float_op_hash1 pp tm in
2799 try
2800 Hashtbl.find sqrt_table hash
2801 with Not_found ->
2802 let result = Float_ops.float_sqrt_lo pp tm in
2803 let _ = my_add sqrt_table hash result in
2804 result
2805 else
2806 Float_ops.float_sqrt_lo;;
2807
2808 (* sqrt_hi *)
2809 let float_sqrt_hi =
2810 if !Arith_options.float_cached then
2811 fun pp tm ->
2812 let _ = sqrt_hi_c := !sqrt_hi_c + 1 in
2813 let hash = "hi" ^ float_op_hash1 pp tm in
2814 try
2815 Hashtbl.find sqrt_table hash
2816 with Not_found ->
2817 let result = Float_ops.float_sqrt_hi pp tm in
2818 let _ = my_add sqrt_table hash result in
2819 result
2820 else
2821 Float_ops.float_sqrt_hi;;
2822
2823
2824
2825 (* ------------------------------------------------ *)
2826 (* Special comparison operations *)
2827 (* ------------------------------------------------ *)
2828
2829 (* For a given floating-point term returns its components as OCaml objects *)
2830 let dest_float_raw f_tm =
2831 let s, n_tm, e_tm = dest_float f_tm in
2832 let sign = if s = "T" then true else false in
2833 sign, raw_dest_hash n_tm, raw_dest_hash e_tm;;
2834
2835 (* Compares raw representations of two floating-point numbers f1 and f2. *)
2836 (* Returns -1 if f1 < f2, 0 if f1 = f2, and 1 if f1 > f2. *)
2837 let compare_floats_raw =
2838 let denorm n e = n */ (Num.num_of_int Arith_num.arith_base **/ e) in
2839 let cmp n1 e1 n2 e2 =
2840 if e1 <= e2 then
2841 compare_num n1 (denorm n2 (e2 -/ e1))
2842 else
2843 compare_num (denorm n1 (e1 -/ e2)) n2 in
2844 fun f1_tm f2_tm ->
2845 let s1, n1, e1 = dest_float_raw f1_tm and
2846 s2, n2, e2 = dest_float_raw f2_tm in
2847 let n1' = if s1 then minus_num n1 else n1 and
2848 n2' = if s2 then minus_num n2 else n2 in
2849 cmp n1' e1 n2' e2;;
2850
2851 (* Returns (true, |- f1 <= f2 <=> T) when f1 <= f2; returns (false, |- f1 <= f2 <=> F) otherwise *)
2852 let float_prove_le f1_tm f2_tm =
2853 let le_th = float_le f1_tm f2_tm in
2854 let flag = (fst o dest_const o rand o concl) le_th = "T" in
2855 flag, le_th;;
2856
2857 (* Returns (true, |- f1 < f2 <=> T) when f1 < f2; returns (false, |- f1 < f2 <=> F) otherwise *)
2858 let float_prove_lt f1_tm f2_tm =
2859 let lt_th = float_lt f1_tm f2_tm in
2860 let flag = (fst o dest_const o rand o concl) lt_th = "T" in
2861 flag, lt_th;;
2862
2863 (*
2864 (* Arith_num.raw_dest_hash is too slow (need to retest without caching) *)
2865 let float_prove_le f1_tm f2_tm =
2866 let r = compare_floats_raw f1_tm f2_tm in
2867 if r <= 0 then
2868 true, float_le f1_tm f2_tm
2869 else
2870 false, TRUTH;;
2871 *)
2872
2873 (* Compares y and an interval a <= x <= b (|- interval_arith x (a, b)). *)
2874 (* Returns (true, |- y <= x) if y <= a. *)
2875 (* Returns (false, |- y <= a <=> F) if y > a. *)
2876 let float_prove_le_interval =
2877 let le_interval = (UNDISCH_ALL o prove)(`interval_arith x (a,b) ==> (y <= a <=> T) ==> y <= x`,
2878 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) in
2879 fun y_tm x_th ->
2880 let x_tm, bounds = dest_interval_arith (concl x_th) in
2881 let ltm, b_tm = dest_comb bounds in
2882 let a_tm = rand ltm in
2883 let flag, le_th = float_prove_le y_tm a_tm in
2884 if flag then
2885 let th0 = INST[x_tm, x_var_real; y_tm, y_var_real;
2886 a_tm, a_var_real; b_tm, b_var_real] le_interval in
2887 true, MY_PROVE_HYP x_th (MY_PROVE_HYP le_th th0)
2888 else
2889 false, le_th;;
2890
2891 (* Compares y and an interval a <= x <= b (|- interval_arith x (a, b)). *)
2892 (* Returns (true, |- x <= y) if b <= y. *)
2893 (* Returns (false, |- b <= y <=> F) if b > y. *)
2894 let float_prove_ge_interval =
2895 let ge_interval = (UNDISCH_ALL o prove)(`interval_arith x (a,b) ==> (b <= y <=> T) ==> x <= y`,
2896 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) in
2897 fun y_tm x_th ->
2898 let x_tm, bounds = dest_interval_arith (concl x_th) in
2899 let ltm, b_tm = dest_comb bounds in
2900 let a_tm = rand ltm in
2901 let flag, le_th = float_prove_le b_tm y_tm in
2902 if flag then
2903 let th0 = INST[x_tm, x_var_real; y_tm, y_var_real;
2904 a_tm, a_var_real; b_tm, b_var_real] ge_interval in
2905 true, MY_PROVE_HYP x_th (MY_PROVE_HYP le_th th0)
2906 else
2907 false, le_th;;
2908
2909 (* Compares y and an interval a <= x <= b (|- interval_arith x (a, b)). *)
2910 (* Returns (true, |- y < x) if y < a. *)
2911 (* Returns (false, |- y < a <=> F) if y >= a. *)
2912 let float_prove_lt_interval =
2913 let lt_interval = (UNDISCH_ALL o prove)(`interval_arith x (a,b) ==> (y < a <=> T) ==> y < x`,
2914 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) in
2915 fun y_tm x_th ->
2916 let x_tm, bounds = dest_interval_arith (concl x_th) in
2917 let ltm, b_tm = dest_comb bounds in
2918 let a_tm = rand ltm in
2919 let flag, lt_th = float_prove_lt y_tm a_tm in
2920 if flag then
2921 let th0 = INST[x_tm, x_var_real; y_tm, y_var_real;
2922 a_tm, a_var_real; b_tm, b_var_real] lt_interval in
2923 true, MY_PROVE_HYP x_th (MY_PROVE_HYP lt_th th0)
2924 else
2925 false, lt_th;;
2926
2927 (* Compares y and an interval a <= x <= b (|- interval_arith x (a, b)). *)
2928 (* Returns (true, |- x < y) if b < y. *)
2929 (* Returns (false, |- b < y <=> F) if b >= y. *)
2930 let float_prove_gt_interval =
2931 let gt_interval = (UNDISCH_ALL o prove)(`interval_arith x (a,b) ==> (b < y <=> T) ==> x < y`,
2932 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) in
2933 fun y_tm x_th ->
2934 let x_tm, bounds = dest_interval_arith (concl x_th) in
2935 let ltm, b_tm = dest_comb bounds in
2936 let a_tm = rand ltm in
2937 let flag, lt_th = float_prove_lt b_tm y_tm in
2938 if flag then
2939 let th0 = INST[x_tm, x_var_real; y_tm, y_var_real;
2940 a_tm, a_var_real; b_tm, b_var_real] gt_interval in
2941 true, MY_PROVE_HYP x_th (MY_PROVE_HYP lt_th th0)
2942 else
2943 false, lt_th;;
2944
2945 (* Compares y and an interval a <= x <= b (|- interval_arith x (a, b)). *)
2946 (* Returns (-1, |- y <= x) if y <= a. *)
2947 (* Returns (1, |- x <= y) if b <= y. *)
2948 (* Returns (0, |- T ) otherwise. *)
2949 let float_compare_interval =
2950 let le_interval = (UNDISCH_ALL o prove)(`interval_arith x (a,b) ==> (y <= a <=> T) ==> y <= x`,
2951 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) in
2952 let ge_interval = (UNDISCH_ALL o prove)(`interval_arith x (a,b) ==> (b <= y <=> T) ==> x <= y`,
2953 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) in
2954 fun y_tm x_th ->
2955 let x_tm, bounds = dest_interval_arith (concl x_th) in
2956 let ltm, b_tm = dest_comb bounds in
2957 let a_tm = rand ltm in
2958 let inst th le_th =
2959 let th0 = INST[x_tm, x_var_real; y_tm, y_var_real;
2960 a_tm, a_var_real; b_tm, b_var_real] th in
2961 MY_PROVE_HYP x_th (MY_PROVE_HYP le_th th0) in
2962 let flag, le_th = float_prove_le y_tm a_tm in
2963 if flag then
2964 -1, inst le_interval le_th
2965 else
2966 let flag, le_th = float_prove_le b_tm y_tm in
2967 if flag then
2968 1, inst ge_interval le_th
2969 else
2970 0, TRUTH;;
2971
2972
2973 (* ------------------------------------------------ *)
2974 (* Float interval operations *)
2975 (* ------------------------------------------------ *)
2976
2977 let FLOAT_OF_NUM' = (SPEC_ALL o REWRITE_RULE[min_exp_def]) FLOAT_OF_NUM;;
2978
2979 let FLOAT_INTERVAL_OF_NUM = (NUMERALS_TO_NUM o REWRITE_RULE[min_exp_def] o prove)(`interval_arith (&n) (float_num F n min_exp, float_num F n min_exp)`,
2980 REWRITE_TAC[FLOAT_OF_NUM; CONST_INTERVAL]);;
2981
2982 let FLOAT_F_bound' = (UNDISCH_ALL o SPEC_ALL) FLOAT_F_bound;;
2983
2984 let FLOAT_T_bound' = (UNDISCH_ALL o SPEC_ALL) FLOAT_T_bound;;
2985
2986 (* interval_arith x (float_num s1 n1 e1, float_num s2 n2 e2) -> x, float_num s1 n1 e1, float_num s2 n2 e2 *)
2987 let dest_float_interval tm =
2988 let ltm, rtm = dest_comb tm in
2989 let f1, f2 = dest_pair rtm in
2990 rand ltm, f1, f2;;
2991
2992 let mk_float_interval_small_num n =
2993 let n_tm0 = mk_small_numeral n in
2994 let n_th = NUMERAL_TO_NUM_CONV n_tm0 in
2995 let n_tm = rand(rand(concl n_th)) in
2996 let n_th1 = TRANS n_th (INST[n_tm, n_var_num] NUM_REMOVE) in
2997 let th1 = AP_TERM amp_op_real n_th1 in
2998 let int_th = INST[n_tm, n_var_num] FLOAT_INTERVAL_OF_NUM in
2999 let rtm = rand(concl int_th) in
3000 EQ_MP (SYM (AP_THM (AP_TERM interval_const th1) rtm)) int_th;;
3001
3002 let mk_float_interval_num n =
3003 let n_tm0 = mk_numeral n in
3004 let n_th = NUMERAL_TO_NUM_CONV n_tm0 in
3005 let n_tm = rand(rand(concl n_th)) in
3006 let n_th1 = TRANS n_th (INST[n_tm, n_var_num] NUM_REMOVE) in
3007 let th1 = AP_TERM amp_op_real n_th1 in
3008 let int_th = INST[n_tm, n_var_num] FLOAT_INTERVAL_OF_NUM in
3009 let rtm = rand(concl int_th) in
3010 EQ_MP (SYM (AP_THM (AP_TERM interval_const th1) rtm)) int_th;;
3011
3012
3013 (* Returns the lower bound for the given float *)
3014 let float_lo p tm =
3015 let s, n_tm, e_tm = dest_float tm in
3016 if s = "F" then
3017 let num_exp_tm = mk_num_exp n_tm e_tm in
3018 let th0 = num_exp_lo p num_exp_tm in
3019 let ltm, e1_tm = dest_comb(lhand(concl th0)) in
3020 let n1_tm = rand ltm in
3021 let th1 = INST[n1_tm, n1_var_num; e1_tm, e1_var_num; n_tm, n2_var_num; e_tm, e2_var_num] FLOAT_F_bound' in
3022 MY_PROVE_HYP th0 th1
3023 else
3024 let num_exp_tm = mk_num_exp n_tm e_tm in
3025 let th0 = num_exp_hi p num_exp_tm in
3026 let ltm, e1_tm = dest_comb(rand(concl th0)) in
3027 let n1_tm = rand ltm in
3028 let th1 = INST[n_tm, n1_var_num; e_tm, e1_var_num; n1_tm, n2_var_num; e1_tm, e2_var_num] FLOAT_T_bound' in
3029 MY_PROVE_HYP th0 th1;;
3030
3031 (* Returns the upper bound for the given float *)
3032 let float_hi p tm =
3033 let s, n_tm, e_tm = dest_float tm in
3034 if s = "F" then
3035 let num_exp_tm = mk_num_exp n_tm e_tm in
3036 let th0 = num_exp_hi p num_exp_tm in
3037 let ltm, e2_tm = dest_comb(rand(concl th0)) in
3038 let n2_tm = rand ltm in
3039 let th1 = INST[n_tm, n1_var_num; e_tm, e1_var_num; n2_tm, n2_var_num; e2_tm, e2_var_num] FLOAT_F_bound' in
3040 MY_PROVE_HYP th0 th1
3041 else
3042 let num_exp_tm = mk_num_exp n_tm e_tm in
3043 let th0 = num_exp_lo p num_exp_tm in
3044 let ltm, e1_tm = dest_comb(lhand(concl th0)) in
3045 let n1_tm = rand ltm in
3046 let th1 = INST[n1_tm, n1_var_num; e1_tm, e1_var_num; n_tm, n2_var_num; e_tm, e2_var_num] FLOAT_T_bound' in
3047 MY_PROVE_HYP th0 th1;;
3048
3049
3050 (* Approximates the given interval with p-digits floating point numbers *)
3051 let float_interval_round p th =
3052 let x_tm, f1, f2 = dest_float_interval (concl th) in
3053 let lo_th = float_lo p f1 in
3054 let hi_th = float_hi p f2 in
3055 let lo_tm = lhand(concl lo_th) in
3056 let hi_tm = rand(concl hi_th) in
3057 let th0 = INST[x_tm, x_var_real; f1, lo_var_real; f2, hi_var_real; lo_tm, a_var_real; hi_tm, b_var_real] APPROX_INTERVAL' in
3058 MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th (MY_PROVE_HYP th th0));;
3059
3060
3061 (* ------------------------------------------------ *)
3062 (* Absolute value of an interval *)
3063 (* ------------------------------------------------ *)
3064
3065 let RULE = UNDISCH_ALL o NUMERALS_TO_NUM o PURE_REWRITE_RULE[GSYM IMP_IMP; min_exp_def];;
3066
3067 let float_interval_abs_ft = (RULE o prove)
3068 (`interval_arith x (float_num F n1 e1, float_num T n2 e2)
3069 ==> interval_arith (abs x) (float_num F 0 min_exp, float_num F 0 min_exp)`,
3070 DISCH_THEN (MP_TAC o MATCH_MP FLOAT_INTERVAL_FT_IMP_0) THEN
3071 REWRITE_TAC[FLOAT_0; interval_arith] THEN REAL_ARITH_TAC);;
3072
3073 let float_interval_abs_ff = (RULE o prove)
3074 (`interval_arith x (float_num F n1 e1, float_num F n2 e2)
3075 ==> interval_arith (abs x) (float_num F n1 e1, float_num F n2 e2)`,
3076 MP_TAC (SPECL[`n1:num`; `e1:num`] FLOAT_F_POS) THEN
3077 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);;
3078
3079 let float_interval_abs_tt = (RULE o prove)
3080 (`interval_arith x (float_num T n1 e1, float_num T n2 e2)
3081 ==> interval_arith (abs x) (float_num F n2 e2, float_num F n1 e1)`,
3082 MP_TAC ((GSYM o SPEC `T`) FLOAT_NEG) THEN SIMP_TAC[] THEN DISCH_TAC THEN
3083 MP_TAC (SPECL[`n2:num`; `e2:num`] FLOAT_T_NEG) THEN
3084 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);;
3085
3086 let float_interval_abs_tf = (RULE o prove)
3087 (`interval_arith x (float_num T n1 e1, float_num F n2 e2) /\
3088 max (float_num F n1 e1) (float_num F n2 e2) = t
3089 ==> interval_arith (abs x) (float_num F 0 min_exp, t)`,
3090 MP_TAC ((GSYM o SPEC `F`) FLOAT_NEG) THEN SIMP_TAC[] THEN DISCH_TAC THEN
3091 REWRITE_TAC[interval_arith; FLOAT_0] THEN REAL_ARITH_TAC);;
3092
3093 let float_interval_abs th =
3094 let x, lo, hi = dest_float_interval (concl th) in
3095 let s1, n1, e1 = dest_float lo and
3096 s2, n2, e2 = dest_float hi in
3097 let inst = INST[x, x_var_real;
3098 n1, n1_var_num; e1, e1_var_num;
3099 n2, n2_var_num; e2, e2_var_num] in
3100 if s1 = s2 then
3101 if s1 = "F" then
3102 (* FF *)
3103 MY_PROVE_HYP th (inst float_interval_abs_ff)
3104 else
3105 (* TT *)
3106 MY_PROVE_HYP th (inst float_interval_abs_tt)
3107 else
3108 if s1 = "F" then
3109 (* FT *)
3110 MY_PROVE_HYP th (inst float_interval_abs_ft)
3111 else
3112 let max_th = float_max (make_float "F" n1 e1) hi in
3113 let t_tm = rand (concl max_th) in
3114 let th0 = INST[x, x_var_real; t_tm, t_var_real;
3115 n1, n1_var_num; e1, e1_var_num;
3116 n2, n2_var_num; e2, e2_var_num] float_interval_abs_tf in
3117 MY_PROVE_HYP max_th (MY_PROVE_HYP th th0);;
3118
3119
3120 (****************************************)
3121 (* float_interval_lt *)
3122
3123 let FLOAT_INTERVAL_LT = prove(`interval_arith x (lo1, hi1) /\ interval_arith y (lo2, hi2) /\ hi1 < lo2
3124 ==> x < y`,
3125 REWRITE_TAC[interval_arith] THEN
3126 REAL_ARITH_TAC);;
3127
3128
3129 (****************************************)
3130 (* float_interval_neg *)
3131
3132 let FLOAT_INTERVAL_NEG = prove(`!s1 s2. interval_arith x (float_num s1 n1 e1, float_num s2 n2 e2)
3133 ==> interval_arith (--x) (float_num (~s2) n2 e2, float_num (~s1) n1 e1)`,
3134 REPEAT GEN_TAC THEN
3135 DISCH_THEN (fun th -> MP_TAC (MATCH_MP INTERVAL_NEG th)) THEN
3136 SIMP_TAC[FLOAT_NEG]);;
3137
3138 let FLOAT_INTERVAL_NEG_FF = (UNDISCH_ALL o REWRITE_RULE[] o SPECL[`F`; `F`]) FLOAT_INTERVAL_NEG;;
3139 let FLOAT_INTERVAL_NEG_FT = (UNDISCH_ALL o REWRITE_RULE[] o SPECL[`F`; `T`]) FLOAT_INTERVAL_NEG;;
3140 let FLOAT_INTERVAL_NEG_TF = (UNDISCH_ALL o REWRITE_RULE[] o SPECL[`T`; `F`]) FLOAT_INTERVAL_NEG;;
3141 let FLOAT_INTERVAL_NEG_TT = (UNDISCH_ALL o REWRITE_RULE[] o SPECL[`T`; `T`]) FLOAT_INTERVAL_NEG;;
3142
3143 (* |- interval x (float s1 n1 e1, float s2 n2 e2) ->
3144 |- interval (--x) (float ~s2 n2 e2, float ~s1 n1 e1 *)
3145 let float_interval_neg th =
3146 let x_tm, f1, f2 = dest_float_interval (concl th) in
3147 let s1, n1_tm, e1_tm = dest_float f1 in
3148 let s2, n2_tm, e2_tm = dest_float f2 in
3149 let inst = INST[x_tm, x_var_real; n1_tm, n1_var_num; e1_tm, e1_var_num;
3150 n2_tm, n2_var_num; e2_tm, e2_var_num] in
3151 let th0 =
3152 if s1 = "F" then
3153 if s2 = "F" then
3154 inst FLOAT_INTERVAL_NEG_FF
3155 else
3156 inst FLOAT_INTERVAL_NEG_FT
3157 else
3158 if s2 = "F" then
3159 inst FLOAT_INTERVAL_NEG_TF
3160 else
3161 inst FLOAT_INTERVAL_NEG_TT in
3162 MY_PROVE_HYP th th0;;
3163
3164
3165 (***********************************************)
3166 (* float_interval_mul *)
3167
3168 let f1_1_var = `f1_1:real` and
3169 f1_2_var = `f1_2:real` and
3170 f2_1_var = `f2_1:real` and
3171 f2_2_var = `f2_2:real`;;
3172
3173
3174 (* FT_xx *)
3175 let FLOAT_INTERVAL_MUL_FT_xx = (UNDISCH_ALL o NUMERALS_TO_NUM o REWRITE_RULE[GSYM IMP_IMP; min_exp_def] o prove)(
3176 `interval_arith x (float_num F n1 e1, float_num T n2 e2)
3177 ==> interval_arith (x * y) (float_num F 0 min_exp, float_num F 0 min_exp)`,
3178 STRIP_TAC THEN
3179 FIRST_X_ASSUM (fun th -> REWRITE_TAC[MATCH_MP FLOAT_INTERVAL_FT_IMP_0 th]) THEN
3180 REWRITE_TAC[REAL_MUL_LZERO; interval_arith] THEN
3181 MP_TAC (GEN_ALL (SPECL [`s:bool`; `0`] FLOAT_EQ_0)) THEN SIMP_TAC[REAL_LE_REFL]);;
3182
3183
3184 (* xx_FT *)
3185 let FLOAT_INTERVAL_MUL_xx_FT = (UNDISCH_ALL o NUMERALS_TO_NUM o REWRITE_RULE[GSYM IMP_IMP; min_exp_def] o prove)(
3186 `interval_arith y (float_num F m1 r1, float_num T m2 r2)
3187 ==> interval_arith (x * y) (float_num F 0 min_exp, float_num F 0 min_exp)`,
3188 STRIP_TAC THEN
3189 FIRST_X_ASSUM (fun th -> REWRITE_TAC[MATCH_MP FLOAT_INTERVAL_FT_IMP_0 th]) THEN
3190 REWRITE_TAC[REAL_MUL_RZERO; interval_arith] THEN
3191 MP_TAC (GEN_ALL (SPECL [`s:bool`; `0`] FLOAT_EQ_0)) THEN SIMP_TAC[REAL_LE_REFL]);;
3192
3193
3194
3195 (* FF_FF *)
3196 let FLOAT_INTERVAL_MUL_FF_FF = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3197 `interval_arith x (float_num F n1 e1, float_num F n2 e2) /\
3198 interval_arith y (float_num F m1 r1, float_num F m2 r2) /\
3199 f1 <= float_num F n1 e1 * float_num F m1 r1 /\
3200 float_num F n2 e2 * float_num F m2 r2 <= f2
3201 ==> interval_arith (x * y) (f1, f2)`,
3202 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3203 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` MP_TAC THENL
3204 [
3205 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN
3206 REWRITE_TAC[FLOAT_F_POS];
3207 ALL_TAC
3208 ] THEN
3209 REPEAT (POP_ASSUM (fun th -> ALL_TAC)) THEN
3210 REWRITE_TAC[interval_arith] THEN
3211 REPEAT STRIP_TAC THENL
3212 [
3213 MATCH_MP_TAC REAL_LE_TRANS THEN
3214 EXISTS_TAC `a * c:real` THEN
3215 ASM_REWRITE_TAC[] THEN
3216 MATCH_MP_TAC REAL_LE_MUL2 THEN
3217 ASM_REWRITE_TAC[];
3218 MATCH_MP_TAC REAL_LE_TRANS THEN
3219 EXISTS_TAC `b * d:real` THEN
3220 ASM_REWRITE_TAC[] THEN
3221 MATCH_MP_TAC REAL_LE_MUL2 THEN
3222 ASM_REWRITE_TAC[] THEN
3223 CONJ_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THENL
3224 [
3225 EXISTS_TAC `a:real` THEN ASM_REWRITE_TAC[];
3226 EXISTS_TAC `c:real` THEN ASM_REWRITE_TAC[]
3227 ]
3228 ]);;
3229
3230 (* TT_TT *)
3231 let FLOAT_INTERVAL_MUL_TT_TT = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3232 `interval_arith x (float_num T n1 e1, float_num T n2 e2) /\
3233 interval_arith y (float_num T m1 r1, float_num T m2 r2) /\
3234 f1 <= float_num T n2 e2 * float_num T m2 r2 /\
3235 float_num T n1 e1 * float_num T m1 r1 <= f2
3236 ==> interval_arith (x * y) (f1, f2)`,
3237 REWRITE_TAC[FLOAT_NEG_T] THEN
3238 REWRITE_TAC[interval_arith] THEN
3239 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3240 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` MP_TAC THENL
3241 [
3242 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN
3243 REWRITE_TAC[FLOAT_F_POS];
3244 ALL_TAC
3245 ] THEN
3246 REWRITE_TAC[REAL_NEG_MUL2] THEN
3247 REPEAT STRIP_TAC THENL
3248 [
3249 MATCH_MP_TAC REAL_LE_TRANS THEN
3250 EXISTS_TAC `b * d:real` THEN
3251 ASM_REWRITE_TAC[] THEN
3252 ONCE_REWRITE_TAC[REAL_ARITH `a <= x * y <=> a <= --x * --y`] THEN
3253 MATCH_MP_TAC REAL_LE_MUL2 THEN
3254 ONCE_REWRITE_TAC[REAL_ARITH `b <= --x <=> x <= --b`] THEN
3255 ASM_REWRITE_TAC[];
3256 MATCH_MP_TAC REAL_LE_TRANS THEN
3257 EXISTS_TAC `a * c:real` THEN
3258 ASM_REWRITE_TAC[] THEN
3259 ONCE_REWRITE_TAC[REAL_ARITH `x * y <= a <=> --x * --y <= a`] THEN
3260 MATCH_MP_TAC REAL_LE_MUL2 THEN
3261 ONCE_REWRITE_TAC[REAL_ARITH `--x <= c <=> --c <= x`] THEN
3262 ASM_REWRITE_TAC[] THEN
3263 ASSUME_TAC (REAL_ARITH `!b x. &0 <= b /\ x <= --b ==> &0 <= --x`) THEN
3264 CONJ_TAC THEN FIRST_X_ASSUM MATCH_MP_TAC THENL
3265 [
3266 EXISTS_TAC `b:real` THEN ASM_REWRITE_TAC[];
3267 EXISTS_TAC `d:real` THEN ASM_REWRITE_TAC[]
3268 ]
3269 ]);;
3270
3271 (* FF_TT *)
3272 let FLOAT_INTERVAL_MUL_FF_TT = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3273 `interval_arith x (float_num F n1 e1, float_num F n2 e2) /\
3274 interval_arith y (float_num T m1 r1, float_num T m2 r2) /\
3275 f1 <= float_num F n2 e2 * float_num T m1 r1 /\
3276 float_num F n1 e1 * float_num T m2 r2 <= f2
3277 ==> interval_arith (x * y) (f1, f2)`,
3278 REWRITE_TAC[FLOAT_NEG_T] THEN
3279 REWRITE_TAC[interval_arith] THEN
3280 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3281 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` MP_TAC THENL
3282 [
3283 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN
3284 REWRITE_TAC[FLOAT_F_POS];
3285 ALL_TAC
3286 ] THEN
3287
3288 REPEAT STRIP_TAC THENL
3289 [
3290 MATCH_MP_TAC REAL_LE_TRANS THEN
3291 EXISTS_TAC `b * --c` THEN
3292 ASM_REWRITE_TAC[] THEN
3293 ONCE_REWRITE_TAC[REAL_ARITH `b * --c <= x * y <=> x * --y <= b * c`] THEN
3294 MATCH_MP_TAC REAL_LE_MUL2 THEN
3295 ONCE_REWRITE_TAC[REAL_ARITH `--y <= c <=> --c <= y`] THEN
3296 ASM_REWRITE_TAC[] THEN
3297 CONJ_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THENL
3298 [
3299 EXISTS_TAC `a:real` THEN ASM_REWRITE_TAC[];
3300 EXISTS_TAC `d:real` THEN
3301 ONCE_REWRITE_TAC[REAL_ARITH `d <= --y <=> y <= --d`] THEN
3302 ASM_REWRITE_TAC[]
3303 ];
3304
3305 MATCH_MP_TAC REAL_LE_TRANS THEN
3306 EXISTS_TAC `a * --d` THEN
3307 ASM_REWRITE_TAC[] THEN
3308 ONCE_REWRITE_TAC[REAL_ARITH `x * y <= a * --d <=> a * d <= x * --y`] THEN
3309 MATCH_MP_TAC REAL_LE_MUL2 THEN
3310 ONCE_REWRITE_TAC[REAL_ARITH `d <= --y <=> y <= --d`] THEN
3311 ASM_REWRITE_TAC[]
3312 ]);;
3313
3314 (* TT_FF *)
3315 let FLOAT_INTERVAL_MUL_TT_FF = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3316 `interval_arith x (float_num T n1 e1, float_num T n2 e2) /\
3317 interval_arith y (float_num F m1 r1, float_num F m2 r2) /\
3318 f1 <= float_num T n1 e1 * float_num F m2 r2 /\
3319 float_num T n2 e2 * float_num F m1 r1 <= f2
3320 ==> interval_arith (x * y) (f1, f2)`,
3321 STRIP_TAC THEN
3322 MP_TAC ((GEN_ALL o DISCH_ALL) FLOAT_INTERVAL_MUL_FF_TT) THEN
3323 DISCH_THEN (MP_TAC o SPECL[`n1:num`; `e1:num`; `n2:num`; `e2:num`; `m1:num`; `r1:num`; `m2:num`; `r2:num`]) THEN
3324 DISCH_THEN (MP_TAC o SPECL[`y:real`; `x:real`; `f1:real`; `f2:real`]) THEN
3325 REPEAT (POP_ASSUM MP_TAC) THEN
3326 SIMP_TAC[REAL_MUL_AC]);;
3327
3328 (* TF_FF *)
3329 let FLOAT_INTERVAL_MUL_TF_FF = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3330 `interval_arith x (float_num T n1 e1, float_num F n2 e2) /\
3331 interval_arith y (float_num F m1 r1, float_num F m2 r2) /\
3332 f1 <= float_num T n1 e1 * float_num F m2 r2 /\
3333 float_num F n2 e2 * float_num F m2 r2 <= f2
3334 ==> interval_arith (x * y) (f1, f2)`,
3335 REWRITE_TAC[FLOAT_NEG_T] THEN
3336 REWRITE_TAC[interval_arith] THEN
3337 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3338 STRIP_TAC THEN
3339 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` ASSUME_TAC THENL
3340 [
3341 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN
3342 REWRITE_TAC[FLOAT_F_POS];
3343 ALL_TAC
3344 ] THEN
3345
3346 SUBGOAL_THEN `&0 <= y` ASSUME_TAC THENL
3347 [
3348 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `c:real` THEN ASM_REWRITE_TAC[];
3349 ALL_TAC
3350 ] THEN
3351
3352 CONJ_TAC THENL
3353 [
3354 DISJ_CASES_TAC (REAL_ARITH `&0 <= x \/ &0 <= --x`) THENL
3355 [
3356 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3357 CONJ_TAC THENL
3358 [
3359 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a * d` THEN
3360 ASM_REWRITE_TAC[REAL_ARITH `--a * d <= &0 <=> &0 <= a * d`] THEN
3361 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3362 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[]
3363 ];
3364 ALL_TAC
3365 ] THEN
3366
3367 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a * d` THEN ASM_REWRITE_TAC[] THEN
3368 ONCE_REWRITE_TAC[REAL_ARITH `--a * d <= x * y <=> --x * y <= a * d`] THEN
3369 MATCH_MP_TAC REAL_LE_MUL2 THEN
3370 ONCE_REWRITE_TAC[REAL_ARITH `--x <= a <=> --a <= x`] THEN ASM_REWRITE_TAC[];
3371
3372 DISJ_CASES_TAC (REAL_ARITH `&0 <= --x \/ &0 <= x`) THENL
3373 [
3374 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3375 CONJ_TAC THENL
3376 [
3377 REWRITE_TAC[REAL_ARITH `x * y <= &0 <=> &0 <= --x * y`] THEN
3378 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3379 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b * d` THEN ASM_REWRITE_TAC[] THEN
3380 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[]
3381 ];
3382 ALL_TAC
3383 ] THEN
3384
3385 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b * d` THEN ASM_REWRITE_TAC[] THEN
3386 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[]
3387 ]);;
3388
3389 (* TF_TT *)
3390 let FLOAT_INTERVAL_MUL_TF_TT = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3391 `interval_arith x (float_num T n1 e1, float_num F n2 e2) /\
3392 interval_arith y (float_num T m1 r1, float_num T m2 r2) /\
3393 f1 <= float_num F n2 e2 * float_num T m1 r1 /\
3394 float_num T n1 e1 * float_num T m1 r1 <= f2
3395 ==> interval_arith (x * y) (f1, f2)`,
3396 REWRITE_TAC[FLOAT_NEG_T] THEN
3397 REWRITE_TAC[interval_arith] THEN
3398 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3399 STRIP_TAC THEN
3400 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` ASSUME_TAC THENL
3401 [
3402 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN
3403 REWRITE_TAC[FLOAT_F_POS];
3404 ALL_TAC
3405 ] THEN
3406
3407 SUBGOAL_THEN `&0 <= --y` ASSUME_TAC THENL
3408 [
3409 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `d:real` THEN
3410 ONCE_REWRITE_TAC[REAL_ARITH `d <= --y <=> y <= --d`] THEN ASM_REWRITE_TAC[];
3411 ALL_TAC
3412 ] THEN
3413
3414 CONJ_TAC THENL
3415 [
3416 DISJ_CASES_TAC (REAL_ARITH `&0 <= --x \/ &0 <= x`) THENL
3417 [
3418 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3419 CONJ_TAC THENL
3420 [
3421 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b * --c` THEN
3422 ASM_REWRITE_TAC[REAL_ARITH `b * --c <= &0 <=> &0 <= b * c`] THEN
3423 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3424 ONCE_REWRITE_TAC[REAL_ARITH `x * y = --x * --y`] THEN
3425 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[]
3426 ];
3427 ALL_TAC
3428 ] THEN
3429
3430 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b * --c` THEN ASM_REWRITE_TAC[] THEN
3431 ONCE_REWRITE_TAC[REAL_ARITH `b * --c <= x * y <=> x * --y <= b * c`] THEN
3432 MATCH_MP_TAC REAL_LE_MUL2 THEN ONCE_REWRITE_TAC[REAL_ARITH `--y <= c <=> --c <= y`] THEN
3433 ASM_REWRITE_TAC[];
3434
3435 DISJ_CASES_TAC (REAL_ARITH `&0 <= x \/ &0 <= --x`) THENL
3436 [
3437 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3438 CONJ_TAC THENL
3439 [
3440 REWRITE_TAC[REAL_ARITH `x * y <= &0 <=> &0 <= x * --y`] THEN
3441 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3442 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a * --c` THEN ASM_REWRITE_TAC[REAL_NEG_MUL2] THEN
3443 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[]
3444 ];
3445 ALL_TAC
3446 ] THEN
3447
3448 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a * --c` THEN ASM_REWRITE_TAC[REAL_NEG_MUL2] THEN
3449 ONCE_REWRITE_TAC[REAL_ARITH `x * y <= a * c <=> --x * --y <= a * c`] THEN
3450 MATCH_MP_TAC REAL_LE_MUL2 THEN ONCE_REWRITE_TAC[REAL_ARITH `--x <= a <=> --a <= x`] THEN
3451 ASM_REWRITE_TAC[]
3452 ]);;
3453
3454 (* FF_TF *)
3455 let FLOAT_INTERVAL_MUL_FF_TF = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3456 `interval_arith x (float_num F n1 e1, float_num F n2 e2) /\
3457 interval_arith y (float_num T m1 r1, float_num F m2 r2) /\
3458 f1 <= float_num F n2 e2 * float_num T m1 r1 /\
3459 float_num F n2 e2 * float_num F m2 r2 <= f2
3460 ==> interval_arith (x * y) (f1, f2)`,
3461 STRIP_TAC THEN
3462 MP_TAC ((SPECL [`n1:num`; `e1:num`; `n2:num`; `e2:num`; `m1:num`; `r1:num`; `m2:num`; `r2:num`; `y:real`; `x:real`; `f1:real`; `f2:real`] o GEN_ALL o DISCH_ALL) FLOAT_INTERVAL_MUL_TF_FF) THEN
3463 ASM_REWRITE_TAC[REAL_MUL_SYM] THEN DISCH_THEN MATCH_MP_TAC THEN
3464 POP_ASSUM MP_TAC THEN REAL_ARITH_TAC);;
3465
3466 (* TT_TF *)
3467 let FLOAT_INTERVAL_MUL_TT_TF = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3468 `interval_arith x (float_num T n1 e1, float_num T n2 e2) /\
3469 interval_arith y (float_num T m1 r1, float_num F m2 r2) /\
3470 f1 <= float_num T n1 e1 * float_num F m2 r2 /\
3471 float_num T n1 e1 * float_num T m1 r1 <= f2
3472 ==> interval_arith (x * y) (f1, f2)`,
3473 STRIP_TAC THEN
3474 MP_TAC ((SPECL [`n1:num`; `e1:num`; `n2:num`; `e2:num`; `m1:num`; `r1:num`; `m2:num`; `r2:num`; `y:real`; `x:real`; `f1:real`; `f2:real`] o GEN_ALL o DISCH_ALL) FLOAT_INTERVAL_MUL_TF_TT) THEN
3475 ASM_REWRITE_TAC[REAL_MUL_SYM] THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN
3476 SIMP_TAC[REAL_MUL_SYM]);;
3477
3478 (* TF_TF *)
3479 let FLOAT_INTERVAL_MUL_TF_TF = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
3480 `interval_arith x (float_num T n1 e1, float_num F n2 e2) /\
3481 interval_arith y (float_num T m1 r1, float_num F m2 r2) /\
3482 f1_1 <= float_num T n1 e1 * float_num F m2 r2 /\
3483 f1_2 <= float_num F n2 e2 * float_num T m1 r1 /\
3484 min f1_1 f1_2 = f1 /\
3485 float_num T n1 e1 * float_num T m1 r1 <= f2_1 /\
3486 float_num F n2 e2 * float_num F m2 r2 <= f2_2 /\
3487 max f2_1 f2_2 = f2
3488 ==> interval_arith (x * y) (f1, f2)`,
3489 REWRITE_TAC[EQ_SYM_EQ; FLOAT_NEG_T] THEN
3490 REWRITE_TAC[interval_arith] THEN
3491 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3492 STRIP_TAC THEN
3493 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` ASSUME_TAC THENL
3494 [
3495 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN
3496 REWRITE_TAC[FLOAT_F_POS];
3497 ALL_TAC
3498 ] THEN
3499
3500 DISJ_CASES_TAC (REAL_ARITH `&0 <= x \/ &0 <= --x`) THENL
3501 [
3502 DISJ_CASES_TAC (REAL_ARITH `&0 <= y \/ &0 <= --y`) THENL
3503 [
3504 CONJ_TAC THENL
3505 [
3506 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3507 CONJ_TAC THENL
3508 [
3509 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `f1_1:real` THEN
3510 ASM_REWRITE_TAC[REAL_MIN_MIN] THEN
3511 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a * d` THEN
3512 ASM_REWRITE_TAC[REAL_ARITH `--a * d <= &0 <=> &0 <= a * d`] THEN
3513 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3514 ALL_TAC
3515 ] THEN
3516 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3517 ALL_TAC
3518 ] THEN
3519
3520 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b * d` THEN
3521 CONJ_TAC THENL
3522 [
3523 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[];
3524 ALL_TAC
3525 ] THEN
3526 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `f2_2:real` THEN
3527 ASM_REWRITE_TAC[REAL_MAX_MAX];
3528 ALL_TAC
3529 ] THEN
3530
3531 CONJ_TAC THENL
3532 [
3533 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `f1_2:real` THEN
3534 ASM_REWRITE_TAC[REAL_MIN_MIN] THEN
3535 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b * --c` THEN
3536 ONCE_REWRITE_TAC[REAL_ARITH `b * --c <= x * y <=> x * --y <= b * c`] THEN ASM_REWRITE_TAC[] THEN
3537 MATCH_MP_TAC REAL_LE_MUL2 THEN ONCE_REWRITE_TAC[REAL_ARITH `--y <= c <=> --c <= y`] THEN
3538 ASM_REWRITE_TAC[];
3539 ALL_TAC
3540 ] THEN
3541 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3542 CONJ_TAC THENL
3543 [
3544 REWRITE_TAC[REAL_ARITH `x * y <= &0 <=> &0 <= x * --y`] THEN
3545 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3546 ALL_TAC
3547 ] THEN
3548 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `f2_2:real` THEN
3549 ASM_REWRITE_TAC[REAL_MAX_MAX] THEN
3550 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b * d` THEN ASM_REWRITE_TAC[] THEN
3551 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3552 ALL_TAC
3553 ] THEN
3554
3555 DISJ_CASES_TAC (REAL_ARITH `&0 <= y \/ &0 <= --y`) THENL
3556 [
3557 CONJ_TAC THENL
3558 [
3559 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `f1_1:real` THEN
3560 ASM_REWRITE_TAC[REAL_MIN_MIN] THEN
3561 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a * d` THEN
3562 ASM_REWRITE_TAC[] THEN ONCE_REWRITE_TAC[REAL_ARITH `--a * d <= x * y <=> --x * y <= a * d`] THEN
3563 MATCH_MP_TAC REAL_LE_MUL2 THEN ONCE_REWRITE_TAC[REAL_ARITH `--x <= a <=> --a <= x`] THEN
3564 ASM_REWRITE_TAC[];
3565 ALL_TAC
3566 ] THEN
3567 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3568 CONJ_TAC THENL
3569 [
3570 REWRITE_TAC[REAL_ARITH `x * y <= &0 <=> &0 <= --x * y`] THEN
3571 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3572 ALL_TAC
3573 ] THEN
3574 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `f2_2:real` THEN
3575 ASM_REWRITE_TAC[REAL_MAX_MAX] THEN
3576 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b * d` THEN ASM_REWRITE_TAC[] THEN
3577 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3578 ALL_TAC
3579 ] THEN
3580
3581 CONJ_TAC THENL
3582 [
3583 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3584 CONJ_TAC THENL
3585 [
3586 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `f1_1:real` THEN
3587 ASM_REWRITE_TAC[REAL_MIN_MIN] THEN
3588 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a * d` THEN
3589 ASM_REWRITE_TAC[REAL_ARITH `--a * d <= &0 <=> &0 <= a * d`] THEN
3590 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3591 ALL_TAC
3592 ] THEN
3593 ONCE_REWRITE_TAC[GSYM REAL_NEG_MUL2] THEN
3594 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
3595 ALL_TAC
3596 ] THEN
3597
3598 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a * --c` THEN
3599 CONJ_TAC THENL
3600 [
3601 ONCE_REWRITE_TAC[GSYM REAL_NEG_MUL2] THEN REWRITE_TAC[REAL_NEG_NEG] THEN
3602 MATCH_MP_TAC REAL_LE_MUL2 THEN ONCE_REWRITE_TAC[REAL_ARITH `--x <= a <=> --a <= x`] THEN
3603 ASM_REWRITE_TAC[];
3604 ALL_TAC
3605 ] THEN
3606 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `f2_1:real` THEN
3607 ASM_REWRITE_TAC[REAL_MAX_MAX]);;
3608
3609
3610 (****************************)
3611 let float_interval_mul =
3612 let mul_ft_xx th1 x y n1 e1 n2 e2 =
3613 let th0 = INST[x, x_var_real; y, y_var_real;
3614 n1, n1_var_num; e1, e1_var_num;
3615 n2, n2_var_num; e2, e2_var_num] FLOAT_INTERVAL_MUL_FT_xx in
3616 MY_PROVE_HYP th1 th0 in
3617 let mul_xx_ft th2 x y m1 r1 m2 r2 =
3618 let th0 = INST[x, x_var_real; y, y_var_real;
3619 m1, m1_var_num; r1, r1_var_num;
3620 m2, m2_var_num; r2, r2_var_num] FLOAT_INTERVAL_MUL_xx_FT in
3621 MY_PROVE_HYP th2 th0 in
3622
3623 fun pp th1 th2 ->
3624 let x, l_lo, l_hi = dest_float_interval (concl th1) and
3625 y, r_lo, r_hi = dest_float_interval (concl th2) in
3626 let s1, n1, e1 = dest_float l_lo and
3627 s2, n2, e2 = dest_float l_hi and
3628 s3, m1, r1 = dest_float r_lo and
3629 s4, m2, r2 = dest_float r_hi in
3630
3631 (* Special case 1 *)
3632 if s1 <> s2 && s1 = "F" then
3633 mul_ft_xx th1 x y n1 e1 n2 e2
3634 else if s3 <> s4 && s3 = "F" then
3635 mul_xx_ft th2 x y m1 r1 m2 r2
3636 else
3637 (* Special case 2 *)
3638 if s1 <> s2 && s3 <> s4 then
3639 let lo1, lo2 = float_mul_lo pp l_lo r_hi, float_mul_lo pp l_hi r_lo and
3640 hi1, hi2 = float_mul_hi pp l_lo r_lo, float_mul_hi pp l_hi r_hi in
3641 let f1_1 = (lhand o concl) lo1 and
3642 f1_2 = (lhand o concl) lo2 and
3643 f2_1 = (rand o concl) hi1 and
3644 f2_2 = (rand o concl) hi2 in
3645 let min_th = float_min f1_1 f1_2 and
3646 max_th = float_max f2_1 f2_2 in
3647 let f1_tm = (rand o concl) min_th and
3648 f2_tm = (rand o concl) max_th in
3649 let th0 = INST[x, x_var_real; n1, n1_var_num; e1, e1_var_num;
3650 y, y_var_real; n2, n2_var_num; e2, e2_var_num;
3651 m1, m1_var_num; r1, r1_var_num;
3652 m2, m2_var_num; r2, r2_var_num;
3653 f1_tm, f1_var_real; f2_tm, f2_var_real;
3654 f1_1, f1_1_var; f1_2, f1_2_var;
3655 f2_1, f2_1_var; f2_2, f2_2_var] FLOAT_INTERVAL_MUL_TF_TF in
3656 (MY_PROVE_HYP min_th o MY_PROVE_HYP max_th o MY_PROVE_HYP lo1 o MY_PROVE_HYP lo2 o
3657 MY_PROVE_HYP hi1 o MY_PROVE_HYP hi2 o MY_PROVE_HYP th1 o MY_PROVE_HYP th2) th0
3658 else
3659 let lo_th, hi_th, th0 =
3660 if s1 <> s2 then
3661 if s3 = "F" then
3662 float_mul_lo pp l_lo r_hi, float_mul_hi pp l_hi r_hi, FLOAT_INTERVAL_MUL_TF_FF
3663 else
3664 float_mul_lo pp l_hi r_lo, float_mul_hi pp l_lo r_lo, FLOAT_INTERVAL_MUL_TF_TT
3665 else
3666 if s3 <> s4 then
3667 if s1 = "F" then
3668 float_mul_lo pp l_hi r_lo, float_mul_hi pp l_hi r_hi, FLOAT_INTERVAL_MUL_FF_TF
3669 else
3670 float_mul_lo pp l_lo r_hi, float_mul_hi pp l_lo r_lo, FLOAT_INTERVAL_MUL_TT_TF
3671 else
3672 if s1 = "F" then
3673 if s3 = "F" then
3674 float_mul_lo pp l_lo r_lo, float_mul_hi pp l_hi r_hi, FLOAT_INTERVAL_MUL_FF_FF
3675 else
3676 float_mul_lo pp l_hi r_lo, float_mul_hi pp l_lo r_hi, FLOAT_INTERVAL_MUL_FF_TT
3677 else
3678 if s3 = "F" then
3679 float_mul_lo pp l_lo r_hi, float_mul_hi pp l_hi r_lo, FLOAT_INTERVAL_MUL_TT_FF
3680 else
3681 float_mul_lo pp l_hi r_hi, float_mul_hi pp l_lo r_lo, FLOAT_INTERVAL_MUL_TT_TT in
3682
3683 let f1_tm = lhand(concl lo_th) and
3684 f2_tm = rand(concl hi_th) in
3685
3686 let th = INST[x, x_var_real; n1, n1_var_num; e1, e1_var_num;
3687 y, y_var_real; n2, n2_var_num; e2, e2_var_num;
3688 m1, m1_var_num; r1, r1_var_num;
3689 m2, m2_var_num; r2, r2_var_num;
3690 f1_tm, f1_var_real; f2_tm, f2_var_real] th0 in
3691 MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th (MY_PROVE_HYP th1 (MY_PROVE_HYP th2 th)));;
3692
3693
3694 (*************************************)
3695 (* float_interval_div *)
3696
3697 (* FT_xx *)
3698 let FLOAT_INTERVAL_DIV_FT_xx = prove(
3699 `interval_arith x (float_num F n1 e1, float_num T n2 e2)
3700 ==> interval_arith (x / y) (float_num F 0 min_exp, float_num F 0 min_exp)`,
3701 REWRITE_TAC[real_div] THEN DISCH_THEN (MP_TAC o MATCH_MP FLOAT_INTERVAL_FT_IMP_0) THEN
3702 SIMP_TAC[REAL_MUL_LZERO; interval_arith] THEN
3703 MP_TAC (GEN_ALL (SPECL [`s:bool`; `0`] FLOAT_EQ_0)) THEN SIMP_TAC[REAL_LE_REFL]);;
3704
3705 (* FF_FF *)
3706 let FLOAT_INTERVAL_DIV_FF_FF = prove(
3707 `~(m1 = 0) /\
3708 interval_arith x (float_num F n1 e1, float_num F n2 e2) /\
3709 interval_arith y (float_num F m1 r1, float_num F m2 r2) /\
3710 f1 <= float_num F n1 e1 / float_num F m2 r2 /\
3711 float_num F n2 e2 / float_num F m1 r1 <= f2
3712 ==> interval_arith (x / y) (f1, f2)`,
3713 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3714 REWRITE_TAC[real_div] THEN
3715 STRIP_TAC THEN
3716 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` MP_TAC THENL
3717 [
3718 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN
3719 REWRITE_TAC[FLOAT_F_POS];
3720 ALL_TAC
3721 ] THEN
3722 SUBGOAL_THEN `~(c = &0)` ASSUME_TAC THENL
3723 [
3724 EXPAND_TAC "c" THEN ASM_REWRITE_TAC[FLOAT_EQ_0];
3725 ALL_TAC
3726 ] THEN
3727 STRIP_TAC THEN
3728 SUBGOAL_THEN `~(d = &0)` MP_TAC THENL
3729 [
3730 MATCH_MP_TAC (REAL_ARITH `~(c = &0) /\ &0 <= c /\ c <= d ==> ~(d = &0)`) THEN
3731 ASM_REWRITE_TAC[] THEN
3732 UNDISCH_TAC `interval_arith y (c,d)` THEN
3733 REWRITE_TAC[interval_arith] THEN
3734 REAL_ARITH_TAC;
3735 ALL_TAC
3736 ] THEN
3737
3738 REPLICATE_TAC 10 (POP_ASSUM MP_TAC) THEN
3739 REPEAT (POP_ASSUM (fun th -> ALL_TAC)) THEN
3740 REWRITE_TAC[interval_arith] THEN
3741 REPEAT STRIP_TAC THENL
3742 [
3743 MATCH_MP_TAC REAL_LE_TRANS THEN
3744 EXISTS_TAC `a * inv d` THEN
3745 ASM_REWRITE_TAC[] THEN
3746 MATCH_MP_TAC REAL_LE_MUL2 THEN
3747 ASM_REWRITE_TAC[REAL_LE_INV_EQ] THEN
3748 MATCH_MP_TAC REAL_LE_INV2 THEN
3749 ASM_REWRITE_TAC[] THEN
3750 MATCH_MP_TAC REAL_LTE_TRANS THEN
3751 EXISTS_TAC `c:real` THEN
3752 ASM_REWRITE_TAC[REAL_ARITH `&0 < c <=> ~(c = &0) /\ &0 <= c`];
3753
3754 MATCH_MP_TAC REAL_LE_TRANS THEN
3755 EXISTS_TAC `b * inv c` THEN
3756 ASM_REWRITE_TAC[] THEN
3757 MATCH_MP_TAC REAL_LE_MUL2 THEN
3758 ASM_REWRITE_TAC[REAL_LE_INV_EQ] THEN
3759 REPEAT CONJ_TAC THENL
3760 [
3761 MATCH_MP_TAC REAL_LE_TRANS THEN
3762 EXISTS_TAC `a:real` THEN ASM_REWRITE_TAC[];
3763 MATCH_MP_TAC REAL_LE_TRANS THEN
3764 EXISTS_TAC `c:real` THEN ASM_REWRITE_TAC[];
3765 ALL_TAC
3766 ] THEN
3767 MATCH_MP_TAC REAL_LE_INV2 THEN
3768 ASM_REWRITE_TAC[REAL_ARITH `&0 < c <=> ~(c = &0) /\ &0 <= c`]
3769 ]);;
3770
3771 (* TT_TT *)
3772 let FLOAT_INTERVAL_DIV_TT_TT = prove(
3773 `~(m2 = 0) /\
3774 interval_arith x (float_num T n1 e1, float_num T n2 e2) /\
3775 interval_arith y (float_num T m1 r1, float_num T m2 r2) /\
3776 f1 <= float_num T n2 e2 / float_num T m1 r1 /\
3777 float_num T n1 e1 / float_num T m2 r2 <= f2
3778 ==> interval_arith (x / y) (f1,f2)`,
3779 REWRITE_TAC[FLOAT_NEG_T] THEN
3780 REWRITE_TAC[real_div; REAL_INV_NEG; REAL_NEG_MUL2] THEN
3781 GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV)[interval_arith] THEN
3782 REWRITE_TAC[REAL_ARITH `--a <= x /\ x <= --b <=> b <= --x /\ --x <= a`] THEN
3783 GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV)[GSYM interval_arith] THEN
3784 STRIP_TAC THEN
3785 MP_TAC ((SPECL[`n2:num`; `e2:num`; `m1:num`; `r1:num`; `n1:num`; `e1:num`; `m2:num`; `r2:num`; `--x`; `--y`] o GEN_ALL) FLOAT_INTERVAL_DIV_FF_FF) THEN
3786 REWRITE_TAC[real_div; REAL_INV_NEG; REAL_NEG_MUL2] THEN
3787 DISCH_THEN MATCH_MP_TAC THEN
3788 ASM_REWRITE_TAC[]);;
3789
3790 (* FF_TT *)
3791 let FLOAT_INTERVAL_DIV_FF_TT = prove(
3792 `~(m2 = 0) /\
3793 interval_arith x (float_num F n1 e1, float_num F n2 e2) /\
3794 interval_arith y (float_num T m1 r1, float_num T m2 r2) /\
3795 f1 <= float_num F n2 e2 / float_num T m2 r2 /\
3796 float_num F n1 e1 / float_num T m1 r1 <= f2
3797 ==> interval_arith (x / y) (f1,f2)`,
3798 REWRITE_TAC[FLOAT_NEG_T] THEN
3799 REWRITE_TAC[real_div; REAL_INV_NEG] THEN
3800 REWRITE_TAC[REAL_ARITH `a * --b <= c <=> --c <= a * b`] THEN
3801 REWRITE_TAC[REAL_ARITH `c <= a * --b <=> a * b <= --c`] THEN
3802 GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV)[interval_arith] THEN
3803 REWRITE_TAC[REAL_ARITH `--a <= x /\ x <= --b <=> b <= --x /\ --x <= a`] THEN
3804 GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV)[GSYM interval_arith] THEN
3805 STRIP_TAC THEN
3806 MP_TAC ((SPECL[`n1:num`; `e1:num`; `m1:num`; `r1:num`; `n2:num`; `e2:num`; `m2:num`; `r2:num`; `x:real`; `--y`; `--f2`; `--f1`] o GEN_ALL) FLOAT_INTERVAL_DIV_FF_FF) THEN
3807 ANTS_TAC THENL
3808 [
3809 ASM_REWRITE_TAC[real_div];
3810 ALL_TAC
3811 ] THEN
3812 REWRITE_TAC[real_div; REAL_INV_NEG; interval_arith] THEN
3813 REAL_ARITH_TAC);;
3814
3815 (* TT_FF *)
3816 let FLOAT_INTERVAL_DIV_TT_FF = prove(
3817 `~(m1 = 0) /\
3818 interval_arith x (float_num T n1 e1, float_num T n2 e2) /\
3819 interval_arith y (float_num F m1 r1, float_num F m2 r2) /\
3820 f1 <= float_num T n1 e1 / float_num F m1 r1 /\
3821 float_num T n2 e2 / float_num F m2 r2 <= f2
3822 ==> interval_arith (x / y) (f1,f2)`,
3823 REWRITE_TAC[FLOAT_NEG_T] THEN
3824 REWRITE_TAC[real_div; REAL_INV_NEG] THEN
3825 REWRITE_TAC[REAL_ARITH `--a * b <= c <=> --c <= a * b`] THEN
3826 REWRITE_TAC[REAL_ARITH `c <= --a * b <=> a * b <= --c`] THEN
3827 GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV)[interval_arith] THEN
3828 REWRITE_TAC[REAL_ARITH `--a <= x /\ x <= --b <=> b <= --x /\ --x <= a`] THEN
3829 GEN_REWRITE_TAC (LAND_CONV o DEPTH_CONV)[GSYM interval_arith] THEN
3830 STRIP_TAC THEN
3831 MP_TAC ((SPECL[`n2:num`; `e2:num`; `m2:num`; `r2:num`; `n1:num`; `e1:num`; `m1:num`; `r1:num`; `--x:real`; `y:real`; `--f2`; `--f1`] o GEN_ALL) FLOAT_INTERVAL_DIV_FF_FF) THEN
3832 ANTS_TAC THENL
3833 [
3834 ASM_REWRITE_TAC[real_div];
3835 ALL_TAC
3836 ] THEN
3837 REWRITE_TAC[real_div; REAL_INV_NEG; interval_arith] THEN
3838 REAL_ARITH_TAC);;
3839
3840
3841 (* TF_FF *)
3842 let FLOAT_INTERVAL_DIV_TF_FF = prove(
3843 `~(m1 = 0) /\
3844 interval_arith x (float_num T n1 e1, float_num F n2 e2) /\
3845 interval_arith y (float_num F m1 r1, float_num F m2 r2) /\
3846 f1 <= float_num T n1 e1 / float_num F m1 r1 /\
3847 float_num F n2 e2 / float_num F m1 r1 <= f2
3848 ==> interval_arith (x / y) (f1,f2)`,
3849 REWRITE_TAC[FLOAT_NEG_T] THEN STRIP_TAC THEN
3850 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3851 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` ASSUME_TAC THENL
3852 [
3853 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN REWRITE_TAC[FLOAT_F_POS];
3854 ALL_TAC
3855 ] THEN
3856
3857 DISJ_CASES_TAC (REAL_ARITH `&0 <= x \/ x <= &0`) THENL
3858 [
3859 SUBGOAL_THEN `interval_arith x (float_num F 0 0, b)` ASSUME_TAC THENL
3860 [
3861 UNDISCH_TAC `interval_arith x (--a, b)` THEN POP_ASSUM MP_TAC THEN
3862 REWRITE_TAC[interval_arith; FLOAT_0] THEN REAL_ARITH_TAC;
3863 ALL_TAC
3864 ] THEN
3865
3866 MP_TAC ((SPEC_ALL o SPECL [`0`; `0`] o GEN_ALL) FLOAT_INTERVAL_DIV_FF_FF) THEN
3867 ASM_REWRITE_TAC[] THEN DISCH_THEN MATCH_MP_TAC THEN
3868 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3869 REWRITE_TAC[real_div] THEN CONJ_TAC THENL
3870 [
3871 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a / c` THEN
3872 ASM_REWRITE_TAC[real_div; ARITH_RULE `--a * b <= &0 <=> &0 <= a * b`] THEN
3873 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[REAL_LE_INV_EQ];
3874 ALL_TAC
3875 ] THEN
3876
3877 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[REAL_LE_INV_EQ; FLOAT_F_POS];
3878 ALL_TAC
3879 ] THEN
3880
3881 SUBGOAL_THEN `interval_arith x (--a, float_num T 0 0)` ASSUME_TAC THENL
3882 [
3883 UNDISCH_TAC `interval_arith x (--a, b)` THEN POP_ASSUM MP_TAC THEN
3884 REWRITE_TAC[interval_arith; FLOAT_0] THEN REAL_ARITH_TAC;
3885 ALL_TAC
3886 ] THEN
3887
3888 MP_TAC ((INST[`0`, `n2:num`; `0`, `e2:num`]) FLOAT_INTERVAL_DIV_TT_FF) THEN
3889 ASM_REWRITE_TAC[FLOAT_NEG_T] THEN DISCH_THEN MATCH_MP_TAC THEN
3890 ASM_REWRITE_TAC[GSYM FLOAT_NEG_T] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3891 REWRITE_TAC[real_div] THEN CONJ_TAC THENL
3892 [
3893 REWRITE_TAC[FLOAT_0; REAL_MUL_LZERO; REAL_LE_REFL];
3894 ALL_TAC
3895 ] THEN
3896
3897 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b / c` THEN ASM_REWRITE_TAC[] THEN
3898 MATCH_MP_TAC REAL_LE_DIV THEN ASM_REWRITE_TAC[]);;
3899
3900 (* TF_TT *)
3901 let FLOAT_INTERVAL_DIV_TF_TT = prove(
3902 `~(m2 = 0) /\
3903 interval_arith x (float_num T n1 e1, float_num F n2 e2) /\
3904 interval_arith y (float_num T m1 r1, float_num T m2 r2) /\
3905 f1 <= float_num F n2 e2 / float_num T m2 r2 /\
3906 float_num T n1 e1 / float_num T m2 r2 <= f2
3907 ==> interval_arith (x / y) (f1,f2)`,
3908 REWRITE_TAC[FLOAT_NEG_T] THEN STRIP_TAC THEN
3909 MAP_EVERY ABBREV_TAC [`a = float_num F n1 e1`; `b = float_num F n2 e2`; `c = float_num F m1 r1`; `d = float_num F m2 r2`] THEN
3910 SUBGOAL_THEN `&0 <= a /\ &0 <= b /\ &0 <= c /\ &0 <= d` ASSUME_TAC THENL
3911 [
3912 MAP_EVERY EXPAND_TAC ["a"; "b"; "c"; "d"] THEN REWRITE_TAC[FLOAT_F_POS];
3913 ALL_TAC
3914 ] THEN
3915
3916 DISJ_CASES_TAC (REAL_ARITH `x <= &0 \/ &0 <= x`) THENL
3917 [
3918 SUBGOAL_THEN `interval_arith x (--a, float_num T 0 0)` ASSUME_TAC THENL
3919 [
3920 UNDISCH_TAC `interval_arith x (--a, b)` THEN POP_ASSUM MP_TAC THEN
3921 REWRITE_TAC[interval_arith; FLOAT_0] THEN REAL_ARITH_TAC;
3922 ALL_TAC
3923 ] THEN
3924
3925 MP_TAC ((SPEC_ALL o SPECL [`0`; `0`] o GEN_ALL) FLOAT_INTERVAL_DIV_TT_TT) THEN
3926 ASM_REWRITE_TAC[] THEN DISCH_THEN MATCH_MP_TAC THEN ASM_REWRITE_TAC[FLOAT_NEG_T] THEN
3927 ASM_REWRITE_TAC[GSYM FLOAT_NEG_T] THEN
3928 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3929 REWRITE_TAC[real_div] THEN CONJ_TAC THENL
3930 [
3931 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b / --d` THEN
3932 ASM_REWRITE_TAC[real_div; REAL_INV_NEG; REAL_ARITH `b * --d <= &0 <=> &0 <= b * d`] THEN
3933 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[REAL_LE_INV_EQ];
3934 ALL_TAC
3935 ] THEN
3936
3937 REWRITE_TAC[FLOAT_0; REAL_MUL_LZERO; REAL_LE_REFL];
3938 ALL_TAC
3939 ] THEN
3940
3941 SUBGOAL_THEN `interval_arith x (float_num F 0 0, b)` ASSUME_TAC THENL
3942 [
3943 UNDISCH_TAC `interval_arith x (--a, b)` THEN POP_ASSUM MP_TAC THEN
3944 REWRITE_TAC[interval_arith; FLOAT_0] THEN REAL_ARITH_TAC;
3945 ALL_TAC
3946 ] THEN
3947
3948 MP_TAC ((INST[`0`, `n1:num`; `0`, `e1:num`]) FLOAT_INTERVAL_DIV_FF_TT) THEN
3949 ASM_REWRITE_TAC[FLOAT_NEG_T] THEN DISCH_THEN MATCH_MP_TAC THEN
3950 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&0` THEN
3951 REWRITE_TAC[real_div] THEN CONJ_TAC THENL
3952 [
3953 REWRITE_TAC[FLOAT_0; REAL_MUL_LZERO; REAL_LE_REFL];
3954 ALL_TAC
3955 ] THEN
3956
3957 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--a / --d` THEN ASM_REWRITE_TAC[] THEN
3958 REWRITE_TAC[real_div; REAL_INV_NEG; REAL_NEG_MUL2] THEN MATCH_MP_TAC REAL_LE_MUL THEN
3959 ASM_REWRITE_TAC[REAL_LE_INV_EQ]);;
3960
3961 let transform = UNDISCH_ALL o
3962 PURE_REWRITE_RULE[TAUT `~P <=> (P <=> F)`] o
3963 NUMERALS_TO_NUM o
3964 REWRITE_RULE[GSYM IMP_IMP; min_exp_def];;
3965
3966 let FLOAT_INTERVAL_DIV_FT_xx' = transform FLOAT_INTERVAL_DIV_FT_xx and
3967 FLOAT_INTERVAL_DIV_FF_FF' = transform FLOAT_INTERVAL_DIV_FF_FF and
3968 FLOAT_INTERVAL_DIV_TT_TT' = transform FLOAT_INTERVAL_DIV_TT_TT and
3969 FLOAT_INTERVAL_DIV_FF_TT' = transform FLOAT_INTERVAL_DIV_FF_TT and
3970 FLOAT_INTERVAL_DIV_TT_FF' = transform FLOAT_INTERVAL_DIV_TT_FF and
3971 FLOAT_INTERVAL_DIV_TF_FF' = transform FLOAT_INTERVAL_DIV_TF_FF and
3972 FLOAT_INTERVAL_DIV_TF_TT' = transform FLOAT_INTERVAL_DIV_TF_TT;;
3973
3974
3975 let float_interval_div pp th1 th2 =
3976 let x, l_lo, l_hi = dest_float_interval (concl th1) and
3977 y, r_lo, r_hi = dest_float_interval (concl th2) in
3978 let s1, n1, e1 = dest_float l_lo and
3979 s2, n2, e2 = dest_float l_hi and
3980 s3, m1, r1 = dest_float r_lo and
3981 s4, m2, r2 = dest_float r_hi in
3982
3983 if s1 <> s2 && s1 = "F" then
3984 let th0 = INST[x, x_var_real; y, y_var_real;
3985 n1, n1_var_num; e1, e1_var_num;
3986 n2, n2_var_num; e2, e2_var_num] FLOAT_INTERVAL_DIV_FT_xx' in
3987 MY_PROVE_HYP th1 th0
3988 else if s3 <> s4 then
3989 failwith "float_interval_div: division by an interval containing 0"
3990 else
3991 let lo_th, hi_th, th0, zero_th =
3992 if s1 = s2 then
3993 if s1 = "F" then
3994 if s3 = "F" then
3995 float_div_lo pp l_lo r_hi, float_div_hi pp l_hi r_lo,
3996 FLOAT_INTERVAL_DIV_FF_FF', raw_eq0_hash_conv m1
3997 else
3998 float_div_lo pp l_hi r_hi, float_div_hi pp l_lo r_lo,
3999 FLOAT_INTERVAL_DIV_FF_TT', raw_eq0_hash_conv m2
4000 else
4001 if s3 = "F" then
4002 float_div_lo pp l_lo r_lo, float_div_hi pp l_hi r_hi,
4003 FLOAT_INTERVAL_DIV_TT_FF', raw_eq0_hash_conv m1
4004 else
4005 float_div_lo pp l_hi r_lo, float_div_hi pp l_lo r_hi,
4006 FLOAT_INTERVAL_DIV_TT_TT', raw_eq0_hash_conv m2
4007 else
4008 if s3 = "F" then
4009 float_div_lo pp l_lo r_lo, float_div_hi pp l_hi r_lo,
4010 FLOAT_INTERVAL_DIV_TF_FF', raw_eq0_hash_conv m1
4011 else
4012 float_div_lo pp l_hi r_hi, float_div_hi pp l_lo r_hi,
4013 FLOAT_INTERVAL_DIV_TF_TT', raw_eq0_hash_conv m2 in
4014
4015 let f1_tm = lhand(concl lo_th) and
4016 f2_tm = rand(concl hi_th) in
4017
4018 let th = INST[x, x_var_real; n1, n1_var_num; e1, e1_var_num;
4019 y, y_var_real; n2, n2_var_num; e2, e2_var_num;
4020 m1, m1_var_num; r1, r1_var_num;
4021 m2, m2_var_num; r2, r2_var_num;
4022 f1_tm, f1_var_real; f2_tm, f2_var_real] th0 in
4023 (MY_PROVE_HYP lo_th o MY_PROVE_HYP hi_th o
4024 MY_PROVE_HYP th1 o MY_PROVE_HYP th2 o MY_PROVE_HYP zero_th) th;;
4025
4026
4027 (*****************************************)
4028 (* float_interval_add, float_interval_sub *)
4029
4030 let n1_var_real = `n1:real` and
4031 n2_var_real = `n2:real` and
4032 m1_var_real = `m1:real` and
4033 m2_var_real = `m2:real` and
4034 n_var_real = `n:real` and
4035 m_var_real = `m:real`;;
4036
4037 let INTERVAL_ADD = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
4038 `interval_arith x (n1, m1) /\
4039 interval_arith y (n2, m2) /\
4040 n <= n1 + n2 /\ m1 + m2 <= m
4041 ==> interval_arith (x + y) (n, m)`,
4042 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);;
4043
4044 let INTERVAL_SUB = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove)(
4045 `interval_arith x (n1, m1) /\
4046 interval_arith y (n2, m2) /\
4047 n <= n1 - m2 /\ m1 - n2 <= m
4048 ==> interval_arith (x - y) (n, m)`,
4049 REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);;
4050
4051
4052 let float_interval_add pp th1 th2 =
4053 let x, n1, m1 = dest_float_interval (concl th1) in
4054 let y, n2, m2 = dest_float_interval (concl th2) in
4055 let lo_th = float_add_lo pp n1 n2 in
4056 let hi_th = float_add_hi pp m1 m2 in
4057 let n_tm = lhand (concl lo_th) in
4058 let m_tm = rand (concl hi_th) in
4059 let th0 = INST[x, x_var_real; n1, n1_var_real; m1, m1_var_real;
4060 y, y_var_real; n2, n2_var_real; m2, m2_var_real;
4061 n_tm, n_var_real; m_tm, m_var_real] INTERVAL_ADD in
4062 MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th (MY_PROVE_HYP th2 (MY_PROVE_HYP th1 th0)));;
4063
4064 let float_interval_sub pp th1 th2 =
4065 let x, n1, m1 = dest_float_interval (concl th1) in
4066 let y, n2, m2 = dest_float_interval (concl th2) in
4067 let lo_th = float_sub_lo pp n1 m2 in
4068 let hi_th = float_sub_hi pp m1 n2 in
4069 let n_tm = lhand(concl lo_th) in
4070 let m_tm = rand(concl hi_th) in
4071 let th0 = INST[x, x_var_real; n1, n1_var_real; m1, m1_var_real;
4072 y, y_var_real; n2, n2_var_real; m2, m2_var_real;
4073 n_tm, n_var_real; m_tm, m_var_real] INTERVAL_SUB in
4074 MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th (MY_PROVE_HYP th2 (MY_PROVE_HYP th1 th0)));;
4075
4076
4077 (********************************************)
4078 (* FLOAT_ABS *)
4079
4080 let s_var_bool = `s:bool`;;
4081
4082 let float_abs tm =
4083 let ltm, rtm = dest_comb tm in
4084 if ((fst o dest_const) ltm <> "real_abs") then
4085 failwith "float_abs: no abs"
4086 else
4087 let ltm, e_tm = dest_comb rtm in
4088 let ltm, n_tm = dest_comb ltm in
4089 let s_tm = rand ltm in
4090 INST[s_tm, s_var_bool; n_tm, n_var_num; e_tm, e_var_num] FLOAT_ABS;;
4091
4092
4093 (*******************************)
4094 (* float_interval_sqrt *)
4095
4096 let FLOAT_INTERVAL_SQRT = prove(`interval_arith x (float_num F n1 e1, hi) /\
4097 f1 <= sqrt (float_num F n1 e1) /\ sqrt hi <= f2
4098 ==> interval_arith (sqrt x) (f1, f2)`,
4099 ABBREV_TAC `lo = float_num F n1 e1` THEN
4100 REWRITE_TAC[interval_arith] THEN
4101 STRIP_TAC THEN
4102 SUBGOAL_THEN `&0 <= lo /\ &0 <= hi` ASSUME_TAC THENL
4103 [
4104 EXPAND_TAC "lo" THEN
4105 REWRITE_TAC[FLOAT_F_POS] THEN
4106 MATCH_MP_TAC REAL_LE_TRANS THEN
4107 EXISTS_TAC `x:real` THEN
4108 ASM_REWRITE_TAC[] THEN
4109 MATCH_MP_TAC REAL_LE_TRANS THEN
4110 EXISTS_TAC `lo:real` THEN
4111 ASM_REWRITE_TAC[] THEN
4112 EXPAND_TAC "lo" THEN
4113 REWRITE_TAC[FLOAT_F_POS];
4114 ALL_TAC
4115 ] THEN
4116 SUBGOAL_THEN `&0 <= x` ASSUME_TAC THENL
4117 [
4118 MATCH_MP_TAC REAL_LE_TRANS THEN
4119 EXISTS_TAC `lo:real` THEN
4120 ASM_REWRITE_TAC[];
4121 ALL_TAC
4122 ] THEN
4123 CONJ_TAC THENL
4124 [
4125 MATCH_MP_TAC REAL_LE_TRANS THEN
4126 EXISTS_TAC `sqrt lo` THEN
4127 ASM_REWRITE_TAC[SQRT_MONO_LE_EQ];
4128 MATCH_MP_TAC REAL_LE_TRANS THEN
4129 EXISTS_TAC `sqrt hi` THEN
4130 ASM_REWRITE_TAC[SQRT_MONO_LE_EQ]
4131 ]);;
4132
4133
4134 let FLOAT_INTERVAL_SQRT' = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP]) FLOAT_INTERVAL_SQRT;;
4135
4136 let float_interval_sqrt pp th =
4137 let x_tm, lo_tm, hi_tm = dest_float_interval (concl th) in
4138 let s1, n1_tm, e1_tm = dest_float lo_tm in
4139 if s1 <> "F" then
4140 failwith "float_interval_sqrt: negative low bound"
4141 else
4142 let lo_th = float_sqrt_lo pp lo_tm in
4143 let hi_th = float_sqrt_hi pp hi_tm in
4144 let f1_tm = lhand (concl lo_th) in
4145 let f2_tm = rand (concl hi_th) in
4146 let th0 = INST[x_tm, x_var_real; n1_tm, n1_var_num; e1_tm, e1_var_num;
4147 hi_tm, hi_var_real; f1_tm, f1_var_real;
4148 f2_tm, f2_var_real] FLOAT_INTERVAL_SQRT' in
4149 MY_PROVE_HYP lo_th (MY_PROVE_HYP hi_th (MY_PROVE_HYP th th0));;
4150
4151
4152 (******************************************)
4153 (* FLOAT_TO_NUM_CONV *)
4154
4155 let FLOAT_TO_NUM_CONV tm =
4156 let ltm, e_tm = dest_comb tm in
4157 let f_tm, n_tm = dest_comb ltm in
4158 if (fst o dest_const o rator) f_tm <> "float_num" then
4159 failwith "FLOAT_TO_NUM_CONV"
4160 else
4161 let n_th' = SYM (INST[n_tm, n_var_num] Arith_num.NUM_THM) in
4162 let e_th' = SYM (INST[e_tm, n_var_num] Arith_num.NUM_THM) in
4163 let n_th = TRANS n_th' (NUM_TO_NUMERAL_CONV (mk_comb(Arith_num.num_const, n_tm))) in
4164 let e_th = TRANS e_th' (NUM_TO_NUMERAL_CONV (mk_comb(Arith_num.num_const, e_tm))) in
4165 let th0 = MK_COMB (AP_TERM f_tm n_th, e_th) in
4166 let tm0 = rand(concl th0) in
4167 let th1 = (REWRITE_CONV[float_alt; arith_base_def; min_exp_def] THENC
4168 NUM_REDUCE_CONV THENC
4169 REAL_RAT_REDUCE_CONV) tm0 in
4170 TRANS th0 th1;;
4171
4172 end;;
4173
4174
4175 (**************************************)
4176 (* Printer for floating-point numbers *)
4177 (**************************************)
4178
4179 let print_float fmt tm =
4180 try
4181 let s, m_tm, e_tm = Arith_float.dest_float tm in
4182 let m = Arith_num.raw_dest_hash m_tm and
4183 e = Arith_num.raw_dest_hash e_tm -/ Num.num_of_int Float_theory.min_exp in
4184 let s_str = if s = "T" then "-" else "" in
4185 let m_str = Num.string_of_num m in
4186 let e_str = if e = num_0 then ""
4187 else "*" ^ string_of_int Arith_num.arith_base ^ "^" ^ Num.string_of_num e in
4188 let str = "##" ^ s_str ^ m_str ^ e_str in
4189 Format.pp_print_string fmt str
4190 with _ -> failwith "print_float";;
4191
4192 install_user_printer ("float_num", print_float);;