Debian Codegraph @

Formal_ineqs/informal/informal_atn.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: atn *)
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_atn_sig =
18 sig
19 val atn_float_lo : int -> Informal_float.ifloat -> Informal_float.ifloat
20 val atn_float_hi : int -> Informal_float.ifloat -> Informal_float.ifloat
21 val atn_interval : int -> Informal_interval.interval -> Informal_interval.interval
22 val pi_approx_array : Informal_interval.interval array
23 val pi2_approx_array : Informal_interval.interval array
24 end;;
25
26
27 module Informal_atn : Informal_atn_sig = struct
28
29 open Num;;
30 open Informal_float;;
31 open Informal_interval;;
32 open Informal_poly;;
33
34 let halfatn_pos_hi pp t =
35 let a = mul_float_lo pp t t in
36 let b = add_float_lo pp float1 a in
37 let c = sqrt_float_lo pp b in
38 let x1 = add_float_lo pp c float1 in
39 let _ = assert (sign_float x1 = false) in
40 let hi = div_float_hi pp t x1 in
41 hi;;
42
43 let halfatn_pos_lo pp t =
44 let a = mul_float_hi pp t t in
45 let b = add_float_hi pp float1 a in
46 let c = sqrt_float_hi pp b in
47 let r = add_float_hi pp c float1 in
48 let lo = div_float_lo pp t r in
49 let _ = assert (sign_float lo = false) in
50 lo;;
51
52 let halfatn4_pos_hi pp t =
53 let _ = assert (sign_float t = false) in
54 let f = halfatn_pos_hi pp in
55 f (f (f (f t)));;
56
57 let halfatn4_pos_lo pp t =
58 let _ = assert (sign_float t = false) in
59 let f = halfatn_pos_lo pp in
60 f (f (f (f t)));;
61
62 let rec fact n =
63 if sign_num n <= 0 then Num.num_of_int 1 else
64 n */ fact (n -/ num_1);;
65
66 let atn_tables pp n =
67 let t1 = map (fun i -> 4 * i + 1) (0 -- (n / 2)) and
68 t2 = map (fun i -> 4 * i + 3) (0 -- ((n + 1) / 2 - 1)) in
69 let f n = if n = 1 then mk_num_interval (Num.num_of_int n) else inv_interval pp (mk_num_interval (Num.num_of_int n)) in
70 map f t1, map f t2;;
71
72 (* Computes x^k / k! *)
73 let rec x_pow_over_fact x k =
74 if k <= 0 then 1. else
75 x /. (float_of_int k) *. x_pow_over_fact x (k - 1);;
76
77 (* Computes i such that x^(2 * i + 1) / (2 * i + 1) <= base^(-(p + 1)) and cond(i) *)
78 let n_of_p_atn x pp cond =
79 let t = (float_of_int Informal_nat.arith_base) ** (float_of_int (-pp - 1)) in
80 let rec try_i i =
81 let _ = if i > 50 then failwith "n_of_p_atn: cannot find i" else () in
82 if cond i then
83 let d = float_of_int (2 * i + 1) in
84 let r = (x ** d) /. d in
85 if r <= t then i else try_i (i + 1)
86 else
87 try_i (i + 1)
88 in
89 try_i 0;;
90
91 let mk_atn_upper pp =
92 let n = n_of_p_atn 0.125 pp (fun i -> i land 1 = 0) in
93 atn_tables (pp + 1) n;;
94
95 let mk_atn_lower pp =
96 let n = n_of_p_atn 0.125 pp (fun i -> i land 1 = 1) in
97 atn_tables (pp + 1) n;;
98
99 let atn_float_pos_high =
100 let tables = Array.init 21 mk_atn_upper and
101 float16 = mk_float 16 0 in
102 fun pp x ->
103 let cs1, cs2 = tables.(pp) in
104 let pp = pp + 1 in
105 let t = halfatn4_pos_hi pp x in
106 let t4_high = eval_pow4_high pp t in
107 let m, t4_low = eval_pow2_pow4_low pp t in
108 let a = eval_high_poly_f_pos_pos pp cs1 t4_high in
109 let b = eval_low_poly_f_pos_pos pp cs2 t4_low in
110 let n = mul_float_lo pp m b in
111 let c = sub_float_hi pp a n in
112 let r = mul_float_hi pp t c in
113 let hi = mul_float_hi pp float16 r in
114 if not (lt_float t float1) then
115 failwith "Informal.atn_float_pos_high: t >= 1"
116 else
117 hi;;
118
119 let atn_float_pos_low =
120 let tables = Array.init 21 mk_atn_lower and
121 float16 = mk_float 16 0 in
122 fun pp x ->
123 let cs1, cs2 = tables.(pp) in
124 let pp = pp + 1 in
125 let t = halfatn4_pos_lo pp x in
126 let t4_low = eval_pow4_low pp t in
127 let m, t4_high = eval_pow2_pow4_high pp t in
128 let a = eval_low_poly_f_pos_pos pp cs1 t4_low in
129 let b = eval_high_poly_f_pos_pos pp cs2 t4_high in
130 let n = mul_float_hi pp m b in
131 let c = sub_float_lo pp a n in
132 let r = mul_float_lo pp t c in
133 let lo = mul_float_lo pp float16 r in
134 if sign_float lo then
135 float0
136 else
137 if not (lt_float t float1) then
138 failwith "Informal.atn_float_pos_low: t >= 1"
139 else
140 lo;;
141
142
143 let atn_float_hi pp x =
144 if not (sign_float x) then
145 atn_float_pos_high pp x
146 else
147 let lo = atn_float_pos_low pp (abs_float x) in
148 neg_float lo;;
149
150 let atn_float_lo pp x =
151 if not (sign_float x) then
152 atn_float_pos_low pp x
153 else
154 let hi = atn_float_pos_high pp (abs_float x) in
155 neg_float hi;;
156
157
158 let atn_interval pp i =
159 let a, b = dest_interval i in
160 let lo = atn_float_lo pp a and
161 hi = atn_float_hi pp b in
162 mk_interval (lo, hi);;
163
164
165 let pi_approx_array, pi2_approx_array =
166 let pp = 20 in
167 let x = one_interval in
168 let r1 = atn_interval pp x in
169 let r2 = mul_interval pp (mk_small_num_interval 4) r1 in
170 let float_pi = r2 in
171 let float_pi2 = div_interval pp float_pi two_interval in
172 let pi_int0 = mk_small_num_interval 0 in
173 let pi2_int0 = pi_int0 in
174 let pi = Array.init 19 (fun i -> if i = 0 then pi_int0 else round_interval i float_pi) and
175 pi2 = Array.init 19 (fun i -> if i = 0 then pi2_int0 else round_interval i float_pi2) in
176 pi, pi2;;
177
178 end;;
179
180 (******************)
181
182 (*
183
184 needs "Formal_ineqs/trig/atn_eval.hl";;
185
186 #install_printer print_ifloat;;
187 #install_printer print_interval;;
188
189 let x = mk_float 0 0 and
190 y = mk_float (-1) 0;;
191
192 let i1 = mk_interval (y, x) and
193 i2 = mk_interval (x, x) and
194 i3 = mk_interval (y, y);;
195
196 let x_tm, y_tm =
197 let mk = Arith_float.mk_float in
198 mk 0 0, mk (-1) 0;;
199
200 let i1_th, i2_th, i3_th =
201 let mk = (PURE_REWRITE_RULE[GSYM Float_theory.FLOAT_NEG_T] o More_float.RULE o ASSUME) in
202 mk `interval_arith y (-- &1, &0)`,
203 mk `interval_arith z (&0, &0)`,
204 mk `interval_arith u (-- &1, -- &1)`;;
205
206 let pp = 10;;
207
208 atn_float_pos_high pp x;;
209 atn_float_hi pp x;;
210 Atn_eval.float_atn_hi pp x_tm;;
211
212 atn_float_pos_low pp x;;
213 atn_float_lo pp x;;
214 Atn_eval.float_atn_lo pp x_tm;;
215
216 atn_float_hi pp y;;
217 Atn_eval.float_atn_hi pp y_tm;;
218
219 atn_float_lo pp y;;
220 Atn_eval.float_atn_lo pp y_tm;;
221
222 atn_interval pp i1;;
223 Atn_eval.float_interval_atn pp i1_th;;
224
225 atn_interval pp i2;;
226 Atn_eval.float_interval_atn pp i2_th;;
227
228 atn_interval pp i3;;
229 Atn_eval.float_interval_atn pp i3_th;;
230
231 pi_approx_array.(18);;
232 Atn_eval.pi_approx_array.(18);;
233
234 *)