Debian Codegraph @

Formal_ineqs/informal/informal_float.hl

raw
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 (* Informal arithmetic procedures: floating-point numbers *)
11 (* -------------------------------------------------------------------------- *)
12
13 (* Dependencies *)
14 needs "Formal_ineqs/informal/informal_nat.hl";;
15
16 (* Floating-point numbers *)
17
18 module type Informal_float_sig =
19 sig
20 type ifloat
21 val min_exp : int
22 val print_ifloat_fmt : Format.formatter -> ifloat -> unit
23 val print_ifloat : ifloat -> unit
24 val mk_float : int -> int -> ifloat
25 val mk_num_float : Num.num -> ifloat
26 val mk_small_num_float : int -> ifloat
27 val float0 : ifloat
28 val float1 : ifloat
29 val float2 : ifloat
30 val float3 : ifloat
31 val float4 : ifloat
32 val dest_float : ifloat -> bool * Num.num * int
33 val make_float : bool -> Num.num -> int -> ifloat
34 val num_of_ifloat : ifloat -> Num.num
35 val float_of_ifloat : ifloat -> float
36 val ifloat_of_float : int -> float -> ifloat
37 val sign_float : ifloat -> bool
38 (* Compares representations, not numbers themselves *)
39 val eq_float : ifloat -> ifloat -> bool
40 val lo_float : int -> ifloat -> ifloat
41 val hi_float : int -> ifloat -> ifloat
42 val neg_float : ifloat -> ifloat
43 val abs_float : ifloat -> ifloat
44 val lt0_float : ifloat -> bool
45 val gt0_float : ifloat -> bool
46 val le0_float : ifloat -> bool
47 val ge0_float : ifloat -> bool
48 val lt_float : ifloat -> ifloat -> bool
49 val le_float : ifloat -> ifloat -> bool
50 val min_float : ifloat -> ifloat -> ifloat
51 val max_float : ifloat -> ifloat -> ifloat
52 val inv_float_lo : int -> ifloat -> ifloat
53 val inv_float_hi : int -> ifloat -> ifloat
54 val mul_float_eq : ifloat -> ifloat -> ifloat
55 val mul_float_lo : int -> ifloat -> ifloat -> ifloat
56 val mul_float_hi : int -> ifloat -> ifloat -> ifloat
57 val div_float_lo : int -> ifloat -> ifloat -> ifloat
58 val div_float_hi : int -> ifloat -> ifloat -> ifloat
59 val add_float_lo : int -> ifloat -> ifloat -> ifloat
60 val add_float_hi : int -> ifloat -> ifloat -> ifloat
61 val sub_float_lo : int -> ifloat -> ifloat -> ifloat
62 val sub_float_hi : int -> ifloat -> ifloat -> ifloat
63 val pow_float_lo : int -> int -> ifloat -> ifloat
64 val pow_float_hi : int -> int -> ifloat -> ifloat
65 val sqrt_float_lo : int -> ifloat -> ifloat
66 val sqrt_float_hi : int -> ifloat -> ifloat
67 end;;
68
69 module Informal_float : Informal_float_sig = struct
70
71 open Num;;
72 open Informal_nat;;
73
74 type ifloat = bool * nat * int;;
75
76 let min_exp = !Arith_options.min_exp;;
77
78 let print_ifloat_fmt fmt (s, n, e) =
79 let k = e - min_exp in
80 let n_str = string_of_num (dest_nat n) in
81 let s_str = if s then "-" else "" in
82 let str =
83 if k = 0 then
84 Printf.sprintf "%s%s" s_str n_str
85 else
86 Printf.sprintf "%s%s*%d^%d" s_str n_str arith_base k in
87 Format.pp_print_string fmt str;;
88
89 let print_ifloat = print_ifloat_fmt Format.std_formatter;;
90
91
92 (* Creates a floating-point value *)
93 let mk_float n e : ifloat =
94 if n < 0 then
95 true, mk_nat (minus_num (Num.num_of_int n)), e + min_exp
96 else
97 false, mk_nat (Num.num_of_int n), e + min_exp;;
98
99 let mk_num_float n = false, mk_nat n, min_exp;;
100
101 let mk_small_num_float n = false, mk_small_nat n, min_exp;;
102
103 let float0 = mk_small_num_float 0 and
104 float1 = mk_small_num_float 1 and
105 float2 = mk_small_num_float 2 and
106 float3 = mk_small_num_float 3 and
107 float4 = mk_small_num_float 4;;
108
109 let dest_float ((s, n, e) : ifloat) = s, dest_nat n, e;;
110
111 let make_float s n e : ifloat = s, mk_nat n, e;;
112
113 let num_of_ifloat =
114 let b = num_of_int arith_base in
115 fun ((s, n, e) : ifloat) ->
116 let r = (dest_nat n) */ (b **/ Num.num_of_int (e - min_exp)) in
117 if s then minus_num r else r;;
118
119 let float_of_ifloat f =
120 let n = num_of_ifloat f in
121 Num.float_of_num n;;
122
123 let ifloat_of_float =
124 let split =
125 let b = float_of_int arith_base in
126 let log_b = log b in
127 let rec fix t k =
128 if t = 0.0 || t = infinity || t = nan then
129 t, k
130 else if t < 1.0 then
131 fix (t *. b) (k - 1)
132 else if t >= b then
133 fix (t /. b) (k + 1)
134 else
135 t, k in
136 fun f ->
137 if f = 0.0 then
138 false, f, 0
139 else
140 let s, x = if f < 0.0 then true, -.f else false, f in
141 let e = -.floor (log x /. log_b) in
142 let k = -int_of_float e in
143 let t, n = fix (x *. (b ** e)) k in
144 s, t, n
145 and extract =
146 let b = float_of_int arith_base in
147 let nb = Num.num_of_int arith_base in
148 let rec step k f acc =
149 if k <= 0 then acc
150 else
151 let d = int_of_float f in
152 step (k - 1) ((f -. float_of_int d) *. b) (Num.num_of_int d +/ (nb */ acc)) in
153 fun pp f ->
154 step pp f (Num.num_of_int 0)
155 in
156 fun pp f ->
157 let s, x, k = split f in
158 let n = extract pp x in
159 make_float s n (min_exp + k - pp + 1);;
160
161 let sign_float ((s,_,_) : ifloat) = s;;
162
163 let eq_float (s1,n1,e1) (s2,n2,e2) = s1 = s2 && eq_nat n1 n2 && e1 = e2;;
164
165 let lo_float pp (s,n,e) =
166 let n1, e1 = if s then hi_nat pp n else lo_nat pp n in
167 (s, n1, e + e1);;
168
169 let hi_float pp (s,n,e) =
170 let n1, e1 = if s then lo_nat pp n else hi_nat pp n in
171 (s, n1, e + e1);;
172
173 (* Auxiliary num_exp functions *)
174
175 let num_exp_add =
176 let (+) = add_nat in
177 fun (n1,e1) (n2,e2) ->
178 if e1 <= e2 then
179 n1 + denormalize_nat (n2, e2 - e1), e1
180 else
181 n2 + denormalize_nat (n1, e1 - e2), e2;;
182
183
184 (* Returns (n,e),true if (n1,e1) >= (n2,e2) and (n,e) = (n1,e1) - (n2,e2)
185 Returns (n,e),false if (n1,e1) <= (n2,e2) and (n,e) = (n2,e2) - (n1,e1) *)
186 let num_exp_sub =
187 let (--) = sub_and_le_nat in
188 fun (n1,e1) (n2,e2) ->
189 if e2 <= e1 then
190 let a = denormalize_nat (n1, e1 - e2) and
191 b = n2 in
192 let sub, flag = a -- b in
193 (sub, e2), flag
194 else
195 let a = n1 and
196 b = denormalize_nat (n2, e2 - e1) in
197 let sub, flag = a -- b in
198 (sub, e1), flag;;
199
200
201 let num_exp_le =
202 let (<=/) = le_nat in
203 fun (n1,e1) (n2,e2) ->
204 if e1 <= e2 then
205 n1 <=/ denormalize_nat (n2, e2 - e1)
206 else
207 denormalize_nat (n1, e1 - e2) <=/ n2;;
208
209
210 let num_exp_lt =
211 let (</) = lt_nat in
212 fun (n1,e1) (n2,e2) ->
213 if e1 <= e2 then
214 n1 </ denormalize_nat (n2, e2 - e1)
215 else
216 denormalize_nat (n1, e1 - e2) </ n2;;
217
218
219
220 (* neg *)
221
222 let neg_float (s,n,e) = (not s, n, e);;
223
224
225 (* abs *)
226
227 let abs_float (_,n,e) = (false, n, e);;
228
229
230
231 (* lt0, gt0 *)
232
233 let lt0_float (s,n,e) =
234 if not s then false else gt0_nat n;;
235
236 let gt0_float (s,n,e) =
237 if s then false else gt0_nat n;;
238
239
240 (* le0, ge0 *)
241
242 let le0_float (s,n,e) =
243 if s then true else eq0_nat n;;
244
245 let ge0_float (s,n,e) =
246 if s then eq0_nat n else true;;
247
248
249 (* lt *)
250
251 let lt_float (s1,n1,e1) (s2,n2,e2) =
252 if not s1 then
253 if s2 then false else num_exp_lt (n1,e1) (n2,e2)
254 else
255 if s2 then num_exp_lt (n2,e2) (n1,e1)
256 else
257 (* TF *)
258 if eq0_nat n1 then gt0_nat n2 else true;;
259
260
261 let le_float (s1,n1,e1) (s2,n2,e2) =
262 if s1 then
263 if s2 then num_exp_le (n2,e2) (n1,e1) else true
264 else
265 if not s2 then num_exp_le (n1,e1) (n2,e2)
266 else
267 (* FT *)
268 if eq0_nat n2 then eq0_nat n1 else false;;
269
270
271
272 (* min, max *)
273
274 let min_float f1 f2 =
275 if le_float f1 f2 then f1 else f2;;
276
277 let max_float f1 f2 =
278 if le_float f1 f2 then f2 else f1;;
279
280
281 (* mul *)
282
283 let badd b1 b2 =
284 if b1 then not b2 else b2;;
285
286
287 let mul_float_eq (s1,n1,e1) (s2,n2,e2) =
288 let s = badd s1 s2 in
289 let n = mul_nat n1 n2 in
290 let e = e1 + e2 - min_exp in
291 if e < 0 then
292 failwith "mul_float_eq: underflow"
293 else
294 (s, n, e);;
295
296
297 let mul_float_lo pp (s1,n1,e1) (s2,n2,e2) =
298 if eq0_nat n1 || eq0_nat n2 then
299 float0
300 else
301 let s = badd s1 s2 in
302 let n' = mul_nat n1 n2 in
303 let n, e' = if s1 = s2 then lo_nat pp n' else hi_nat pp n' in
304 let e = e1 + e2 + e' - min_exp in
305 if e < 0 then
306 failwith "mul_float_lo: underflow"
307 else
308 (s, n, e);;
309
310
311 let mul_float_hi pp (s1,n1,e1) (s2,n2,e2) =
312 if eq0_nat n1 || eq0_nat n2 then
313 float0
314 else
315 let s = badd s1 s2 in
316 let n' = mul_nat n1 n2 in
317 let n, e' = if s1 = s2 then hi_nat pp n' else lo_nat pp n' in
318 let e = e1 + e2 + e' - min_exp in
319 if e < 0 then
320 failwith "mul_float_hi: underflow"
321 else
322 (s, n, e);;
323
324
325 (* div *)
326
327 let div_float_lo pp (s1,n1,e1) (s2,n2,e2) =
328 if eq0_nat n1 then
329 float0
330 else
331 let s = badd s1 s2 in
332 let k = 2 * pp in
333 let nn1 = denormalize_nat (n1, k) in
334 let n' = div_nat nn1 n2 in
335 let n, e' = if s1 = s2 then lo_nat pp n' else hi_lt_nat pp n' in
336 let e = min_exp + e' + e1 - e2 - k in
337 if e < 0 then
338 failwith "div_float_lo: underflow"
339 else
340 (s, n, e);;
341
342 let div_float_hi pp (s1,n1,e1) (s2,n2,e2) =
343 if eq0_nat n1 then
344 float0
345 else
346 let s = badd s1 s2 in
347 let k = 2 * pp in
348 let nn1 = denormalize_nat (n1, k) in
349 let n' = div_nat nn1 n2 in
350 let n, e' = if s1 = s2 then hi_lt_nat pp n' else lo_nat pp n' in
351 let e = min_exp + e' + e1 - e2 - k in
352 if e < 0 then
353 failwith "div_float_hi: underflow"
354 else
355 (s, n, e);;
356
357 (* inv *)
358
359 let inv_float_lo pp x =
360 div_float_lo pp float1 x;;
361
362 let inv_float_hi pp x =
363 div_float_hi pp float1 x;;
364
365
366 (* add *)
367
368 let add_float_lo pp (s1,n1,e1) (s2,n2,e2) =
369 if s1 = s2 then
370 let n', e' = num_exp_add (n1,e1) (n2,e2) in
371 let n, e'' = if s1 then hi_nat pp n' else lo_nat pp n' in
372 (s1, n, e' + e'')
373 else
374 if s1 then
375 let (n', e'), flag = num_exp_sub (n2,e2) (n1,e1) in
376 if flag then
377 let n, e'' = lo_nat pp n' in
378 (false, n, e' + e'')
379 else
380 let n, e'' = hi_nat pp n' in
381 (true, n, e' + e'')
382 else
383 let (n', e'), flag = num_exp_sub (n1,e1) (n2,e2) in
384 if flag then
385 let n, e'' = lo_nat pp n' in
386 (false, n, e' + e'')
387 else
388 let n, e'' = hi_nat pp n' in
389 (true, n, e' + e'');;
390
391
392 let add_float_hi pp (s1,n1,e1) (s2,n2,e2) =
393 if s1 = s2 then
394 let n', e' = num_exp_add (n1,e1) (n2,e2) in
395 let n, e'' = if s1 then lo_nat pp n' else hi_nat pp n' in
396 (s1, n, e' + e'')
397 else
398 if s1 then
399 let (n', e'), flag = num_exp_sub (n2,e2) (n1,e1) in
400 if flag then
401 let n, e'' = hi_nat pp n' in
402 (false, n, e' + e'')
403 else
404 let n, e'' = lo_nat pp n' in
405 (true, n, e' + e'')
406 else
407 let (n', e'), flag = num_exp_sub (n1,e1) (n2,e2) in
408 if flag then
409 let n, e'' = hi_nat pp n' in
410 (false, n, e' + e'')
411 else
412 let n, e'' = lo_nat pp n' in
413 (true, n, e' + e'');;
414
415
416 (* sub *)
417
418 let sub_float_lo pp f1 f2 = add_float_lo pp f1 (neg_float f2);;
419 let sub_float_hi pp f1 f2 = add_float_hi pp f1 (neg_float f2);;
420
421
422 (* sqrt *)
423
424 let rec sqrt_float_lo pp (s,n1,e1) =
425 if s then
426 failwith "sqrt_float_lo: negative argument"
427 else
428 if e1 land 1 = 1 then
429 sqrt_float_lo pp (s, denormalize_nat (n1, 1), e1 - 1)
430 else
431 let p2 = pp * 2 in
432 let f1' = denormalize_nat (n1, p2) in
433 let f1 = Big_int.sqrt_big_int (big_int_of_num (dest_nat f1')) in
434 let n, e' = lo_nat pp (mk_nat (num_of_big_int f1)) in
435 let e = ((e1 + min_exp) lsr 1) + e' - pp in
436 if e < 0 then
437 failwith "sqrt_float_lo: underflow"
438 else
439 (s, n, e);;
440
441
442 let rec sqrt_float_hi pp (s,n1,e1) =
443 if s then
444 failwith "sqrt_float_hi: negative argument"
445 else
446 if e1 land 1 = 1 then
447 sqrt_float_hi pp (s, denormalize_nat (n1, 1), e1 - 1)
448 else
449 let p2 = pp * 2 in
450 let x = (big_int_of_num o dest_nat o denormalize_nat) (n1, p2) in
451 let f1' = Big_int.sqrt_big_int x in
452 let f1 = (mk_nat o num_of_big_int) f1' in
453 let n, e' =
454 let ( * ) = Big_int.mult_big_int and
455 (==) = Big_int.eq_big_int in
456 hi_nat pp (if f1' * f1' == x then f1 else suc_nat f1) in
457 let e = ((e1 + min_exp) lsr 1) + e' - pp in
458 if e < 0 then
459 failwith "sqrt_float_hi: underflow"
460 else
461 (s, n, e);;
462
463 (* pow *)
464
465 let pow_float_pos_hi pp n (x : ifloat) =
466 let rec pow n =
467 match n with
468 | 0 -> float1
469 | 1 -> x
470 | 2 -> mul_float_hi pp x x
471 | _ ->
472 if (n land 1) = 0 then
473 let t = pow (n lsr 1) in
474 mul_float_hi pp t t
475 else
476 let t = pow (n - 1) in
477 mul_float_hi pp x t in
478 let _ = assert (n >= 0) in
479 pow n;;
480
481 let pow_float_pos_lo pp n (x : ifloat) =
482 let rec pow n =
483 match n with
484 | 0 -> float1
485 | 1 -> x
486 | 2 -> mul_float_lo pp x x
487 | _ ->
488 if (n land 1) = 0 then
489 let t = pow (n lsr 1) in
490 mul_float_lo pp t t
491 else
492 let t = pow (n - 1) in
493 mul_float_lo pp x t in
494 let _ = assert (n >= 0) in
495 pow n;;
496
497 let pow_float_hi pp n x =
498 match n with
499 | 0 -> float1
500 | 1 -> x
501 | 2 -> mul_float_hi pp x x
502 | _ ->
503 let _ = assert (n > 2) in
504 if not (sign_float x) then
505 pow_float_pos_hi pp n x
506 else
507 let x_pos = abs_float x in
508 if (n land 1) = 0 then
509 pow_float_pos_hi pp n x_pos
510 else
511 neg_float (pow_float_pos_lo pp n x_pos);;
512
513 let pow_float_lo pp n x =
514 match n with
515 | 0 -> float1
516 | 1 -> x
517 | 2 -> mul_float_lo pp x x
518 | _ ->
519 let _ = assert (n > 2) in
520 if not (sign_float x) then
521 pow_float_pos_lo pp n x
522 else
523 let x_pos = abs_float x in
524 if (n land 1) = 0 then
525 pow_float_pos_lo pp n x_pos
526 else
527 neg_float (pow_float_pos_hi pp n x_pos);;
528
529 end;;
530
531