| 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 |
*) |