Debian Codegraph @

Formal_ineqs/arith/float_theory.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 (* Theoretical results for 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/interval_arith.hl";;
17
18 module Float_theory = struct
19
20 open Num_exp_theory;;
21 open Arith_nat;;
22 open Interval_arith;;
23
24 (* Fix the minimal exponent *)
25 let min_exp = !Arith_options.min_exp;;
26
27 (* The main definition *)
28 let min_exp_num_const = rand (mk_small_numeral_array min_exp);;
29 let min_exp_const = mk_small_numeral min_exp;;
30
31 let min_exp_def = new_definition (mk_eq(`min_exp:num`, min_exp_const));;
32
33 let float_tm = `float_num s n e = (if s then (-- &1) else &1) * &(num_exp n e) / &(num_exp 1 min_exp)`;;
34 let float = new_definition float_tm;;
35
36 let arith_base_def = new_definition
37 (mk_eq (`arith_base:num`, mk_small_numeral Arith_num.arith_base));;
38
39 let arith_base_neq0 = prove
40 (`~(arith_base = 0)`,
41 REWRITE_TAC[arith_base_def] THEN ARITH_TAC);;
42
43 let float_alt = prove
44 (`!s n e. float_num s n e = (if s then -- &1 else &1) * &n *
45 if (min_exp <= e) then &arith_base pow (e - min_exp) else inv (&arith_base pow (min_exp - e))`,
46 REPEAT GEN_TAC THEN REWRITE_TAC[float; num_exp; GSYM arith_base_def] THEN
47 REWRITE_TAC[GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_POW; REAL_MUL_LID] THEN
48 REWRITE_TAC[REAL_ARITH `(&n * b) / c = &n * (b / c)`] THEN
49 SIMP_TAC[arith_base_neq0; REAL_OF_NUM_EQ; REAL_DIV_POW2]);;
50
51 let FLOAT_OF_NUM = (GEN_ALL o prove)(`&n = float_num F n min_exp`,
52 REWRITE_TAC[float; num_exp; REAL_MUL_LID] THEN
53 REWRITE_TAC[GSYM REAL_OF_NUM_MUL; REAL_MUL_LID; real_div] THEN
54 SUBGOAL_THEN (mk_comb(`(~)`, mk_eq(mk_comb(`&`, mk_binop `EXP` base_const `min_exp`), `&0`))) ASSUME_TAC THENL
55 [
56 REWRITE_TAC[REAL_OF_NUM_EQ; EXP_EQ_0] THEN ARITH_TAC;
57 ALL_TAC
58 ] THEN
59 ASM_SIMP_TAC[GSYM REAL_MUL_ASSOC; REAL_MUL_RINV; REAL_MUL_RID]);;
60
61 let FLOAT_NEG = prove(`!s n e. --float_num s n e = float_num (~s) n e`,
62 REWRITE_TAC[float] THEN REAL_ARITH_TAC);;
63
64 let FLOAT_NEG_F = (GSYM o REWRITE_RULE[] o SPEC `T`) FLOAT_NEG;;
65 let FLOAT_NEG_T = (GSYM o REWRITE_RULE[] o SPEC `F`) FLOAT_NEG;;
66
67 let FLOAT_F_POS = prove(`!n e. &0 <= float_num F n e`,
68 REPEAT GEN_TAC THEN REWRITE_TAC[float; REAL_MUL_LID; real_div] THEN
69 MATCH_MP_TAC REAL_LE_MUL THEN
70 REWRITE_TAC[REAL_POS; REAL_LE_INV_EQ]);;
71
72 let FLOAT_T_NEG = prove(`!n e. float_num T n e <= &0`,
73 REPEAT GEN_TAC THEN REWRITE_TAC[float; real_div] THEN
74 REWRITE_TAC[REAL_ARITH `-- &1 * a * b <= &0 <=> &0 <= a * b`] THEN
75 MATCH_MP_TAC REAL_LE_MUL THEN
76 REWRITE_TAC[REAL_POS; REAL_LE_INV_EQ]);;
77
78 let FLOAT_EQ_0 = prove(`!s n e. float_num s n e = &0 <=> n = 0`,
79 REPEAT GEN_TAC THEN REWRITE_TAC[float; real_div] THEN
80 REWRITE_TAC[REAL_ENTIRE] THEN
81 EQ_TAC THENL
82 [
83 STRIP_TAC THEN POP_ASSUM MP_TAC THENL
84 [
85 COND_CASES_TAC THEN REAL_ARITH_TAC;
86 REWRITE_TAC[REAL_OF_NUM_EQ; NUM_EXP_EQ_0];
87 REWRITE_TAC[REAL_INV_EQ_0; REAL_OF_NUM_EQ; NUM_EXP_EQ_0] THEN
88 ARITH_TAC
89 ];
90
91 DISCH_TAC THEN
92 DISJ2_TAC THEN DISJ1_TAC THEN
93 ASM_REWRITE_TAC[REAL_OF_NUM_EQ; NUM_EXP_EQ_0]
94 ]);;
95
96 let FLOAT_F_bound = (GEN_ALL o prove)(`num_exp n1 e1 <= num_exp n2 e2
97 ==> float_num F n1 e1 <= float_num F n2 e2`,
98 DISCH_TAC THEN
99 REWRITE_TAC[float; REAL_MUL_LID; real_div] THEN
100 MATCH_MP_TAC REAL_LE_RMUL THEN
101 ASM_REWRITE_TAC[REAL_OF_NUM_LE; REAL_LE_INV_EQ; REAL_POS]);;
102
103 let FLOAT_T_bound = (GEN_ALL o prove)(`num_exp n1 e1 <= num_exp n2 e2
104 ==> float_num T n2 e2 <= float_num T n1 e1`,
105 REWRITE_TAC[FLOAT_NEG_T; REAL_LE_NEG2; FLOAT_F_bound]);;
106
107
108 let FLOAT_INTERVAL_FT_IMP_0 = prove
109 (`interval_arith x (float_num F n1 e1, float_num T n2 e2) ==> x = &0`,
110 REWRITE_TAC[interval_arith] THEN STRIP_TAC THEN
111 REWRITE_TAC[GSYM REAL_LE_ANTISYM] THEN
112 CONJ_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THENL [
113 EXISTS_TAC `float_num T n2 e2` THEN ASM_REWRITE_TAC[FLOAT_T_NEG];
114 EXISTS_TAC `float_num F n1 e1` THEN ASM_REWRITE_TAC[FLOAT_F_POS]
115 ]);;
116
117 let FLOAT_0 = prove(`!s e. float_num s 0 e = &0`, REWRITE_TAC[FLOAT_EQ_0]);;
118
119 let FLOAT_ABS = prove(`abs (float_num s n e) = float_num F n e`,
120 BOOL_CASES_TAC `s:bool` THEN
121 REWRITE_TAC[FLOAT_NEG_T; REAL_ABS_NEG; REAL_ABS_REFL; FLOAT_F_POS]);;
122
123
124 end;;