| 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;; |