Debian Codegraph @

Formal_ineqs/informal/informal_sin_cos.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: sin, cos *)
11 (* -------------------------------------------------------------------------- *)
12
13 (* Dependencies *)
14 needs "Formal_ineqs/informal/informal_poly.hl";;
15 needs "Formal_ineqs/informal/informal_atn.hl";;
16
17 (* sin, cos *)
18 module type Informal_sin_cos_sig =
19 sig
20 val cos_interval : int -> Informal_interval.interval -> Informal_interval.interval
21 val sin_interval : int -> Informal_interval.interval -> Informal_interval.interval
22 end;;
23
24 module Informal_sin_cos : Informal_sin_cos_sig = struct
25
26 open Num;;
27 open Informal_float;;
28 open Informal_interval;;
29 open Informal_poly;;
30 open Informal_atn;;
31
32 let rec fact n =
33 if sign_num n <= 0 then Num.num_of_int 1 else
34 n */ fact (n -/ num_1);;
35
36 let one = mk_small_num_float 1 and
37 neg_one = neg_float (mk_small_num_float 1);;
38
39 let cos_tables pp n =
40 let t1 = map (fun i -> fact (Num.num_of_int (4 * i))) (0 -- (n / 2)) and
41 t2 = map (fun i -> fact (Num.num_of_int (4 * i + 2))) (0 -- ((n + 1) / 2 - 1)) in
42 let f n = inv_interval pp (mk_num_interval n) in
43 map f t1, map f t2;;
44
45 (* Computes x^k / k! *)
46 let rec x_pow_over_fact x k =
47 if k <= 0 then 1. else
48 x /. (float_of_int k) *. x_pow_over_fact x (k - 1);;
49
50 (* Computes i such that x^(2(i + 1))/(2(i + 1))! <= base^(-(p + 1)) and cond(i) *)
51 let n_of_p_cos x pp cond =
52 let t = (float_of_int Informal_nat.arith_base) ** (float_of_int (-pp - 1)) in
53 let rec try_i i =
54 let _ = if i > 50 then failwith "n_of_p_cos: cannot find i" else () in
55 if cond i then
56 let r = x_pow_over_fact x (2 * (i + 1)) in
57 if r <= t then i else try_i (i + 1)
58 else
59 try_i (i + 1)
60 in
61 try_i 0;;
62
63 let mk_cos_upper pp =
64 let n = n_of_p_cos (2.0 *. atan 1.0) pp (fun i -> i land 1 = 0) in
65 cos_tables (pp + 1) n;;
66
67 let mk_cos_lower pp =
68 let n = n_of_p_cos (2.0 *. atan 1.0) pp (fun i -> i land 1 = 1) in
69 cos_tables (pp + 1) n;;
70
71 let cos_high_raw =
72 let tables = Array.init 21 mk_cos_upper in
73 let one = mk_small_num_float 1 in
74 fun pp x ->
75 let cs1, cs2 = tables.(pp) in
76 let pp = pp + 1 in
77 let x4_high = eval_pow4_high pp x in
78 let m, x4_low = eval_pow2_pow4_low pp x in
79 let a = eval_high_poly_f_pos_pos pp cs1 x4_high in
80 let b = eval_low_poly_f_pos_pos pp cs2 x4_low in
81 let n = mul_float_lo pp m b in
82 let r = sub_float_hi pp a n in
83 if le_float r one then r else one;;
84
85 let cos_low_raw =
86 let tables = Array.init 21 mk_cos_lower in
87 let neg_one = neg_float (mk_small_num_float 1) in
88 fun pp x ->
89 let cs1, cs2 = tables.(pp) in
90 let pp = pp + 1 in
91 let m, x4_high = eval_pow2_pow4_high pp x in
92 let x4_low = eval_pow4_low pp x in
93 let a = eval_low_poly_f_pos_pos pp cs1 x4_low in
94 let b = eval_high_poly_f_pos_pos pp cs2 x4_high in
95 let n = mul_float_hi pp m b in
96 let r = sub_float_lo pp a n in
97 if le_float neg_one r then r else neg_one;;
98
99 (* 2 * pi *)
100 let two_pi_array =
101 let n = Array.length pi_approx_array in
102 let pi = pi_approx_array.(n - 1) in
103 let two_pi = mul_interval n (mk_small_num_interval 2) pi in
104 Array.init (n - 1) (fun i -> if i = 0 then zero_interval else round_interval i two_pi);;
105
106 (* (3 * pi) / 2 *)
107 let pi32_array =
108 let n = Array.length pi_approx_array in
109 let pi = pi_approx_array.(n - 1) in
110 let three = mk_small_num_interval 3 in
111 let two = mk_small_num_interval 2 in
112 let pi32 = div_interval n (mul_interval n three pi) two in
113 Array.init (n - 1) (fun i -> if i = 0 then zero_interval else round_interval i pi32);;
114
115 (* -pi *)
116 let neg_pi_array =
117 let n = Array.length pi_approx_array in
118 Array.init n (fun i -> neg_interval pi_approx_array.(i));;
119
120
121 (* ------------------------------ *)
122 (* Reduction procedures *)
123 (* ------------------------------ *)
124
125 let eval_high_0_pi pp x =
126 let pi2 = pi2_approx_array.(pp) in
127 if not (ge_interval x pi2) then
128 cos_high_raw pp x
129 else
130 let pi = pi_approx_array.(pp) in
131 let hi = snd (dest_interval pi) in
132 let t = sub_float_hi pp hi x in
133 if not (le_interval t pi) then
134 one
135 else
136 let r = cos_low_raw pp t in
137 neg_float r;;
138
139 let eval_low_0_pi pp x =
140 let pi2 = pi2_approx_array.(pp) in
141 if not (ge_interval x pi2) then
142 cos_low_raw pp x
143 else
144 let pi = pi_approx_array.(pp) in
145 let lo = fst (dest_interval pi) in
146 let t = sub_float_lo pp lo x in
147 if not (ge0_float t) then
148 neg_one
149 else
150 let r = cos_high_raw pp t in
151 neg_float r;;
152
153 let eval_high_neg_pi_0 pp x =
154 let y = neg_float x in
155 eval_high_0_pi pp y;;
156
157 let eval_low_neg_pi_0 pp x =
158 let y = neg_float x in
159 eval_low_0_pi pp y;;
160
161 let eval_high_pi_2pi pp x =
162 let pi32_lo = fst (dest_interval pi32_array.(pp)) in
163 if le_float x pi32_lo then
164 let pi = pi_approx_array.(pp) in
165 let lo = fst (dest_interval pi) in
166 let t = sub_float_hi pp x lo in
167 if not (le_interval t pi) then
168 one
169 else
170 let r = cos_low_raw pp t in
171 neg_float r
172 else
173 let two_pi = two_pi_array.(pp) in
174 let lo = fst (dest_interval two_pi) in
175 let t = sub_float_hi pp lo x in
176 if not (ge0_float t) then
177 one
178 else
179 cos_high_raw pp t;;
180
181 let eval_low_pi_2pi pp x =
182 let pi = pi_approx_array.(pp) in
183 let pi32_lo = fst (dest_interval pi32_array.(pp)) in
184 if le_float x pi32_lo then
185 let hi = snd (dest_interval pi) in
186 let t = sub_float_lo pp x hi in
187 if not (ge0_float t) then
188 neg_one
189 else
190 let r = cos_high_raw pp t in
191 neg_float r
192 else
193 let two_pi = two_pi_array.(pp) in
194 let hi = snd (dest_interval two_pi) in
195 let t = sub_float_hi pp hi x in
196 if not (le_interval t pi) then
197 neg_one
198 else
199 cos_low_raw pp t;;
200
201
202 (* ------------------------------ *)
203 (* Interval reduction *)
204 (* ------------------------------ *)
205
206 exception Correction_failed;;
207
208 let get_i =
209 let f_pi = 3.14159265358979323846 and
210 f_2_pi = 6.28318530717958647693 in
211 fun f ->
212 let x = float_of_ifloat f in
213 let k0 = -int_of_float (x /. f_2_pi) in
214 let y = x +. float_of_int k0 *. f_2_pi in
215 if y < -.f_pi then k0 + 1
216 else if y > f_pi then k0 - 1
217 else k0;;
218
219 let reduction_zero a b = a, b;;
220
221 let reduction_neg pp i a b =
222 let _ = assert (i < 0) in
223 let z = mk_small_num_float (-i) in
224 let lo, hi = dest_interval two_pi_array.(pp) in
225 let m = mul_float_hi pp z hi in
226 let n = mul_float_lo pp z lo in
227 let a1 = sub_float_lo pp a m in
228 let b1 = sub_float_hi pp b n in
229 a1, b1;;
230
231 let reduction_pos pp i a b =
232 let _ = assert (i >= 0) in
233 let z = mk_small_num_float i in
234 let lo, hi = dest_interval two_pi_array.(pp) in
235 let m = mul_float_lo pp z lo in
236 let n = mul_float_hi pp z hi in
237 let a1 = add_float_lo pp a m in
238 let b1 = add_float_hi pp b n in
239 a1, b1;;
240
241 let correct_neg_pi pp a1 b1 =
242 let lo, hi = dest_interval two_pi_array.(pp) in
243 let a2 = add_float_lo pp a1 lo in
244 let b2 = add_float_hi pp b1 hi in
245 a2, b2;;
246
247 let correct_pi pp a1 =
248 let pi = pi_approx_array.(pp) in
249 if le_interval a1 pi then
250 a1
251 else
252 fst (dest_interval pi);;
253
254 let correct_ab_sum pp a1 b1 =
255 let lo, hi = dest_interval two_pi_array.(pp) in
256 let n = add_float_hi pp a1 b1 in
257 if le_float n lo then
258 -1, b1
259 else
260 let m = add_float_lo pp a1 b1 in
261 if le_float hi m then
262 1, b1
263 else
264 let t = sub_float_hi pp hi lo in
265 let r = sub_float_hi pp n m in
266 let z = add_float_hi pp r t in
267 1, add_float_hi pp b1 z;;
268
269 (* ----------------------------------- *)
270 (* The main evaluation function *)
271 (* ----------------------------------- *)
272
273 let cos_interval pp x_int =
274 let a, b = dest_interval x_int in
275 try
276 (* Reduce the interval of x *)
277 let i = get_i a in
278 let a1, b1 =
279 if i = 0 then reduction_zero a b
280 else if i < 0 then reduction_neg pp i a b
281 else reduction_pos pp i a b in
282
283 (* Correct the value of a1 if a1 < -pi *)
284 let neg_pi = neg_pi_array.(pp) in
285 let a1, b1 =
286 if ge_interval a1 neg_pi then
287 a1, b1
288 else
289 let a1', b1' = correct_neg_pi pp a1 b1 in
290 if not (ge_interval a1' neg_pi) then
291 raise Correction_failed
292 else
293 a1', b1' in
294
295 (* Make sure that a1 <= pi *)
296 let a1 = correct_pi pp a1 in
297 let a1_case = if ge0_float a1 then 1 else -1 in
298 if a1_case > 0 then
299 (* a1 in [0, pi] *)
300 let ab_sum_case, b1 = correct_ab_sum pp a1 b1 in
301 let flag_b_pi = le_interval b1 pi_approx_array.(pp) in
302 let flag_b_2pi = le_interval b1 two_pi_array.(pp) in
303 if flag_b_pi then
304 (* b1 in [0, pi] *)
305 let low = eval_low_0_pi pp b1 and
306 high = eval_high_0_pi pp a1 in
307 mk_interval (low, high)
308 else if ab_sum_case < 0 then
309 (* a1 + b1 <= 2 * pi *)
310 let high = eval_high_0_pi pp a1 in
311 mk_interval (neg_one, high)
312 else if ab_sum_case > 0 && flag_b_2pi then
313 (* a1 + b1 >= 2 * pi /\ b1 <= 2 * pi *)
314 let high = eval_high_pi_2pi pp b1 in
315 mk_interval (neg_one, high)
316 else
317 mk_interval (neg_one, one)
318 else
319 (* a1 in [-pi, 0] *)
320 if le0_float b1 then
321 (* b1 <= 0 *)
322 let low = eval_low_neg_pi_0 pp a1 and
323 high = eval_high_neg_pi_0 pp b1 in
324 mk_interval (low, high)
325 else
326 (* b1 >= 0 *)
327 let b2 = neg_float b1 in
328 if le_float a1 b2 then
329 (* a1 <= -b1 *)
330 let low = eval_low_neg_pi_0 pp a1 in
331 mk_interval (low, one)
332 else
333 (* a1 >= -b1 *)
334 if le_interval b1 pi_approx_array.(pp) then
335 (* b1 <= pi *)
336 let low = eval_low_0_pi pp b1 in
337 mk_interval (low, one)
338 else
339 mk_interval (neg_one, one)
340 with Correction_failed ->
341 let _ = warn true (Printf.sprintf "cos_interval: reduction failed") in
342 mk_interval (neg_one, one);;
343
344 (* ---------------------------- *)
345 (* sin evaluation *)
346 (* ---------------------------- *)
347
348 let translate_pi2 pp x_int =
349 let a, b = dest_interval x_int in
350 let lo, hi = dest_interval pi2_approx_array.(pp) in
351 let a1 = sub_float_lo pp a hi in
352 let b1 = sub_float_hi pp b lo in
353 mk_interval (a1, b1);;
354
355 let sin_interval pp x_int =
356 let x_pi2 = translate_pi2 pp x_int in
357 cos_interval pp x_pi2;;
358
359 end;;
360
361
362 (*
363 (*****)
364
365 open Informal_float;;
366 open Informal_interval;;
367
368 let pp = 8;;
369
370 let n = -10000;;
371
372 let a = 3 and
373 b = 5;;
374
375 let x = mk_interval (mk_float (Num.num_of_int a) 0, mk_float (Num.num_of_int b) 0);;
376 let y = mk_interval (mk_float (Num.num_of_int (-a)) 0, mk_float (Num.num_of_int b) 0);;
377 let z = mk_interval (mk_float (Num.num_of_int (-b)) 0, mk_float (Num.num_of_int a) 0);;
378 let u = mk_interval (mk_float (Num.num_of_int (-3)) 0, mk_float (Num.num_of_int (-2)) 0);;
379
380 abs_interval x;;
381 abs_interval y;;
382 abs_interval z;;
383 abs_interval u;;
384
385 let x = mk_interval (mk_float (Num.num_of_int a) 0, mk_float (Num.num_of_int b) 0);;
386 let x_th = (ASSUME o Interval_arith.mk_interval `x:real` o mk_pair)
387 (More_float.mk_float a 0, More_float.mk_float b 0);;
388
389
390 Sin_eval.float_interval_sin pp x_th;;
391 sin_interval pp x;;
392
393 Sin_eval.float_interval_sin 10 Float_atn.pi_approx_array.(10);;
394 sin_interval 10 pi_approx_array.(10);;
395
396
397 Cos_bounds_eval.float_cos_high_raw pp x_tm;;
398 cos_high_raw pp x;;
399
400 Cos_bounds_eval.float_cos_low_raw pp x_tm;;
401 cos_low_raw pp x;;
402
403
404 let t1, t2 = cos_tables 3 3;;
405
406 #install_printer print_ifloat;;
407 #install_printer print_interval;;
408 t1;;
409 t2;;
410
411
412 let dest i =
413 let lo, hi = dest_interval i in
414 dest_float lo, dest_float hi;;
415
416 map dest t1;;
417 map dest t2;;
418 *)