| 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: matan *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
(* Dependencies *) |
| 14 |
needs "Formal_ineqs/informal/informal_atn.hl";; |
| 15 |
|
| 16 |
(* matan *) |
| 17 |
module type Informal_matan_sig = |
| 18 |
sig |
| 19 |
val matan_interval : int -> Informal_interval.interval -> Informal_interval.interval |
| 20 |
val dmatan_interval : int -> Informal_interval.interval -> Informal_interval.interval |
| 21 |
val ddmatan_interval : int -> Informal_interval.interval -> Informal_interval.interval |
| 22 |
end;; |
| 23 |
|
| 24 |
module Informal_matan : Informal_matan_sig = struct |
| 25 |
|
| 26 |
open Num;; |
| 27 |
open Informal_float;; |
| 28 |
open Informal_interval;; |
| 29 |
open Informal_atn;; |
| 30 |
|
| 31 |
(* Creates an interval approximation of the given decimal term *) |
| 32 |
let mk_float_interval_decimal pp decimal_tm = |
| 33 |
let n_tm, d_tm = dest_binary "DECIMAL" decimal_tm in |
| 34 |
let n, d = dest_numeral n_tm, dest_numeral d_tm in |
| 35 |
let n_int, d_int = mk_num_interval n, mk_num_interval d in |
| 36 |
div_interval pp n_int d_int;; |
| 37 |
|
| 38 |
let interval_neg_02 = neg_interval (mk_float_interval_decimal 10 `#0.2`);; |
| 39 |
let interval_09 = mk_float_interval_decimal 10 `#0.9`;; |
| 40 |
let interval_1e8 = mk_float_interval_decimal 10 `#0.00000001`;; |
| 41 |
let float_1e8 = fst (dest_interval interval_1e8);; |
| 42 |
|
| 43 |
|
| 44 |
(* matan *) |
| 45 |
|
| 46 |
let matan_interval = |
| 47 |
let one = mk_small_num_interval 1 and |
| 48 |
three = mk_small_num_interval 3 and |
| 49 |
five = mk_small_num_interval 5 and |
| 50 |
fseven = mk_small_num_float 7 and |
| 51 |
fone = mk_small_num_float 1 in |
| 52 |
fun pp x -> |
| 53 |
let ( * ) = mul_interval pp and |
| 54 |
( / ) = div_interval pp and |
| 55 |
( + ) = add_interval pp and |
| 56 |
( - ) = sub_interval pp in |
| 57 |
let lo, hi = dest_interval x in |
| 58 |
let flag = le_float lo float_1e8 in |
| 59 |
if flag then |
| 60 |
(* Use series *) |
| 61 |
let u = iabs_interval x in |
| 62 |
let flag = le_interval u interval_09 in |
| 63 |
if not flag then |
| 64 |
failwith "matan_interval: the argument is out of range" |
| 65 |
else |
| 66 |
let s = (one - x / three) + (x * x) / five in |
| 67 |
let u3 = mul_float_hi pp u (mul_float_hi pp u u) in |
| 68 |
let r1 = sub_float_lo pp fone u in |
| 69 |
let r2 = mul_float_lo pp fseven r1 in |
| 70 |
let err = div_float_hi pp u3 r2 in |
| 71 |
let a, b = dest_interval s in |
| 72 |
let low = sub_float_lo pp a err and |
| 73 |
high = add_float_hi pp b err in |
| 74 |
mk_interval (low, high) |
| 75 |
else |
| 76 |
let r = sqrt_interval pp x in |
| 77 |
let r2 = atn_interval pp r in |
| 78 |
r2 / r;; |
| 79 |
|
| 80 |
|
| 81 |
(* dmatan *) |
| 82 |
|
| 83 |
let dmatan_interval = |
| 84 |
let one = mk_small_num_interval 1 and |
| 85 |
two = mk_small_num_interval 2 and |
| 86 |
three = mk_small_num_interval 3 and |
| 87 |
five = mk_small_num_interval 5 and |
| 88 |
ftwo = mk_small_num_float 2 and |
| 89 |
fone = mk_small_num_float 1 in |
| 90 |
fun pp x -> |
| 91 |
let ( * ) = mul_interval pp and |
| 92 |
( / ) = div_interval pp and |
| 93 |
( + ) = add_interval pp and |
| 94 |
( - ) = sub_interval pp in |
| 95 |
let lo, hi = dest_interval x in |
| 96 |
let flag = le_float lo float_1e8 in |
| 97 |
if flag then |
| 98 |
(* Use series *) |
| 99 |
let u = iabs_interval x in |
| 100 |
let flag = le_interval u interval_09 in |
| 101 |
if not flag then |
| 102 |
failwith "dmatan_interval: the argument is out of range" |
| 103 |
else |
| 104 |
let s = two * (x / five) - one / three in |
| 105 |
let u2 = mul_float_hi pp u u in |
| 106 |
let r1 = sub_float_lo pp fone u in |
| 107 |
let r2 = mul_float_lo pp ftwo r1 in |
| 108 |
let err = div_float_hi pp u2 r2 in |
| 109 |
let a, b = dest_interval s in |
| 110 |
let low = sub_float_lo pp a err and |
| 111 |
high = add_float_hi pp b err in |
| 112 |
mk_interval (low, high) |
| 113 |
else |
| 114 |
let r = sqrt_interval pp x in |
| 115 |
let two_x = two * x in |
| 116 |
let s1 = inv_interval pp (two_x * (x + one)) in |
| 117 |
let s2 = (atn_interval pp r) / (two_x * r) in |
| 118 |
s1 - s2;; |
| 119 |
|
| 120 |
|
| 121 |
(* ddmatan *) |
| 122 |
|
| 123 |
let ddmatan_interval = |
| 124 |
let v = mk_float_interval_decimal 20 `#0.65` in |
| 125 |
let v0 = mk_small_num_interval 1 in |
| 126 |
let vs = Array.init 20 |
| 127 |
(fun i -> if i = 0 then v0 else round_interval i v) in |
| 128 |
fun pp x -> |
| 129 |
let lo, _ = dest_interval x in |
| 130 |
let flag = ge_interval lo interval_neg_02 in |
| 131 |
if not flag then |
| 132 |
failwith "ddmatan_interval: the argument is out of range" |
| 133 |
else |
| 134 |
let v = vs.(pp) in |
| 135 |
let _, b = dest_interval v in |
| 136 |
mk_interval (neg_float b, b);; |
| 137 |
|
| 138 |
end;; |
| 139 |
|
| 140 |
|
| 141 |
|
| 142 |
(* |
| 143 |
|
| 144 |
(***************************) |
| 145 |
|
| 146 |
let pp = 8;; |
| 147 |
let n = -10000;; |
| 148 |
let a = 3 and |
| 149 |
b = 5;; |
| 150 |
|
| 151 |
open Informal_interval;; |
| 152 |
open Informal_float;; |
| 153 |
open Informal_matan;; |
| 154 |
open Arith_float;; |
| 155 |
|
| 156 |
#install_printer print_ifloat;; |
| 157 |
#install_printer print_interval;; |
| 158 |
|
| 159 |
let f = Eval_interval.build_interval_fun `&1 + &3`;; |
| 160 |
Eval_interval.eval_interval_fun 3 f [] [];; |
| 161 |
|
| 162 |
let mk_intervals pp a b = |
| 163 |
let inf_mk tm = |
| 164 |
let f = Informal_eval_interval.build_interval_fun tm in |
| 165 |
Informal_eval_interval.eval_interval_fun pp f [] [] in |
| 166 |
let mk tm = |
| 167 |
let f = Eval_interval.build_interval_fun tm in |
| 168 |
Eval_interval.eval_interval_fun pp f [] [] in |
| 169 |
let x1 = (fst o dest_interval o inf_mk) a and |
| 170 |
x2 = (snd o dest_interval o inf_mk) b in |
| 171 |
let f1 = (fst o dest_pair o rand o concl o mk) a and |
| 172 |
f2 = (snd o dest_pair o rand o concl o mk) b in |
| 173 |
let inf_int = mk_interval (x1, x2) in |
| 174 |
let int = (ASSUME o Interval_arith.mk_interval `x:real` o mk_pair) (f1, f2) in |
| 175 |
inf_int, int;; |
| 176 |
|
| 177 |
let test_ints1 = map (uncurry (mk_intervals 3)) [ |
| 178 |
`-- #0.5`, ` -- #0.5`; |
| 179 |
`-- #0.1`, `-- #0.1`; |
| 180 |
`&0`, `&0`; |
| 181 |
`#0.00000000000001`, `#0.00000000000001`; |
| 182 |
`#0.1`, `#0.1`; |
| 183 |
`#0.9`, `#0.9`; |
| 184 |
`&10`, `&10`];; |
| 185 |
|
| 186 |
let test_ints2 = map (uncurry (mk_intervals 3)) [ |
| 187 |
`-- #0.5`, ` -- #0.4`; |
| 188 |
`-- #0.1`, `#0.1`; |
| 189 |
`&0`, `&1`; |
| 190 |
`#0.00000000000001`, `#0.2`; |
| 191 |
`#0.1`, `&1`; |
| 192 |
`#0.9`, `#1.9`; |
| 193 |
`&10`, `&100`];; |
| 194 |
|
| 195 |
let check pp (x, x_th) = |
| 196 |
(Matan_eval.float_interval_matan pp x_th), |
| 197 |
matan_interval pp x;; |
| 198 |
|
| 199 |
let dcheck pp (x, x_th) = |
| 200 |
(Matan_eval.float_interval_dmatan pp x_th), |
| 201 |
dmatan_interval pp x;; |
| 202 |
|
| 203 |
let ddcheck pp (x, x_th) = |
| 204 |
(Matan_eval.float_interval_ddmatan pp x_th), |
| 205 |
ddmatan_interval pp x;; |
| 206 |
|
| 207 |
|
| 208 |
ddcheck 3 (List.nth test_ints2 4);; |
| 209 |
|
| 210 |
|
| 211 |
|
| 212 |
*) |