Debian Codegraph @

Formal_ineqs/informal/informal_exp.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2014 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* 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 *)