(* ========================================================================== *) (* Formal verification of nonlinear inequalities in HOL Light *) (* *) (* Copyright (c) 2014 Alexey Solovyev *) (* *) (* This file is distributed under the terms of the MIT licence *) (* ========================================================================== *) (* -------------------------------------------------------------------------- *) (* Informal arithmetic procedures: matan *) (* -------------------------------------------------------------------------- *) (* Dependencies *) needs "Formal_ineqs/informal/informal_atn.hl";; (* matan *) module type Informal_matan_sig = sig val matan_interval : int -> Informal_interval.interval -> Informal_interval.interval val dmatan_interval : int -> Informal_interval.interval -> Informal_interval.interval val ddmatan_interval : int -> Informal_interval.interval -> Informal_interval.interval end;; module Informal_matan : Informal_matan_sig = struct open Num;; open Informal_float;; open Informal_interval;; open Informal_atn;; (* Creates an interval approximation of the given decimal term *) let mk_float_interval_decimal pp decimal_tm = let n_tm, d_tm = dest_binary "DECIMAL" decimal_tm in let n, d = dest_numeral n_tm, dest_numeral d_tm in let n_int, d_int = mk_num_interval n, mk_num_interval d in div_interval pp n_int d_int;; let interval_neg_02 = neg_interval (mk_float_interval_decimal 10 `#0.2`);; let interval_09 = mk_float_interval_decimal 10 `#0.9`;; let interval_1e8 = mk_float_interval_decimal 10 `#0.00000001`;; let float_1e8 = fst (dest_interval interval_1e8);; (* matan *) let matan_interval = let one = mk_small_num_interval 1 and three = mk_small_num_interval 3 and five = mk_small_num_interval 5 and fseven = mk_small_num_float 7 and fone = mk_small_num_float 1 in fun pp x -> let ( * ) = mul_interval pp and ( / ) = div_interval pp and ( + ) = add_interval pp and ( - ) = sub_interval pp in let lo, hi = dest_interval x in let flag = le_float lo float_1e8 in if flag then (* Use series *) let u = iabs_interval x in let flag = le_interval u interval_09 in if not flag then failwith "matan_interval: the argument is out of range" else let s = (one - x / three) + (x * x) / five in let u3 = mul_float_hi pp u (mul_float_hi pp u u) in let r1 = sub_float_lo pp fone u in let r2 = mul_float_lo pp fseven r1 in let err = div_float_hi pp u3 r2 in let a, b = dest_interval s in let low = sub_float_lo pp a err and high = add_float_hi pp b err in mk_interval (low, high) else let r = sqrt_interval pp x in let r2 = atn_interval pp r in r2 / r;; (* dmatan *) let dmatan_interval = let one = mk_small_num_interval 1 and two = mk_small_num_interval 2 and three = mk_small_num_interval 3 and five = mk_small_num_interval 5 and ftwo = mk_small_num_float 2 and fone = mk_small_num_float 1 in fun pp x -> let ( * ) = mul_interval pp and ( / ) = div_interval pp and ( + ) = add_interval pp and ( - ) = sub_interval pp in let lo, hi = dest_interval x in let flag = le_float lo float_1e8 in if flag then (* Use series *) let u = iabs_interval x in let flag = le_interval u interval_09 in if not flag then failwith "dmatan_interval: the argument is out of range" else let s = two * (x / five) - one / three in let u2 = mul_float_hi pp u u in let r1 = sub_float_lo pp fone u in let r2 = mul_float_lo pp ftwo r1 in let err = div_float_hi pp u2 r2 in let a, b = dest_interval s in let low = sub_float_lo pp a err and high = add_float_hi pp b err in mk_interval (low, high) else let r = sqrt_interval pp x in let two_x = two * x in let s1 = inv_interval pp (two_x * (x + one)) in let s2 = (atn_interval pp r) / (two_x * r) in s1 - s2;; (* ddmatan *) let ddmatan_interval = let v = mk_float_interval_decimal 20 `#0.65` in let v0 = mk_small_num_interval 1 in let vs = Array.init 20 (fun i -> if i = 0 then v0 else round_interval i v) in fun pp x -> let lo, _ = dest_interval x in let flag = ge_interval lo interval_neg_02 in if not flag then failwith "ddmatan_interval: the argument is out of range" else let v = vs.(pp) in let _, b = dest_interval v in mk_interval (neg_float b, b);; end;; (* (***************************) let pp = 8;; let n = -10000;; let a = 3 and b = 5;; open Informal_interval;; open Informal_float;; open Informal_matan;; open Arith_float;; #install_printer print_ifloat;; #install_printer print_interval;; let f = Eval_interval.build_interval_fun `&1 + &3`;; Eval_interval.eval_interval_fun 3 f [] [];; let mk_intervals pp a b = let inf_mk tm = let f = Informal_eval_interval.build_interval_fun tm in Informal_eval_interval.eval_interval_fun pp f [] [] in let mk tm = let f = Eval_interval.build_interval_fun tm in Eval_interval.eval_interval_fun pp f [] [] in let x1 = (fst o dest_interval o inf_mk) a and x2 = (snd o dest_interval o inf_mk) b in let f1 = (fst o dest_pair o rand o concl o mk) a and f2 = (snd o dest_pair o rand o concl o mk) b in let inf_int = mk_interval (x1, x2) in let int = (ASSUME o Interval_arith.mk_interval `x:real` o mk_pair) (f1, f2) in inf_int, int;; let test_ints1 = map (uncurry (mk_intervals 3)) [ `-- #0.5`, ` -- #0.5`; `-- #0.1`, `-- #0.1`; `&0`, `&0`; `#0.00000000000001`, `#0.00000000000001`; `#0.1`, `#0.1`; `#0.9`, `#0.9`; `&10`, `&10`];; let test_ints2 = map (uncurry (mk_intervals 3)) [ `-- #0.5`, ` -- #0.4`; `-- #0.1`, `#0.1`; `&0`, `&1`; `#0.00000000000001`, `#0.2`; `#0.1`, `&1`; `#0.9`, `#1.9`; `&10`, `&100`];; let check pp (x, x_th) = (Matan_eval.float_interval_matan pp x_th), matan_interval pp x;; let dcheck pp (x, x_th) = (Matan_eval.float_interval_dmatan pp x_th), dmatan_interval pp x;; let ddcheck pp (x, x_th) = (Matan_eval.float_interval_ddmatan pp x_th), ddmatan_interval pp x;; ddcheck 3 (List.nth test_ints2 4);; *)