| 1 |
(* ========================================================================== *) |
| 2 |
(* Formal verification of nonlinear inequalities in HOL Light *) |
| 3 |
(* *) |
| 4 |
(* Copyright (c) 2014 Alexey Solovyev *) |
| 5 |
(* *) |
| 6 |
(* This file is distributed under the terms of the MIT licence *) |
| 7 |
(* ========================================================================== *) |
| 8 |
|
| 9 |
(* -------------------------------------------------------------------------- *) |
| 10 |
(* Informal arithmetic procedures: exp *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
(* Dependencies *) |
| 14 |
needs "Formal_ineqs/informal/informal_interval.hl";; |
| 15 |
needs "Formal_ineqs/informal/informal_poly.hl";; |
| 16 |
|
| 17 |
module type Informal_exp_sig = |
| 18 |
sig |
| 19 |
val exp_float_lo : int -> Informal_float.ifloat -> Informal_float.ifloat |
| 20 |
val exp_float_hi : int -> Informal_float.ifloat -> Informal_float.ifloat |
| 21 |
val exp_interval : int -> Informal_interval.interval -> Informal_interval.interval |
| 22 |
end;; |
| 23 |
|
| 24 |
|
| 25 |
module Informal_exp : Informal_exp_sig = struct |
| 26 |
|
| 27 |
open Num;; |
| 28 |
open Informal_float;; |
| 29 |
open Informal_interval;; |
| 30 |
open Informal_poly;; |
| 31 |
|
| 32 |
(* TODO: Make sure that this constant is the same as in trig/exp_eval.hl *) |
| 33 |
let exp_max_x = 1.0;; |
| 34 |
let num_1 = Num.num_of_int 1;; |
| 35 |
|
| 36 |
let rec fact n = |
| 37 |
if sign_num n <= 0 then Num.num_of_int 1 else |
| 38 |
n */ fact (n -/ num_1);; |
| 39 |
|
| 40 |
let exp_pos_tables pp n = |
| 41 |
let t1 = map (fun i -> fact (Num.num_of_int i)) (0 -- n) in |
| 42 |
let f n = inv_interval pp (mk_num_interval n) in |
| 43 |
map f t1;; |
| 44 |
|
| 45 |
let exp_neg_tables pp n = |
| 46 |
let t1 = map (fun i -> fact (Num.num_of_int (2 * i))) (0 -- (n / 2)) and |
| 47 |
t2 = map (fun i -> fact (Num.num_of_int (2 * i + 1))) (0 -- ((n + 1) / 2 - 1)) in |
| 48 |
let f n = inv_interval pp (mk_num_interval n) in |
| 49 |
map f t1, map f t2;; |
| 50 |
|
| 51 |
(* Computes x^k / k! *) |
| 52 |
let rec x_pow_over_fact x k = |
| 53 |
if k <= 0 then 1. else |
| 54 |
x /. (float_of_int k) *. x_pow_over_fact x (k - 1);; |
| 55 |
|
| 56 |
(* Computes i such that x^i / i! <= base^(-(p + 1)) and cond(i) *) |
| 57 |
let n_of_p_exp x pp cond = |
| 58 |
let t = (float_of_int Informal_nat.arith_base) ** (float_of_int (-pp - 1)) in |
| 59 |
let rec try_i i = |
| 60 |
let _ = if i > 50 then failwith "n_of_p_exp: cannot find i" else () in |
| 61 |
if cond i then |
| 62 |
let r = x_pow_over_fact x i in |
| 63 |
if r <= t then i else try_i (i + 1) |
| 64 |
else |
| 65 |
try_i (i + 1) |
| 66 |
in |
| 67 |
try_i 0;; |
| 68 |
|
| 69 |
let mk_exp_pos_lower pp = |
| 70 |
let n = n_of_p_exp exp_max_x pp (fun i -> true) in |
| 71 |
exp_pos_tables (pp + 1) n;; |
| 72 |
|
| 73 |
let mk_exp_neg_lower pp = |
| 74 |
let n = n_of_p_exp exp_max_x pp (fun i -> i land 1 = 1) in |
| 75 |
exp_neg_tables (pp + 1) n;; |
| 76 |
|
| 77 |
let mk_exp_neg_upper pp = |
| 78 |
let n = n_of_p_exp exp_max_x pp (fun i -> i land 1 = 0) in |
| 79 |
exp_neg_tables (pp + 1) n;; |
| 80 |
|
| 81 |
let exp_pos_low_raw = |
| 82 |
let table = Array.init 21 mk_exp_pos_lower in |
| 83 |
fun pp x -> |
| 84 |
let cs1 = table.(pp) in |
| 85 |
let pp = pp + 1 in |
| 86 |
if not (ge0_float x) then |
| 87 |
failwith "Informal.exp_pos_low_raw: x < 0" |
| 88 |
else |
| 89 |
let r = eval_low_poly_f_pos_pos pp cs1 x in |
| 90 |
r;; |
| 91 |
|
| 92 |
let exp_neg_low_raw = |
| 93 |
let table = Array.init 21 mk_exp_neg_lower in |
| 94 |
fun pp x -> |
| 95 |
let cs1, cs2 = table.(pp) in |
| 96 |
let pp = pp + 1 in |
| 97 |
let x2_high = eval_pow2_high pp x and |
| 98 |
x2_low = eval_pow2_low pp x in |
| 99 |
let a = eval_low_poly_f_pos_pos pp cs1 x2_low and |
| 100 |
b = eval_high_poly_f_pos_pos pp cs2 x2_high in |
| 101 |
let n = mul_float_hi pp x b in |
| 102 |
let r = sub_float_lo pp a n in |
| 103 |
if le_float x float1 && ge0_float x then |
| 104 |
r |
| 105 |
else |
| 106 |
failwith "Informal.exp_neg_low_raw: bad x";; |
| 107 |
|
| 108 |
let exp_neg_high_raw = |
| 109 |
let table = Array.init 21 mk_exp_neg_upper in |
| 110 |
fun pp x -> |
| 111 |
let cs1, cs2 = table.(pp) in |
| 112 |
let pp = pp + 1 in |
| 113 |
let x2_high = eval_pow2_high pp x and |
| 114 |
x2_low = eval_pow2_low pp x in |
| 115 |
let a = eval_high_poly_f_pos_pos pp cs1 x2_high and |
| 116 |
b = eval_low_poly_f_pos_pos pp cs2 x2_low in |
| 117 |
let n = mul_float_lo pp x b in |
| 118 |
let r = sub_float_hi pp a n in |
| 119 |
if le_float x float1 && ge0_float x then |
| 120 |
r |
| 121 |
else |
| 122 |
failwith "Informal.exp_neg_high_raw: bad x";; |
| 123 |
|
| 124 |
let exp_low_raw pp x = |
| 125 |
let s = sign_float x in |
| 126 |
if not s then |
| 127 |
exp_pos_low_raw pp x |
| 128 |
else |
| 129 |
exp_neg_low_raw pp (abs_float x);; |
| 130 |
|
| 131 |
let exp_high_raw pp x = |
| 132 |
let s = sign_float x in |
| 133 |
if not s then |
| 134 |
let t = exp_neg_low_raw pp x in |
| 135 |
inv_float_hi pp t |
| 136 |
else |
| 137 |
exp_neg_high_raw pp (abs_float x);; |
| 138 |
|
| 139 |
let reduce_float x = |
| 140 |
let f = float_fabs (float_of_ifloat x) in |
| 141 |
if f <= exp_max_x then |
| 142 |
false, 0 |
| 143 |
else |
| 144 |
let k = int_of_float (floor (f /. exp_max_x)) + 1 in |
| 145 |
true, k;; |
| 146 |
|
| 147 |
let exp_float_hi pp x = |
| 148 |
let flag, k = reduce_float x in |
| 149 |
if not flag then |
| 150 |
exp_high_raw pp x |
| 151 |
else |
| 152 |
let t = mk_float k 0 in |
| 153 |
let y = div_float_hi (pp + 1) x t in |
| 154 |
let hi = exp_high_raw (pp + 1) y in |
| 155 |
pow_float_hi pp k hi;; |
| 156 |
|
| 157 |
let exp_float_lo pp x = |
| 158 |
let flag, k = reduce_float x in |
| 159 |
if not flag then |
| 160 |
exp_low_raw pp x |
| 161 |
else |
| 162 |
let t = mk_float k 0 in |
| 163 |
let y = div_float_lo (pp + 1) x t in |
| 164 |
let lo = exp_low_raw (pp + 1) y in |
| 165 |
if ge0_float lo then |
| 166 |
pow_float_lo pp k lo |
| 167 |
else |
| 168 |
failwith "Informal.exp_float_lo: lo < 0";; |
| 169 |
|
| 170 |
let exp_interval pp i = |
| 171 |
let a, b = dest_interval i in |
| 172 |
let lo = exp_float_lo pp a and |
| 173 |
hi = exp_float_hi pp b in |
| 174 |
mk_interval (lo, hi);; |
| 175 |
|
| 176 |
end;; |
| 177 |
|
| 178 |
(******************) |
| 179 |
|
| 180 |
(* |
| 181 |
|
| 182 |
needs "Formal_ineqs/trig/exp_eval.hl";; |
| 183 |
|
| 184 |
open Informal_float;; |
| 185 |
open Informal_interval;; |
| 186 |
open Informal_poly;; |
| 187 |
open Informal_exp;; |
| 188 |
|
| 189 |
#install_printer print_ifloat;; |
| 190 |
#install_printer print_interval;; |
| 191 |
|
| 192 |
let x = mk_float 1 0 and |
| 193 |
y = mk_float (-1) 0 and |
| 194 |
z = mk_float 2345 (-1) and |
| 195 |
r = mk_float 100 0;; |
| 196 |
|
| 197 |
let i1 = mk_interval (y, x) and |
| 198 |
i2 = mk_interval (x, x) and |
| 199 |
i3 = mk_interval (y, y) and |
| 200 |
i4 = mk_interval (z, z);; |
| 201 |
|
| 202 |
let x_tm, y_tm, z_tm, r_tm = |
| 203 |
let mk = Arith_float.mk_float in |
| 204 |
mk 1 0, mk (-1) 0, mk 2345 (-1), mk 100 0;; |
| 205 |
|
| 206 |
let i1_th, i2_th, i3_th = |
| 207 |
let mk = (PURE_REWRITE_RULE[GSYM Float_theory.FLOAT_NEG_T] o More_float.RULE o ASSUME) in |
| 208 |
mk `interval_arith y (-- &1, &1)`, |
| 209 |
mk `interval_arith z (&1, &1)`, |
| 210 |
mk `interval_arith u (-- &1, -- &1)`;; |
| 211 |
|
| 212 |
|
| 213 |
let pp = 10;; |
| 214 |
|
| 215 |
exp_float_hi pp x;; |
| 216 |
Exp_eval.float_exp_hi pp x_tm;; |
| 217 |
|
| 218 |
exp_float_lo pp x;; |
| 219 |
Exp_eval.float_exp_lo pp x_tm;; |
| 220 |
|
| 221 |
exp_float_hi pp y;; |
| 222 |
Exp_eval.float_exp_hi pp y_tm;; |
| 223 |
|
| 224 |
exp_float_lo pp y;; |
| 225 |
Exp_eval.float_exp_lo pp y_tm;; |
| 226 |
|
| 227 |
exp_float_hi pp z;; |
| 228 |
Exp_eval.float_exp_hi pp z_tm;; |
| 229 |
|
| 230 |
exp_float_lo pp z;; |
| 231 |
Exp_eval.float_exp_lo pp z_tm;; |
| 232 |
|
| 233 |
exp_float_hi pp r;; |
| 234 |
Exp_eval.float_exp_hi pp r_tm;; |
| 235 |
|
| 236 |
exp_float_lo pp r;; |
| 237 |
Exp_eval.float_exp_lo pp r_tm;; |
| 238 |
|
| 239 |
exp_interval pp i1;; |
| 240 |
Exp_eval.float_interval_exp pp i1_th;; |
| 241 |
|
| 242 |
exp_interval pp i2;; |
| 243 |
Exp_eval.float_interval_exp pp i2_th;; |
| 244 |
|
| 245 |
exp_interval pp i3;; |
| 246 |
Exp_eval.float_interval_exp pp i3_th;; |
| 247 |
|
| 248 |
*) |