(* ========================================================================== *) (* Formal verification of nonlinear inequalities in HOL Light *) (* *) (* Copyright (c) 2014 Alexey Solovyev *) (* *) (* This file is distributed under the terms of the MIT licence *) (* ========================================================================== *) (* -------------------------------------------------------------------------- *) (* Formal interval evaluation of functions: cos *) (* -------------------------------------------------------------------------- *) needs "Formal_ineqs/misc/misc_functions.hl";; needs "Formal_ineqs/misc/misc_vars.hl";; needs "Formal_ineqs/arith/interval_arith.hl";; needs "Formal_ineqs/trig/atn_eval.hl";; needs "Formal_ineqs/trig/cos_bounds_eval.hl";; module type Cos_eval_sig = sig val float_interval_cos : int -> thm -> thm end;; module Cos_eval : Cos_eval_sig = struct open Misc_functions;; open Float_theory;; open Interval_arith;; open More_float;; open Arith_float;; open Atn_eval;; open Cos_bounds_eval;; open Misc_vars;; prioritize_real();; (* Interval approximations of 2 * pi: *) (* (|- interval_arith (&2 * pi) (lo, hi), |- hi - lo <= t, (lo, hi)) *) let two_pi_array = let n = Array.length pi_approx_array in let pi = pi_approx_array.(n - 1) in let two_pi = float_interval_mul n two_interval pi in Array.init (n - 1) (fun i -> let th = float_interval_round i two_pi in let _, bounds = dest_interval_arith (concl th) in let lo_tm, hi_tm = dest_pair bounds in th, float_sub_hi i hi_tm lo_tm, (lo_tm, hi_tm));; let pi32_array = let n = Array.length pi_approx_array in let pi = pi_approx_array.(n - 1) in let three = mk_float_interval_small_num 3 in let pi32 = float_interval_div n (float_interval_mul n three pi) two_interval in Array.init (n - 1) (fun i -> let th = float_interval_round i pi32 in let _, bounds = dest_interval_arith (concl th) in let lo_tm, hi_tm = dest_pair bounds in th, (lo_tm, hi_tm));; (* Interval approximations of -pi *) let neg_pi_array = let n = Array.length pi_approx_array in Array.init n (fun i -> float_interval_neg pi_approx_array.(i));; let neg_pi_le_pi_lo_array = let th = prove(`(&0 <= lo <=> T) ==> --pi <= lo`, MP_TAC PI_POS_LE THEN REAL_ARITH_TAC) in let n = Array.length pi_approx_array in Array.init n (fun i -> let lo = (rand o rator o rand o concl) pi_approx_array.(i) in let lo_ge0 = float_ge0 lo in MATCH_MP th lo_ge0);; (* Theorems of the form: |- &2 * pi <= high, |- &0 <= low *) let two_pi_high, two_pi_low = let interval_pos = prove(`interval_arith x (float_num F n e, f) ==> x <= f /\ &0 <= (float_num F n e)`, REWRITE_TAC[interval_arith] THEN MP_TAC (SPECL[`n:num`; `e:num`] FLOAT_F_POS) THEN REAL_ARITH_TAC) in let two_pi_list = Array.to_list two_pi_array in let ths1 = map (fun (th,_,_) -> CONJUNCTS (MATCH_MP interval_pos th)) two_pi_list in let list1, list2 = unzip (map pair_of_list ths1) in Array.of_list list1, Array.of_list list2;; (**********) let f_pi = 3.14159265358979323846 and f_2_pi = 6.28318530717958647693 and f_pi_2 = 1.57079632679489661923;; let th_rule = UNDISCH_ALL o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL;; let case_rule = PURE_REWRITE_RULE[NOT_CLAUSES; GSYM float1_eq; FLOAT_NEG] o th_rule;; (* cos cases *) let cos_minus_pi = prove(`!x. cos (x - pi) = -- cos x`, ONCE_REWRITE_TAC[GSYM (SPEC `x - pi` COS_PERIODIC)] THEN REWRITE_TAC[REAL_ARITH `a - b + &2 * b = a + b`] THEN REWRITE_TAC[COS_PERIODIC_PI]);; let cos_pi_minus = prove(`!x. cos (pi - x) = -- cos x`, ONCE_REWRITE_TAC[REAL_ARITH `a - b = --(b - a)`] THEN REWRITE_TAC[COS_NEG; cos_minus_pi]);; let cos_2pi_minus = prove(`cos (&2 * pi - x) = cos x`, REWRITE_TAC[COS_EQ] THEN EXISTS_TAC `&1` THEN REWRITE_TAC[INTEGER_CLOSED] THEN REAL_ARITH_TAC);; (* -1 *) let cos_full_interval = prove(`!x. interval_arith (cos x) (-- &1, &1)`, REWRITE_TAC[interval_arith; COS_BOUNDS]);; let cos_case_neg1 = case_rule cos_full_interval;; (* 0 *) let cos_reduction_0_pi_1 = prove(`interval_arith x (a,b) /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) /\ interval_arith a1 (&0, pi) /\ b1 <= pi /\ cos a1 <= high /\ low <= cos b1 ==> interval_arith (cos x) (low, high)`, REWRITE_TAC[interval_arith] THEN STRIP_TAC THEN REWRITE_TAC[GSYM interval_arith] THEN MATCH_MP_TAC APPROX_INTERVAL THEN EXISTS_TAC `cos b1` THEN EXISTS_TAC `cos a1` THEN ASM_REWRITE_TAC[interval_arith] THEN SUBGOAL_THEN `cos x = cos (x + (&2 * pi) * k)` (fun th -> REWRITE_TAC[th]) THENL [ REWRITE_TAC[COS_EQ] THEN EXISTS_TAC `--k:real` THEN ASM_SIMP_TAC[INTEGER_CLOSED] THEN REAL_ARITH_TAC; ALL_TAC ] THEN CONJ_TAC THEN MATCH_MP_TAC COS_MONO_LE THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let cos_case0 = case_rule cos_reduction_0_pi_1;; (* 1 *) let cos_reduction_0_pi_2 = prove(`interval_arith x (a,b) /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) /\ interval_arith a1 (&0, pi) /\ b1 <= &2 * pi /\ cos a1 <= high1 /\ cos b1 <= high2 /\ max high1 high2 = high ==> interval_arith (cos x) (-- &1, high)`, REWRITE_TAC[interval_arith; COS_BOUNDS] THEN STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `max (cos a1) (cos b1)` THEN CONJ_TAC THENL [ ALL_TAC; REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC ] THEN REWRITE_TAC[REAL_LE_MAX] THEN SUBGOAL_THEN `cos x = cos (x + (&2 * pi) * k)` (fun th -> REWRITE_TAC[th]) THENL [ REWRITE_TAC[COS_EQ] THEN EXISTS_TAC `--k:real` THEN ASM_SIMP_TAC[INTEGER_CLOSED] THEN REAL_ARITH_TAC; ALL_TAC ] THEN ASM_CASES_TAC `x + (&2 * pi) * k <= pi` THENL [ DISJ1_TAC THEN MATCH_MP_TAC COS_MONO_LE THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; ALL_TAC ] THEN DISJ2_TAC THEN ONCE_REWRITE_TAC[GSYM REAL_LE_NEG2] THEN REWRITE_TAC[GSYM cos_minus_pi] THEN MATCH_MP_TAC COS_MONO_LE THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let cos_case1 = case_rule cos_reduction_0_pi_2;; (* 2 *) let cos_reduction_0_pi_2a = prove(`interval_arith x (a,b) /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) /\ interval_arith a1 (&0, pi) /\ a1 + b1 <= &2 * pi /\ cos a1 <= high ==> interval_arith (cos x) (-- &1, high)`, STRIP_TAC THEN MATCH_MP_TAC (GEN_ALL cos_reduction_0_pi_2) THEN MAP_EVERY EXISTS_TAC [`a:real`; `b:real`; `a1:real`; `b1:real`; `high:real`; `high:real`] THEN ASM_REWRITE_TAC[REAL_MAX_ACI] THEN REPEAT CONJ_TAC THENL [ EXISTS_TAC `k:real` THEN ASM_REWRITE_TAC[]; REPEAT (POP_ASSUM MP_TAC) THEN REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC; ALL_TAC ] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `cos a1` THEN ASM_REWRITE_TAC[] THEN ASM_CASES_TAC `b1 <= pi` THENL [ MATCH_MP_TAC COS_MONO_LE THEN REPEAT (POP_ASSUM MP_TAC) THEN REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC; ALL_TAC ] THEN ONCE_REWRITE_TAC[GSYM REAL_LE_NEG2] THEN REWRITE_TAC[GSYM cos_minus_pi] THEN SUBGOAL_THEN `cos (a1 - pi) = cos (pi - a1)` (fun th -> REWRITE_TAC[th]) THENL [ ONCE_REWRITE_TAC[REAL_ARITH `a1 - pi = --(pi - a1)`] THEN REWRITE_TAC[COS_NEG]; ALL_TAC ] THEN MATCH_MP_TAC COS_MONO_LE THEN REPEAT (POP_ASSUM MP_TAC) THEN REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let cos_case2 = case_rule cos_reduction_0_pi_2a;; (* 3 *) let cos_reduction_0_pi_2b = prove(`interval_arith x (a,b) /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) /\ interval_arith a1 (&0, pi) /\ b1 <= &2 * pi /\ &2 * pi <= a1 + b1 /\ cos b1 <= high ==> interval_arith (cos x) (-- &1, high)`, STRIP_TAC THEN MATCH_MP_TAC (GEN_ALL cos_reduction_0_pi_2) THEN MAP_EVERY EXISTS_TAC [`a:real`; `b:real`; `a1:real`; `b1:real`; `high:real`; `high:real`] THEN ASM_REWRITE_TAC[REAL_MAX_ACI] THEN REPEAT CONJ_TAC THENL [ EXISTS_TAC `k:real` THEN ASM_REWRITE_TAC[]; ALL_TAC ] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `cos b1` THEN ASM_REWRITE_TAC[] THEN ONCE_REWRITE_TAC[GSYM REAL_LE_NEG2] THEN REWRITE_TAC[GSYM cos_minus_pi] THEN SUBGOAL_THEN `cos (a1 - pi) = cos (pi - a1)` (fun th -> REWRITE_TAC[th]) THENL [ ONCE_REWRITE_TAC[REAL_ARITH `a1 - pi = --(pi - a1)`] THEN REWRITE_TAC[COS_NEG]; ALL_TAC ] THEN MATCH_MP_TAC COS_MONO_LE THEN REPEAT (POP_ASSUM MP_TAC) THEN REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let cos_case3 = case_rule cos_reduction_0_pi_2b;; (* 4 *) let cos_reduction_neg_pi_0_1 = prove(`interval_arith x (a,b) /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) /\ interval_arith a1 (--pi, &0) /\ (b1 <= &0 <=> T) /\ low <= cos a1 /\ cos b1 <= high ==> interval_arith (cos x) (low, high)`, STRIP_TAC THEN ONCE_REWRITE_TAC[GSYM INTERVAL_NEG_EQ] THEN REWRITE_TAC[GSYM COS_PERIODIC_PI] THEN MATCH_MP_TAC (GEN_ALL cos_reduction_0_pi_1) THEN MAP_EVERY EXISTS_TAC [`a + pi`; `b + pi`; `a1 + pi`; `b1 + pi`] THEN REWRITE_TAC[COS_PERIODIC_PI] THEN REPEAT CONJ_TAC THEN TRY (REPEAT (POP_ASSUM MP_TAC) THEN REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) THEN EXISTS_TAC `k:real` THEN ASM_REWRITE_TAC[] THEN CONJ_TAC THENL [ ASM_REWRITE_TAC[REAL_ARITH `(a + pi) + b = (a + b) + pi`; REAL_LE_RADD]; ASM_REWRITE_TAC[REAL_ARITH `(a + pi) + b = (a + b) + pi`; REAL_LE_RADD]; ]);; let cos_case4 = case_rule cos_reduction_neg_pi_0_1;; (* 5 (not used in computations) *) let cos_reduction_neg_pi_0_2 = prove(`interval_arith x (a,b) /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) /\ interval_arith a1 (--pi, &0) /\ b1 <= pi /\ low1 <= cos a1 /\ low2 <= cos b1 /\ min low1 low2 = low ==> interval_arith (cos x) (low, &1)`, STRIP_TAC THEN ONCE_REWRITE_TAC[GSYM INTERVAL_NEG_EQ] THEN REWRITE_TAC[GSYM COS_PERIODIC_PI] THEN MATCH_MP_TAC (GEN_ALL cos_reduction_0_pi_2) THEN MAP_EVERY EXISTS_TAC [`a + pi`; `b + pi`; `a1 + pi`; `b1 + pi`; `--low1`; `--low2`] THEN REWRITE_TAC[COS_PERIODIC_PI] THEN REPEAT CONJ_TAC THEN TRY (REPEAT (POP_ASSUM MP_TAC) THEN REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) THEN EXISTS_TAC `k:real` THEN ASM_REWRITE_TAC[] THEN CONJ_TAC THENL [ ASM_REWRITE_TAC[REAL_ARITH `(a + pi) + b = (a + b) + pi`; REAL_LE_RADD]; ASM_REWRITE_TAC[REAL_ARITH `(a + pi) + b = (a + b) + pi`; REAL_LE_RADD]; ]);; let cos_case5 = case_rule cos_reduction_neg_pi_0_2;; (* 6 *) let cos_reduction_neg_pi_0_2a = prove(`interval_arith x (a,b) /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) /\ interval_arith a1 (--pi, &0) /\ b2 = --b1 /\ (a1 <= b2 <=> T) /\ low <= cos a1 ==> interval_arith (cos x) (low, &1)`, STRIP_TAC THEN ONCE_REWRITE_TAC[GSYM INTERVAL_NEG_EQ] THEN REWRITE_TAC[GSYM COS_PERIODIC_PI] THEN MATCH_MP_TAC (GEN_ALL cos_reduction_0_pi_2a) THEN MAP_EVERY EXISTS_TAC [`a + pi`; `b + pi`; `b1 + pi`; `a1 + pi`] THEN REWRITE_TAC[COS_PERIODIC_PI] THEN REPEAT CONJ_TAC THEN TRY (REPEAT (POP_ASSUM MP_TAC) THEN REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) THEN EXISTS_TAC `k:real` THEN ASM_REWRITE_TAC[] THEN CONJ_TAC THENL [ ASM_REWRITE_TAC[REAL_ARITH `(a + pi) + b = (a + b) + pi`; REAL_LE_RADD]; ASM_REWRITE_TAC[REAL_ARITH `(a + pi) + b = (a + b) + pi`; REAL_LE_RADD]; ]);; let cos_case6 = case_rule cos_reduction_neg_pi_0_2a;; (* 7 *) let cos_reduction_neg_pi_0_2b = prove(`interval_arith x (a,b) /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) /\ interval_arith a1 (--pi, &0) /\ b1 <= pi /\ b2 = --b1 /\ (a1 <= b2 <=> F) /\ low <= cos b1 ==> interval_arith (cos x) (low, &1)`, STRIP_TAC THEN ONCE_REWRITE_TAC[GSYM INTERVAL_NEG_EQ] THEN REWRITE_TAC[GSYM COS_PERIODIC_PI] THEN MATCH_MP_TAC (GEN_ALL cos_reduction_0_pi_2b) THEN MAP_EVERY EXISTS_TAC [`a + pi`; `b + pi`; `a1 + pi`; `b1 + pi`] THEN REWRITE_TAC[COS_PERIODIC_PI] THEN REPEAT CONJ_TAC THEN TRY (REPEAT (POP_ASSUM MP_TAC) THEN REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) THEN EXISTS_TAC `k:real` THEN ASM_REWRITE_TAC[] THEN CONJ_TAC THENL [ ASM_REWRITE_TAC[REAL_ARITH `(a + pi) + b = (a + b) + pi`; REAL_LE_RADD]; ASM_REWRITE_TAC[REAL_ARITH `(a + pi) + b = (a + b) + pi`; REAL_LE_RADD]; ]);; let cos_case7 = case_rule cos_reduction_neg_pi_0_2b;; (* ---------------------------- *) (* Reduction to [0, pi / 2] *) (* ---------------------------- *) let cos_high_trivial = (case_rule o prove) (`cos x <= &1`, REWRITE_TAC[COS_BOUNDS]);; let cos_low_trivial = (case_rule o prove) (`-- &1 <= cos x`, REWRITE_TAC[COS_BOUNDS]);; let interval_neg_pi_0 = (case_rule o prove) (`interval_arith x (--pi, &0) /\ y = --x ==> interval_arith y (&0, pi)`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let reduction_high_neg = (case_rule o prove) (`y = --x /\ cos y <= high ==> cos x <= high`, STRIP_TAC THEN POP_ASSUM MP_TAC THEN ASM_REWRITE_TAC[COS_NEG]);; let reduction_low_neg = (case_rule o prove) (`y = --x /\ low <= cos y ==> low <= cos x`, STRIP_TAC THEN POP_ASSUM MP_TAC THEN ASM_REWRITE_TAC[COS_NEG]);; let reduction_high_0_pi = (case_rule o prove) (`interval_arith x (&0, pi) /\ interval_arith pi (lo, hi) /\ hi - x <= t /\ t <= pi /\ r <= cos t /\ high = --r ==> cos x <= high`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--cos t` THEN ASM_REWRITE_TAC[REAL_LE_NEG2] THEN REWRITE_TAC[GSYM cos_pi_minus] THEN MATCH_MP_TAC COS_MONO_LE THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let reduction_low_0_pi = (case_rule o prove) (`interval_arith x (&0, pi) /\ interval_arith pi (lo, hi) /\ t <= lo - x /\ (&0 <= t <=> T) /\ cos t <= r /\ low = --r ==> low <= cos x`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `--cos t` THEN ASM_REWRITE_TAC[REAL_LE_NEG2] THEN REWRITE_TAC[GSYM cos_pi_minus] THEN MATCH_MP_TAC COS_MONO_LE THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let reduction_high_pi_2pi_1 = (case_rule o prove) (`interval_arith x (pi, &2 * pi) /\ interval_arith (&2 * pi) (lo, hi) /\ t <= lo - x /\ (&0 <= t <=> T) /\ cos t <= r ==> cos x <= r`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `cos t` THEN ASM_REWRITE_TAC[] THEN SUBGOAL_THEN `cos x = cos (&2 * pi - x)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ REWRITE_TAC[cos_2pi_minus]; ALL_TAC ] THEN MATCH_MP_TAC COS_MONO_LE THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let reduction_low_pi_2pi_1 = (case_rule o prove) (`interval_arith x (pi, &2 * pi) /\ interval_arith (&2 * pi) (lo, hi) /\ hi - x <= t /\ t <= pi /\ r <= cos t ==> r <= cos x`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `cos t` THEN ASM_REWRITE_TAC[] THEN SUBGOAL_THEN `cos x = cos (&2 * pi - x)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ REWRITE_TAC[cos_2pi_minus]; ALL_TAC ] THEN MATCH_MP_TAC COS_MONO_LE THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let reduction_high_pi_2pi_2 = (case_rule o prove) (`interval_arith x (pi, &2 * pi) /\ interval_arith pi (lo, hi) /\ x - lo <= t /\ t <= pi /\ r <= cos t /\ high = --r ==> cos x <= high`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN SUBGOAL_THEN `cos x = --cos (x - pi)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ REWRITE_TAC[cos_minus_pi; REAL_NEG_NEG]; ALL_TAC ] THEN ASM_REWRITE_TAC[REAL_LE_NEG2] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `cos t` THEN ASM_REWRITE_TAC[] THEN MATCH_MP_TAC COS_MONO_LE THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let reduction_low_pi_2pi_2 = (case_rule o prove) (`interval_arith x (pi, &2 * pi) /\ interval_arith pi (lo, hi) /\ t <= x - hi /\ (&0 <= t <=> T) /\ cos t <= r /\ low = --r ==> low <= cos x`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN SUBGOAL_THEN `cos x = --cos (x - pi)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ REWRITE_TAC[cos_minus_pi; REAL_NEG_NEG]; ALL_TAC ] THEN ASM_REWRITE_TAC[REAL_LE_NEG2] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `cos t` THEN ASM_REWRITE_TAC[] THEN MATCH_MP_TAC COS_MONO_LE THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; (* ----------------------------- *) (* Reduction theorems *) (* ----------------------------- *) let reduction_zero_th = (th_rule o prove) (`?k. integer k /\ a <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b`, EXISTS_TAC `&0` THEN REWRITE_TAC[INTEGER_CLOSED] THEN REAL_ARITH_TAC);; let reduction_neg_th = (th_rule o prove) (`&i = z /\ interval_arith (&2 * pi) (lo, hi) /\ &0 <= lo /\ z * hi <= m /\ a1 <= a - m /\ n <= z * lo /\ b - n <= b1 ==> ?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN EXISTS_TAC `-- &i` THEN SIMP_TAC[INTEGER_CLOSED] THEN CONJ_TAC THENL [ MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a - m:real` THEN ASM_REWRITE_TAC[REAL_LE_LADD; real_sub; REAL_MUL_RNEG; REAL_LE_NEG2] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `z * hi:real` THEN ASM_REWRITE_TAC[REAL_ARITH `(&2 * pi) * z = z * (&2 * pi)`] THEN MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN MP_TAC PI_POS_LE THEN REAL_ARITH_TAC; MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b - n:real` THEN ASM_REWRITE_TAC[REAL_LE_LADD; real_sub; REAL_MUL_RNEG; REAL_LE_NEG2] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `z * lo:real` THEN ASM_REWRITE_TAC[REAL_ARITH `(&2 * pi) * z = z * (&2 * pi)`] THEN MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN MP_TAC PI_POS_LE THEN REAL_ARITH_TAC ]);; let reduction_pos_th = (th_rule o prove) (`&i = z /\ interval_arith (&2 * pi) (lo, hi) /\ &0 <= lo /\ m <= z * lo /\ a1 <= a + m /\ z * hi <= n /\ b + n <= b1 ==> ?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN EXISTS_TAC `&i` THEN SIMP_TAC[INTEGER_CLOSED] THEN CONJ_TAC THENL [ MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a + m:real` THEN ASM_REWRITE_TAC[REAL_LE_LADD] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `z * lo:real` THEN ASM_REWRITE_TAC[REAL_ARITH `(&2 * pi) * z = z * (&2 * pi)`] THEN MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b + n:real` THEN ASM_REWRITE_TAC[REAL_LE_LADD] THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `z * hi:real` THEN ASM_REWRITE_TAC[REAL_ARITH `(&2 * pi) * z = z * (&2 * pi)`] THEN MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN MP_TAC PI_POS_LE THEN REAL_ARITH_TAC ]);; let a_neg_pi_correction = (th_rule o prove) (`interval_arith (&2 * pi) (lo, hi) /\ a2 <= a1 + lo /\ b1 + hi <= b2 /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) ==> (?k. integer k /\ a2 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b2)`, REWRITE_TAC[interval_arith] THEN REPEAT STRIP_TAC THEN EXISTS_TAC `k + &1` THEN ASM_SIMP_TAC[INTEGER_ADD_EQ; INTEGER_CLOSED] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let a_pi_correction1, a_pi_correction2 = (pair_of_list o CONJUNCTS o th_rule o prove) (`interval_arith pi (lo, hi) /\ (a1 <= lo <=> F) ==> lo <= a1 /\ lo <= pi`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let ab_sum1_correction = (th_rule o prove) (`interval_arith (&2 * pi) (lo, hi) /\ m <= a1 + b1 /\ (lo <= m <=> T) /\ hi - lo <= t /\ b1 + t <= b2 ==> b1 <= b2 /\ &2 * pi <= a1 + b2`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let ab_sum2_correction = (th_rule o prove) (`interval_arith (&2 * pi) (lo, hi) /\ a1 + b1 <= n /\ (n <= lo <=> T) ==> a1 + b1 <= &2 * pi`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let ab_sum3_correction = (th_rule o prove) (`interval_arith (&2 * pi) (lo, hi) /\ hi - lo <= t /\ m <= a1 + b1 /\ a1 + b1 <= n /\ n - m <= r /\ (n <= lo <=> F) /\ r + t <= z /\ b1 + z <= b2 ==> b1 <= b2 /\ &2 * pi <= a1 + b2`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let ab_sum4_correction = (th_rule o prove) (`interval_arith (&2 * pi) (lo, hi) /\ m <= a1 + b1 /\ (hi <= m <=> T) ==> &2 * pi <= a1 + b1`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let a_b_correction = (th_rule o prove) (`a2 <= a1 /\ b1 <= b2 /\ (?k. integer k /\ a1 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b1) ==> (?k. integer k /\ a2 <= a + (&2 * pi) * k /\ b + (&2 * pi) * k <= b2)`, REPEAT STRIP_TAC THEN EXISTS_TAC `k:real` THEN ASM_REWRITE_TAC[] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; let a1_case1 = (th_rule o prove)(`(&0 <= a1 <=> T) /\ a1 <= pi ==> interval_arith a1 (&0, pi)`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let a1_case2 = (th_rule o prove)(`(&0 <= a1 <=> F) /\ --pi <= a1 ==> interval_arith a1 (--pi, &0)`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let b1_interval_0_pi_1 = (case_rule o prove) (`(&0 <= b1 <=> T) /\ b1 <= pi ==> interval_arith b1 (&0, pi)`, REWRITE_TAC[interval_arith]);; let b1_interval_0_pi_2 = (case_rule o prove) (`b1 <= pi /\ (&0 <= a1 <=> F) /\ b2 = --b1 /\ (a1 <= b2 <=> F) ==> interval_arith b1 (&0, pi)`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let b1_interval_pi_2pi = (case_rule o prove) (`&2 * pi <= a1 + b1 /\ a1 <= pi /\ b1 <= &2 * pi ==> interval_arith b1 (pi, &2 * pi)`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; let b1_interval_neg_pi_0 = (case_rule o prove) (`(b1 <= &0 <=> T) /\ (a1 <= b1 <=> T) /\ --pi <= a1 ==> interval_arith b1 (--pi, &0)`, REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; (* ------------------------------ *) (* Reduction procedures *) (* ------------------------------ *) (* Upper bound for x in [0, pi] *) let eval_high_0_pi pp x_0_pi x_tm = let pi2_th = pi2_approx_array.(pp) in let flag, ge_pi2 = float_prove_ge_interval x_tm pi2_th in if not flag then float_cos_high_raw pp x_tm else let pi_th = pi_approx_array.(pp) in let bounds = rand (concl pi_th) in let ltm, hi_tm = dest_comb bounds in let lo_tm = rand ltm in let hi_sub_x = float_sub_hi pp hi_tm x_tm in let t_tm = rand (concl hi_sub_x) in let flag, t_le_pi = float_prove_le_interval t_tm pi_th in if not flag then INST[x_tm, x_var_real] cos_high_trivial else let cos_t = float_cos_low_raw pp t_tm in let r_tm = rand (rator (concl cos_t)) in let high_eq = float_neg r_tm in let high_tm = rand (rator (concl high_eq)) in let th0 = INST[x_tm, x_var_real; high_tm, high_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real; r_tm, r_var_real; t_tm, t_var_real] reduction_high_0_pi in itlist MY_PROVE_HYP [high_eq; pi_th; x_0_pi; cos_t; t_le_pi; hi_sub_x] th0;; (* Lower bound for x in [0, pi] *) let eval_low_0_pi pp x_0_pi x_tm = let pi2_th = pi2_approx_array.(pp) in let flag, ge_pi2 = float_prove_ge_interval x_tm pi2_th in if not flag then float_cos_low_raw pp x_tm else let pi_th = pi_approx_array.(pp) in let bounds = rand (concl pi_th) in let ltm, hi_tm = dest_comb bounds in let lo_tm = rand ltm in let lo_sub_x = float_sub_lo pp lo_tm x_tm in let t_tm = rand (rator (concl lo_sub_x)) in let t_ge0 = float_ge0 t_tm in if (fst o dest_const o rand o concl) t_ge0 = "F" then INST[x_tm, x_var_real] cos_low_trivial else let cos_t = float_cos_high_raw pp t_tm in let r_tm = rand (concl cos_t) in let low_eq = float_neg r_tm in let low_tm = rand (rator (concl low_eq)) in let th0 = INST[x_tm, x_var_real; low_tm, low_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real; r_tm, r_var_real; t_tm, t_var_real] reduction_low_0_pi in itlist MY_PROVE_HYP [low_eq; pi_th; x_0_pi; cos_t; t_ge0; lo_sub_x] th0;; (* Upper bound for x in [-pi, 0] *) let eval_high_neg_pi_0 pp x_neg_pi_0 x_tm = let y_neg_x = float_neg x_tm in let y_tm = rand (rator (concl y_neg_x)) in let y_th0 = INST[x_tm, x_var_real; y_tm, y_var_real] interval_neg_pi_0 in let y_int_th = MY_PROVE_HYP y_neg_x (MY_PROVE_HYP x_neg_pi_0 y_th0) in let cos_y = eval_high_0_pi pp y_int_th y_tm in let high_tm = rand (concl cos_y) in let th0 = INST[x_tm, x_var_real; y_tm, y_var_real; high_tm, high_var_real] reduction_high_neg in MY_PROVE_HYP y_neg_x (MY_PROVE_HYP cos_y th0);; (* Lower bound for x in [-pi, 0] *) let eval_low_neg_pi_0 pp x_neg_pi_0 x_tm = let y_neg_x = float_neg x_tm in let y_tm = rand (rator (concl y_neg_x)) in let y_th0 = INST[x_tm, x_var_real; y_tm, y_var_real] interval_neg_pi_0 in let y_int_th = MY_PROVE_HYP y_neg_x (MY_PROVE_HYP x_neg_pi_0 y_th0) in let cos_y = eval_low_0_pi pp y_int_th y_tm in let low_tm = rand (rator (concl cos_y)) in let th0 = INST[x_tm, x_var_real; y_tm, y_var_real; low_tm, low_var_real] reduction_low_neg in MY_PROVE_HYP y_neg_x (MY_PROVE_HYP cos_y th0);; (* Upper bound for x in [pi, 2 * pi] *) let eval_high_pi_2pi pp x_pi_2pi x_tm = let _, (pi32_lo, _) = pi32_array.(pp) in let flag, le_pi32 = float_prove_le x_tm pi32_lo in if flag then (* x in [pi, 3/2 * pi] ==> consider (x - pi) *) let pi_th = pi_approx_array.(pp) in let bounds = rand (concl pi_th) in let ltm, hi_tm = dest_comb bounds in let lo_tm = rand ltm in let x_sub_lo = float_sub_hi pp x_tm lo_tm in let t_tm = rand (concl x_sub_lo) in let flag, t_le_pi = float_prove_le_interval t_tm pi_th in if not flag then INST[x_tm, x_var_real] cos_high_trivial else let cos_t = float_cos_low_raw pp t_tm in let r_tm = rand (rator (concl cos_t)) in let high_eq = float_neg r_tm in let high_tm = rand (rator (concl high_eq)) in let th0 = INST[x_tm, x_var_real; high_tm, high_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real; r_tm, r_var_real; t_tm, t_var_real] reduction_high_pi_2pi_2 in itlist MY_PROVE_HYP [high_eq; pi_th; x_pi_2pi; cos_t; t_le_pi; x_sub_lo] th0 else (* x in [3/2 * pi, pi] ==> consider (2 * pi - x) *) let two_pi, _, (lo_tm, hi_tm) = two_pi_array.(pp) in let lo_sub_x = float_sub_lo pp lo_tm x_tm in let t_tm = rand (rator (concl lo_sub_x)) in let t_ge0 = float_ge0 t_tm in if (fst o dest_const o rand o concl) t_ge0 = "F" then INST[x_tm, x_var_real] cos_high_trivial else let cos_t = float_cos_high_raw pp t_tm in let r_tm = rand (concl cos_t) in let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real; r_tm, r_var_real; t_tm, t_var_real] reduction_high_pi_2pi_1 in itlist MY_PROVE_HYP [t_ge0; x_pi_2pi; two_pi; lo_sub_x; cos_t] th0;; (* Lower bound for x in [pi, 2 * pi] *) let eval_low_pi_2pi pp x_pi_2pi x_tm = let _, (pi32_lo, _) = pi32_array.(pp) in let flag, le_pi32 = float_prove_le x_tm pi32_lo in if flag then (* x in [pi, 3/2 * pi] ==> consider (x - pi) *) let pi_th = pi_approx_array.(pp) in let bounds = rand (concl pi_th) in let ltm, hi_tm = dest_comb bounds in let lo_tm = rand ltm in let x_sub_hi = float_sub_lo pp x_tm hi_tm in let t_tm = rand (rator (concl x_sub_hi)) in let t_ge0 = float_ge0 t_tm in if (fst o dest_const o rand o concl) t_ge0 = "F" then INST[x_tm, x_var_real] cos_low_trivial else let cos_t = float_cos_high_raw pp t_tm in let r_tm = rand (concl cos_t) in let low_eq = float_neg r_tm in let low_tm = rand (rator (concl low_eq)) in let th0 = INST[x_tm, x_var_real; low_tm, low_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real; r_tm, r_var_real; t_tm, t_var_real] reduction_low_pi_2pi_2 in itlist MY_PROVE_HYP [low_eq; pi_th; x_pi_2pi; cos_t; t_ge0; x_sub_hi] th0 else (* x in [3/2 * pi, pi] ==> consider (2 * pi - x) *) let two_pi, _, (lo_tm, hi_tm) = two_pi_array.(pp) in let pi_th = pi_approx_array.(pp) in let hi_sub_x = float_sub_hi pp hi_tm x_tm in let t_tm = rand (concl hi_sub_x) in let flag, t_le_pi = float_prove_le_interval t_tm pi_th in if not flag then INST[x_tm, x_var_real] cos_low_trivial else let cos_t = float_cos_low_raw pp t_tm in let r_tm = rand (rator (concl cos_t)) in let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real; r_tm, r_var_real; t_tm, t_var_real] reduction_low_pi_2pi_1 in itlist MY_PROVE_HYP [t_le_pi; x_pi_2pi; two_pi; hi_sub_x; cos_t] th0;; (* ------------------------------ *) (* Interval reduction *) (* ------------------------------ *) exception Correction_failed;; let get_i f_tm = let x = float_of_float_tm f_tm in let k0 = -int_of_float (x /. f_2_pi) in let y = x +. float_of_int k0 *. f_2_pi in if y < -.f_pi then k0 + 1 else if y > f_pi then k0 - 1 else k0;; (* i = 0 *) (* a = f_tm *) (* i = 0 *) let reduction_zero a_tm b_tm = let th0 = INST[a_tm, a_var_real; b_tm, b_var_real] reduction_zero_th in a_tm, b_tm, th0;; (* i < 0 *) let reduction_neg pp i a_tm b_tm = let i_eq_th, i_num_tm = float_eq_th_of_num (Num.num_of_int (-i)) in let z_tm = rand (concl i_eq_th) in let two_pi_th, _, (lo_tm, hi_tm) = two_pi_array.(pp) in let lo_ge0_th = two_pi_low.(pp) in let z_hi_th = float_mul_hi pp z_tm hi_tm in let z_lo_th = float_mul_lo pp z_tm lo_tm in let m_tm = rand (concl z_hi_th) in let n_tm = rand (rator (concl z_lo_th)) in let a_sub_m_th = float_sub_lo pp a_tm m_tm in let b_sub_n_th = float_sub_hi pp b_tm n_tm in let a1_tm = rand (rator (concl a_sub_m_th)) in let b1_tm = rand (concl b_sub_n_th) in let th0 = INST[z_tm, z_var_real; i_num_tm, i_var_num; lo_tm, lo_var_real; hi_tm, hi_var_real; a_tm, a_var_real; a1_tm, a1_var_real; b_tm, b_var_real; b1_tm, b1_var_real; m_tm, m_var_real; n_tm, n_var_real] reduction_neg_th in let th1 = itlist MY_PROVE_HYP [i_eq_th; two_pi_th; lo_ge0_th; z_hi_th; z_lo_th; a_sub_m_th; b_sub_n_th] th0 in a1_tm, b1_tm, th1;; (* i > 0 *) let reduction_pos pp i a_tm b_tm = let i_eq_th, i_num_tm = float_eq_th_of_num (Num.num_of_int i) in let z_tm = rand (concl i_eq_th) in let two_pi_th, _, (lo_tm, hi_tm) = two_pi_array.(pp) in let lo_ge0_th = two_pi_low.(pp) in let z_lo_th = float_mul_lo pp z_tm lo_tm in let z_hi_th = float_mul_hi pp z_tm hi_tm in let m_tm = rand (rator (concl z_lo_th)) in let n_tm = rand (concl z_hi_th) in let a_add_m_th = float_add_lo pp a_tm m_tm in let b_add_n_th = float_add_hi pp b_tm n_tm in let a1_tm = rand (rator (concl a_add_m_th)) in let b1_tm = rand (concl b_add_n_th) in let th0 = INST[z_tm, z_var_real; i_num_tm, i_var_num; lo_tm, lo_var_real; hi_tm, hi_var_real; a_tm, a_var_real; a1_tm, a1_var_real; b_tm, b_var_real; b1_tm, b1_var_real; m_tm, m_var_real; n_tm, n_var_real] reduction_pos_th in let th1 = itlist MY_PROVE_HYP [i_eq_th; two_pi_th; lo_ge0_th; z_hi_th; z_lo_th; a_add_m_th; b_add_n_th] th0 in a1_tm, b1_tm, th1;; let correct_neg_pi pp red_th a_tm b_tm a1_tm b1_tm = let two_pi_th, _, (lo_tm, hi_tm) = two_pi_array.(pp) in let a1_add_lo_th = float_add_lo pp a1_tm lo_tm and b1_add_hi_th = float_add_hi pp b1_tm hi_tm in let a2_tm = rand (rator (concl a1_add_lo_th)) and b2_tm = rand (concl b1_add_hi_th) in let th0 = INST[a1_tm, a1_var_real; b1_tm, b1_var_real; a_tm, a_var_real; b_tm, b_var_real; a2_tm, a2_var_real; b2_tm, b2_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real] a_neg_pi_correction in let th1 = itlist MY_PROVE_HYP [red_th; two_pi_th; a1_add_lo_th; b1_add_hi_th] th0 in a2_tm, b2_tm, th1;; let correct_pi pp a1_tm neg_pi_le_a1_th = let pi_th = pi_approx_array.(pp) in let flag, le_th = float_prove_le_interval a1_tm pi_th in if flag then [], a1_tm, neg_pi_le_a1_th, le_th else let bounds = rand (concl pi_th) in let ltm, hi_tm = dest_comb bounds in let lo_tm = rand ltm in let inst = INST[lo_tm, lo_var_real; hi_tm, hi_var_real; a1_tm, a1_var_real] in let prove_hyp = MY_PROVE_HYP pi_th o MY_PROVE_HYP le_th in let th1 = prove_hyp (inst a_pi_correction1) and th2 = prove_hyp (inst a_pi_correction2) in [th1], lo_tm, neg_pi_le_pi_lo_array.(pp), th2;; (* TODO: use ab_sum1_correction to increase b and another result (similar to ab_sum3_correction) to decrease a *) let correct_ab_sum pp a1_tm b1_tm = let two_pi_th, sub_th, (lo_tm, hi_tm) = two_pi_array.(pp) in let a1_add_b1_hi = float_add_hi pp a1_tm b1_tm in let n_tm = rand (concl a1_add_b1_hi) in let flag, n_le_th = float_prove_le n_tm lo_tm in if flag then (* a1 + b1 <= 2 pi *) let th0 = INST[lo_tm, lo_var_real; hi_tm, hi_var_real; n_tm, n_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] ab_sum2_correction in let th1 = itlist MY_PROVE_HYP [two_pi_th; a1_add_b1_hi; n_le_th] th0 in -1, [], b1_tm, th1 else let a1_add_b1_lo = float_add_lo pp a1_tm b1_tm in let m_tm = rand (rator (concl a1_add_b1_lo)) in let flag, m_ge_th = float_prove_le hi_tm m_tm in if flag then (* a1 + b1 >= 2 pi *) let th0 = INST[lo_tm, lo_var_real; hi_tm, hi_var_real; m_tm, m_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] ab_sum4_correction in let th1 = itlist MY_PROVE_HYP [two_pi_th; a1_add_b1_lo; m_ge_th] th0 in 1, [], b1_tm, th1 else (* Find b2 >= b1 such that a1 + b2 >= 2 pi *) let t_tm = rand (concl sub_th) in let n_sub_m = float_sub_hi pp n_tm m_tm in let r_tm = rand (concl n_sub_m) in let r_add_t = float_add_hi pp r_tm t_tm in let z_tm = rand (concl r_add_t) in let b1_add_z = float_add_hi pp b1_tm z_tm in let b2_tm = rand (concl b1_add_z) in let th0 = INST[lo_tm, lo_var_real; hi_tm, hi_var_real; n_tm, n_var_real; m_tm, m_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real; t_tm, t_var_real; r_tm, r_var_real; z_tm, z_var_real; b2_tm, b2_var_real] ab_sum3_correction in let th1 = itlist MY_PROVE_HYP [two_pi_th; a1_add_b1_hi; a1_add_b1_lo; sub_th; n_sub_m; r_add_t; b1_add_z; n_le_th] th0 in let b1_le_b2, ge_2pi = pair_of_list (CONJUNCTS th1) in 1, [b1_le_b2], b2_tm, ge_2pi;; let correct_ab = let le_refl = SPEC_ALL REAL_LE_REFL in fun red_th a_tm b_tm a1_tm b1_tm a1_le0 b1_le0 -> if a1_le0 = [] && b1_le0 = [] then red_th else let a2_le_a1 = match a1_le0 with | le_th :: _ -> le_th | [] -> INST[a1_tm, x_var_real] le_refl in let b1_le_b2 = match b1_le0 with | le_th :: _ -> le_th | [] -> INST[b1_tm, x_var_real] le_refl in let a2_tm, a1_tm = dest_binary "real_le" (concl a2_le_a1) and b1_tm, b2_tm = dest_binary "real_le" (concl b1_le_b2) in let th0 = INST[a1_tm, a1_var_real; b1_tm, b1_var_real; a2_tm, a2_var_real; b2_tm, b2_var_real; a_tm, a_var_real; b_tm, b_var_real] a_b_correction in itlist MY_PROVE_HYP [red_th; a2_le_a1; b1_le_b2] th0;; (* ----------------------------------- *) (* The main evaluation function *) (* ----------------------------------- *) let float_interval_cos pp x_th = let x_tm, bounds = dest_interval_arith (concl x_th) in let ltm, b_tm = dest_comb bounds in let a_tm = rand ltm in try (* Reduce the interval of x *) let i = get_i a_tm in let a1_tm, b1_tm, red_th = if i = 0 then reduction_zero a_tm b_tm else if i < 0 then reduction_neg pp i a_tm b_tm else reduction_pos pp i a_tm b_tm in (* Prove -pi <= a1; otherwise correct the value of a1 *) let neg_pi_th = neg_pi_array.(pp) in let flag, le_th = float_prove_ge_interval a1_tm neg_pi_th in let a1_tm, b1_tm, red_th, neg_pi_le_a1_th = if flag then a1_tm, b1_tm, red_th, le_th else let a1_tm', b1_tm', red_th' = correct_neg_pi pp red_th a_tm b_tm a1_tm b1_tm in let flag, le_th = float_prove_ge_interval a1_tm' neg_pi_th in let _ = if not flag then raise Correction_failed in a1_tm', b1_tm', red_th', le_th in (* Make sure that a1 <= pi *) let a1_le0, a1_tm, neg_pi_le_a1_th, a1_le_pi_th = correct_pi pp a1_tm neg_pi_le_a1_th in let a1_0_th = float_ge0 a1_tm in let a1_case, a1_case_th = let inst = MY_PROVE_HYP a1_0_th o INST[a1_tm, a1_var_real] in if (fst o dest_const o rand o concl) a1_0_th = "T" then 1, MY_PROVE_HYP a1_le_pi_th (inst a1_case1) else -1, MY_PROVE_HYP neg_pi_le_a1_th (inst a1_case2) in (* Consider cases: 1) a1 in [0, pi], 2) a1 in [-pi, 0] *) if a1_case > 0 then (* a1 in [0, pi] *) let ab_sum_case, b1_le0, b1_tm, ab_sum_th = correct_ab_sum pp a1_tm b1_tm in let red_th = correct_ab red_th a_tm b_tm a1_tm b1_tm a1_le0 b1_le0 in let inst_tms = [x_tm, x_var_real; a_tm, a_var_real; b_tm, b_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] in let flag_b_pi, b_le_pi = float_prove_le_interval b1_tm pi_approx_array.(pp) in let two_pi_th, _, _ = two_pi_array.(pp) in let flag_b_2pi, b_le_2pi = float_prove_le_interval b1_tm two_pi_th in if flag_b_pi then (* b1 in [0, pi] *) let b1_ge0 = float_ge0 b1_tm in let b1_int = let th0 = INST[b1_tm, b1_var_real] b1_interval_0_pi_1 in MY_PROVE_HYP b1_ge0 (MY_PROVE_HYP b_le_pi th0) in let cos_b1 = eval_low_0_pi pp b1_int b1_tm and cos_a1 = eval_high_0_pi pp a1_case_th a1_tm in let low_tm = rand (rator (concl cos_b1)) and high_tm = rand (concl cos_a1) in let th0 = INST ([low_tm, low_var_real; high_tm, high_var_real] @ inst_tms) cos_case0 in itlist MY_PROVE_HYP [red_th; a1_case_th; b_le_pi; x_th; cos_b1; cos_a1] th0 else if ab_sum_case < 0 then (* a1 + b1 <= 2 * pi *) let cos_a1 = eval_high_0_pi pp a1_case_th a1_tm in let high_tm = rand (concl cos_a1) in let th0 = INST ([high_tm, high_var_real] @ inst_tms) cos_case2 in itlist MY_PROVE_HYP [red_th; a1_case_th; ab_sum_th; x_th; cos_a1] th0 else if ab_sum_case > 0 && flag_b_2pi then (* a1 + b1 >= 2 * pi /\ b1 <= 2 * pi ==> b1 in [pi, 2 * pi] *) let b1_int = let th0 = INST[b1_tm, b1_var_real; a1_tm, a1_var_real] b1_interval_pi_2pi in MY_PROVE_HYP ab_sum_th (MY_PROVE_HYP a1_le_pi_th (MY_PROVE_HYP b_le_2pi th0)) in let cos_b1 = eval_high_pi_2pi pp b1_int b1_tm in let high_tm = rand (concl cos_b1) in let th0 = INST ([high_tm, high_var_real] @ inst_tms) cos_case3 in itlist MY_PROVE_HYP [red_th; a1_case_th; b_le_2pi; ab_sum_th; x_th; cos_b1] th0 else INST[x_tm, x_var_real] cos_case_neg1 else (* a1 in [-pi, 0] *) let inst_tms = [x_tm, x_var_real; a_tm, a_var_real; b_tm, b_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] in let b1_0 = float_le0 b1_tm in if (fst o dest_const o rand o concl) b1_0 = "T" then (* b1 <= 0 ==> b1 in [-pi, 0] *) let b1_int = let th0 = INST[b1_tm, b1_var_real; a1_tm, a1_var_real] b1_interval_neg_pi_0 in let a1_le_b1 = float_le a1_tm b1_tm in MY_PROVE_HYP a1_le_b1 (MY_PROVE_HYP b1_0 (MY_PROVE_HYP neg_pi_le_a1_th th0)) in let cos_a1 = eval_low_neg_pi_0 pp a1_case_th a1_tm and cos_b1 = eval_high_neg_pi_0 pp b1_int b1_tm in let low_tm = rand (rator (concl cos_a1)) and high_tm = rand (concl cos_b1) in let th0 = INST ([low_tm, low_var_real; high_tm, high_var_real] @ inst_tms) cos_case4 in itlist MY_PROVE_HYP [red_th; a1_case_th; b1_0; x_th; cos_a1; cos_b1] th0 else (* b1 >= 0 *) let neg_b_eq = float_neg b1_tm in let b2_tm = rand (rator (concl neg_b_eq)) in let ab_cmp = float_le a1_tm b2_tm in if (fst o dest_const o rand o concl) ab_cmp = "T" then (* a1 <= --b1 *) let cos_a1 = eval_low_neg_pi_0 pp a1_case_th a1_tm in let low_tm = rand (rator (concl cos_a1)) in let th0 = INST ([b2_tm, b2_var_real; low_tm, low_var_real] @ inst_tms) cos_case6 in itlist MY_PROVE_HYP [red_th; a1_case_th; neg_b_eq; ab_cmp; x_th; cos_a1] th0 else (* a1 >= --b1 *) let flag_b_pi, b_le_pi = float_prove_le_interval b1_tm pi_approx_array.(pp) in if flag_b_pi then (* b1 <= pi ==> b1 in [0, pi] *) let b1_int = let th0 = INST[b1_tm, b1_var_real; a1_tm, a1_var_real; b2_tm, b2_var_real] b1_interval_0_pi_2 in itlist MY_PROVE_HYP [b_le_pi; a1_0_th; neg_b_eq; ab_cmp] th0 in let cos_b1 = eval_low_0_pi pp b1_int b1_tm in let low_tm = rand (rator (concl cos_b1)) in let th0 = INST ([b2_tm, b2_var_real; low_tm, low_var_real] @ inst_tms) cos_case7 in itlist MY_PROVE_HYP [red_th; a1_case_th; neg_b_eq; ab_cmp; b_le_pi; x_th; cos_b1] th0 else INST[x_tm, x_var_real] cos_case_neg1 with Correction_failed -> let _ = warn true (Printf.sprintf "float_interval_cos: reduction failed (%s, %s)" (string_of_term a_tm) (string_of_term b_tm)) in INST[x_tm, x_var_real] cos_case_neg1;; end;; (* (************) let x_int = float_interval_mul 10 (mk_float_interval_small_num 33) pi_approx_array.(10);; float_interval_cos 5 x_int;; let y_int = (ASSUME o mk_interval `x:real` o mk_pair) (mk_float (-100) 0, mk_float (-99) 0);; float_interval_cos 5 y_int;; test 100 (float_interval_cos 10) x_int;; (************) let a_tm = mk_float (int_of_float (-.(f_pi +. f_2_pi +. 0.0001) *. 10. ** 10.)) (-10);; let b_tm = mk_float (-9) 0;; let a_tm = mk_float (int_of_float ((f_pi +. f_2_pi +. 0.0001) *. 10. ** 10.)) (-10);; let b_tm = mk_float 10 0;; let a_tm = mk_float (int_of_float ((-.f_pi /. 2.0 +. f_2_pi +. 0.0001) *. 10. ** 10.)) (-10);; let b_tm = mk_float 10 0;; let a_tm = mk_float (int_of_float ((-.f_pi) *. 10. ** 10.)) (-10);; let b_tm = a_tm;; let a_tm = mk_float 1 0;; let b_tm = mk_float (int_of_float ((f_2_pi -. 1.0) *. 10. ** 10.)) (-10);; let pp = 5;; reduce_cos 10 a_tm b_tm;; test 1000 (reduce_cos 10 a_tm) b_tm;; (**************) let x_tm = mk_float 62 (-1);; let a_th = (INST[x_tm, x_var_real] o ASSUME) `interval_arith x (&0, pi)`;; let b_th = (INST[x_tm, x_var_real] o ASSUME) `interval_arith x (--pi, &0)`;; let c_th = (INST[x_tm, x_var_real] o ASSUME) `interval_arith x (pi, &2 * pi)`;; eval_low_pi_2pi 10 c_th x_tm;; eval_high_0_pi 5 a_th x_tm;; eval_high_pi_2pi 5 c_th x_tm;; float_cos_high_raw 2 x_tm;; eval_low_0_pi 6 a_th x_tm;; eval_high_neg_pi_0 4 b_th x_tm;; eval_low_neg_pi_0 3 b_th x_tm;; eval_low_0_pi 3 a_th x_tm;; eval_high_0_pi 4 a_th x_tm;; float_neg (mk_float 1 0);; ;; (**************) let i = get_i a_tm;; let a1_tm, b1_tm, red_th = if i = 0 then reduction_zero a_tm b_tm else if i < 0 then reduction_neg pp i a_tm b_tm else reduction_pos pp i a_tm b_tm;; (* Prove -pi <= a1; otherwise correct the value of a1 *) let neg_pi_th = neg_pi_array.(pp);; let flag, le_th = float_prove_ge_interval a1_tm neg_pi_th;; let a1_tm, b1_tm, red_th, neg_pi_le_a1_th = if flag then a1_tm, b1_tm, red_th, le_th else let a1_tm', b1_tm', red_th' = correct_neg_pi pp red_th a_tm b_tm a1_tm b1_tm in let flag, le_th = float_prove_ge_interval a1_tm' neg_pi_th in let _ = if not flag then raise Correction_failed in a1_tm', b1_tm', red_th', le_th;; let a1_le0, a1_tm, neg_pi_le_a1_th, a1_le_pi_th = correct_pi pp a1_tm neg_pi_le_a1_th;; let a1_0_th = float_ge0 a1_tm;; let a1_case, a1_case_th = let inst = MY_PROVE_HYP a1_0_th o INST[a1_tm, a1_var_real] in if (fst o dest_const o rand o concl) a1_0_th = "T" then 1, MY_PROVE_HYP a1_le_pi_th (inst a1_case1) else -1, MY_PROVE_HYP neg_pi_le_a1_th (inst a1_case2);; (* a1_case > 0 *) let ab_sum_case, b1_le0, b1_tm, ab_sum_th = correct_ab_sum pp a1_tm b1_tm;; let red_th = correct_ab red_th a_tm b_tm a1_tm b1_tm a1_le0 b1_le0 in let inst_tms = INST[a_tm, a_var_real; b_tm, b_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] in let flag_b_pi, b_le_pi = float_prove_le_interval b1_tm pi_approx_array.(pp) in let flag_b_2pi, b_le_2pi = float_prove_le_interval b1_tm two_pi_th in if flag_b_pi then let th0 = inst_tms cos_case0 in 0, itlist MY_PROVE_HYP [red_th; a1_case_th; b_le_pi] th0 else if ab_sum_case < 0 then let th0 = inst_tms cos_case2 in 2, itlist MY_PROVE_HYP [red_th; a1_case_th; ab_sum_th] th0 else if ab_sum_case > 0 && flag_b_2pi then let th0 = inst_tms cos_case3 in 3, itlist MY_PROVE_HYP [red_th; a1_case_th; b_le_2pi; ab_sum_th] th0 else -1, cos_case_neg1;; (* a1_case < 0 *) else let inst_tms = [a_tm, a_var_real; b_tm, b_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] in let b1_0 = float_le0 b1_tm in if (fst o dest_const o rand o concl) b1_0 = "T" then let th0 = INST inst_tms cos_case4 in 4, itlist MY_PROVE_HYP [red_th; a1_case_th; b1_0] th0 else let neg_b_eq = float_neg b1_tm in let neg_b_tm = rand (rator (concl neg_b_eq)) in let ab_cmp = float_le a1_tm neg_b_tm in if (fst o dest_const o rand o concl) ab_cmp = "T" then let th0 = INST ((neg_b_tm, b2_var_real) :: inst_tms) cos_case6 in 6, itlist MY_PROVE_HYP [red_th; a1_case_th; neg_b_eq; ab_cmp] th0 else let flag_b_pi, b_le_pi = float_prove_le_interval b1_tm pi_approx_array.(pp) in if flag_b_pi then let th0 = INST ((neg_b_tm, b2_var_real) :: inst_tms) cos_case7 in 7, itlist MY_PROVE_HYP [red_th; a1_case_th; neg_b_eq; ab_cmp; b_le_pi] th0 else -1, cos_case_neg1 with Correction_failed -> let _ = warn true (Printf.sprintf "cos_reduction: reduction failed (%s, %s)" (string_of_term a_tm) (string_of_term b_tm)) in -1, cos_case_neg1;; let two_pi_th, sub_th, (lo_tm, hi_tm) = two_pi_array.(pp);; let a1_add_b1_hi = float_add_hi pp a1_tm b1_tm;; let n_tm = rand (concl a1_add_b1_hi);; let flag, n_le_th = float_prove_le n_tm lo_tm;; if flag then let th0 = INST[lo_tm, lo_var_real; hi_tm, hi_var_real; n_tm, n_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] ab_sum2_correction in let th1 = itlist MY_PROVE_HYP [two_pi_th; a1_add_b1_hi; n_le_th] th0 in -1, [], b1_tm, th1 else let t_tm = rand (concl sub_th) in let a1_add_b1_lo = float_add_lo pp a1_tm b1_tm in let m_tm = rand (rator (concl a1_add_b1_lo)) in let n_sub_m = float_sub_hi pp n_tm m_tm in let r_tm = rand (concl n_sub_m) in let r_add_t = float_add_hi pp r_tm t_tm in let z_tm = rand (concl r_add_t) in let b1_add_z = float_add_hi pp b1_tm z_tm in let b2_tm = rand (concl b1_add_z) in let th0 = INST[lo_tm, lo_var_real; hi_tm, hi_var_real; n_tm, n_var_real; m_tm, m_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real; t_tm, t_var_real; r_tm, r_var_real; z_tm, z_var_real; b2_tm, b2_var_real] ab_sum3_correction in let th1 = itlist MY_PROVE_HYP [two_pi_th; a1_add_b1_hi; a1_add_b1_lo; sub_th; n_sub_m; r_add_t; b1_add_z; n_le_th] th0 in let b1_le_b2, ge_2pi = pair_of_list (CONJUNCTS th1) in 1, [b1_le_b2], b2_tm, ge_2pi;; let reduce_cos pp a_tm b_tm = try let i = get_i a_tm in let a1_tm, b1_tm, red_th = if i = 0 then reduction_zero a_tm b_tm else if i < 0 then reduction_neg pp i a_tm b_tm else reduction_pos pp i a_tm b_tm in (* Prove -pi <= a1; otherwise correct the value of a1 *) let neg_pi_th = neg_pi_array.(pp) in let flag, le_th = float_prove_ge_interval a1_tm neg_pi_th in let a1_tm, b1_tm, red_th, neg_pi_le_a1_th = if flag then a1_tm, b1_tm, red_th, le_th else let a1_tm', b1_tm', red_th' = correct_neg_pi pp red_th a_tm b_tm a1_tm b1_tm in let flag, le_th = float_prove_ge_interval a1_tm' neg_pi_th in let _ = if not flag then raise Correction_failed in a1_tm', b1_tm', red_th', le_th in let a1_le0, a1_tm, neg_pi_le_a1_th, a1_le_pi_th = correct_pi pp a1_tm neg_pi_le_a1_th in let a1_0_th = float_ge0 a1_tm in let a1_case, a1_case_th = let inst = MY_PROVE_HYP a1_0_th o INST[a1_tm, a1_var_real] in if (fst o dest_const o rand o concl) a1_0_th = "T" then 1, MY_PROVE_HYP a1_le_pi_th (inst a1_case1) else -1, MY_PROVE_HYP neg_pi_le_a1_th (inst a1_case2) in if a1_case > 0 then let ab_sum_case, b1_le0, b1_tm, ab_sum_th = correct_ab_sum pp a1_tm b1_tm in let red_th = correct_ab red_th a_tm b_tm a1_tm b1_tm a1_le0 b1_le0 in let inst_tms = INST[a_tm, a_var_real; b_tm, b_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] in let flag_b_pi, b_le_pi = float_prove_le_interval b1_tm pi_approx_array.(pp) in let two_pi_th, _, _ = two_pi_array.(pp) in let flag_b_2pi, b_le_2pi = float_prove_le_interval b1_tm two_pi_th in if flag_b_pi then let th0 = inst_tms cos_case0 in 0, itlist MY_PROVE_HYP [red_th; a1_case_th; b_le_pi] th0 else if ab_sum_case < 0 then let th0 = inst_tms cos_case2 in 2, itlist MY_PROVE_HYP [red_th; a1_case_th; ab_sum_th] th0 else if ab_sum_case > 0 && flag_b_2pi then let th0 = inst_tms cos_case3 in 3, itlist MY_PROVE_HYP [red_th; a1_case_th; b_le_2pi; ab_sum_th] th0 else -1, cos_case_neg1 else let inst_tms = [a_tm, a_var_real; b_tm, b_var_real; a1_tm, a1_var_real; b1_tm, b1_var_real] in let b1_0 = float_le0 b1_tm in if (fst o dest_const o rand o concl) b1_0 = "T" then let th0 = INST inst_tms cos_case4 in 4, itlist MY_PROVE_HYP [red_th; a1_case_th; b1_0] th0 else let neg_b_eq = float_neg b1_tm in let neg_b_tm = rand (rator (concl neg_b_eq)) in let ab_cmp = float_le a1_tm neg_b_tm in if (fst o dest_const o rand o concl) ab_cmp = "T" then let th0 = INST ((neg_b_tm, b2_var_real) :: inst_tms) cos_case6 in 6, itlist MY_PROVE_HYP [red_th; a1_case_th; neg_b_eq; ab_cmp] th0 else let flag_b_pi, b_le_pi = float_prove_le_interval b1_tm pi_approx_array.(pp) in if flag_b_pi then let th0 = INST ((neg_b_tm, b2_var_real) :: inst_tms) cos_case7 in 7, itlist MY_PROVE_HYP [red_th; a1_case_th; neg_b_eq; ab_cmp; b_le_pi] th0 else -1, cos_case_neg1 with Correction_failed -> let _ = warn true (Printf.sprintf "cos_reduction: reduction failed (%s, %s)" (string_of_term a_tm) (string_of_term b_tm)) in -1, cos_case_neg1;; *)