src/HOL/Decision_Procs/Approximation.thy
changeset 63040 eb4ddd18d635
parent 62390 842917225d56
child 63170 eae6549dbea2
equal deleted inserted replaced
63039:1a20fd9cf281 63040:eb4ddd18d635
  2397 lemma ln_shifted_float:
  2397 lemma ln_shifted_float:
  2398   assumes "0 < m"
  2398   assumes "0 < m"
  2399   shows "ln (Float m e) = ln 2 * (e + (bitlen m - 1)) + ln (Float m (- (bitlen m - 1)))"
  2399   shows "ln (Float m e) = ln 2 * (e + (bitlen m - 1)) + ln (Float m (- (bitlen m - 1)))"
  2400 proof -
  2400 proof -
  2401   let ?B = "2^nat (bitlen m - 1)"
  2401   let ?B = "2^nat (bitlen m - 1)"
  2402   def bl \<equiv> "bitlen m - 1"
  2402   define bl where "bl = bitlen m - 1"
  2403   have "0 < real_of_int m" and "\<And>X. (0 :: real) < 2^X" and "0 < (2 :: real)" and "m \<noteq> 0"
  2403   have "0 < real_of_int m" and "\<And>X. (0 :: real) < 2^X" and "0 < (2 :: real)" and "m \<noteq> 0"
  2404     using assms by auto
  2404     using assms by auto
  2405   hence "0 \<le> bl" by (simp add: bitlen_def bl_def)
  2405   hence "0 \<le> bl" by (simp add: bitlen_def bl_def)
  2406   show ?thesis
  2406   show ?thesis
  2407   proof (cases "0 \<le> e")
  2407   proof (cases "0 \<le> e")
  2526   case False
  2526   case False
  2527   hence "\<not> x \<le> 0" and "\<not> x < 1" "0 < x" "\<not> x \<le> Float 3 (- 1)"
  2527   hence "\<not> x \<le> 0" and "\<not> x < 1" "0 < x" "\<not> x \<le> Float 3 (- 1)"
  2528     using \<open>1 \<le> x\<close> by auto
  2528     using \<open>1 \<le> x\<close> by auto
  2529   show ?thesis
  2529   show ?thesis
  2530   proof -
  2530   proof -
  2531     def m \<equiv> "mantissa x"
  2531     define m where "m = mantissa x"
  2532     def e \<equiv> "exponent x"
  2532     define e where "e = exponent x"
  2533     from Float_mantissa_exponent[of x] have Float: "x = Float m e"
  2533     from Float_mantissa_exponent[of x] have Float: "x = Float m e"
  2534       by (simp add: m_def e_def)
  2534       by (simp add: m_def e_def)
  2535     let ?s = "Float (e + (bitlen m - 1)) 0"
  2535     let ?s = "Float (e + (bitlen m - 1)) 0"
  2536     let ?x = "Float m (- (bitlen m - 1))"
  2536     let ?x = "Float m (- (bitlen m - 1))"
  2537 
  2537 
  2538     have "0 < m" and "m \<noteq> 0" using \<open>0 < x\<close> Float powr_gt_zero[of 2 e]
  2538     have "0 < m" and "m \<noteq> 0" using \<open>0 < x\<close> Float powr_gt_zero[of 2 e]
  2539       apply (auto simp add: zero_less_mult_iff)
  2539       apply (auto simp add: zero_less_mult_iff)
  2540       using not_le powr_ge_pzero apply blast
  2540       using not_le powr_ge_pzero apply blast
  2541       done
  2541       done
  2542     def bl \<equiv> "bitlen m - 1"
  2542     define bl where "bl = bitlen m - 1"
  2543     hence "bl \<ge> 0"
  2543     hence "bl \<ge> 0"
  2544       using \<open>m > 0\<close> by (simp add: bitlen_def)
  2544       using \<open>m > 0\<close> by (simp add: bitlen_def)
  2545     have "1 \<le> Float m e"
  2545     have "1 \<le> Float m e"
  2546       using \<open>1 \<le> x\<close> Float unfolding less_eq_float_def by auto
  2546       using \<open>1 \<le> x\<close> Float unfolding less_eq_float_def by auto
  2547     from bitlen_div[OF \<open>0 < m\<close>] float_gt1_scale[OF \<open>1 \<le> Float m e\<close>] \<open>bl \<ge> 0\<close>
  2547     from bitlen_div[OF \<open>0 < m\<close>] float_gt1_scale[OF \<open>1 \<le> Float m e\<close>] \<open>bl \<ge> 0\<close>
  2744   proof cases
  2744   proof cases
  2745     assume "l1 = 0" "u1 = 0"
  2745     assume "l1 = 0" "u1 = 0"
  2746     with x lu show ?thesis by (auto simp: bnds_powr_def)
  2746     with x lu show ?thesis by (auto simp: bnds_powr_def)
  2747   next
  2747   next
  2748     assume A: "l1 = 0" "u1 \<noteq> 0" "l2 \<ge> 1"
  2748     assume A: "l1 = 0" "u1 \<noteq> 0" "l2 \<ge> 1"
  2749     def uln \<equiv> "the (ub_ln prec u1)"
  2749     define uln where "uln = the (ub_ln prec u1)"
  2750     show ?thesis
  2750     show ?thesis
  2751     proof (cases "x = 0")
  2751     proof (cases "x = 0")
  2752       case False
  2752       case False
  2753       with A x y have "x powr y = exp (ln x * y)" by (simp add: powr_def)
  2753       with A x y have "x powr y = exp (ln x * y)" by (simp add: powr_def)
  2754       also {
  2754       also {
  3967     hence setprod_head_Suc: "\<And>k i. \<Prod>{k ..< k + Suc i} = k * \<Prod>{Suc k ..< Suc k + i}"
  3967     hence setprod_head_Suc: "\<And>k i. \<Prod>{k ..< k + Suc i} = k * \<Prod>{Suc k ..< Suc k + i}"
  3968       by auto
  3968       by auto
  3969     have setsum_move0: "\<And>k F. setsum F {0..<Suc k} = F 0 + setsum (\<lambda> k. F (Suc k)) {0..<k}"
  3969     have setsum_move0: "\<And>k F. setsum F {0..<Suc k} = F 0 + setsum (\<lambda> k. F (Suc k)) {0..<k}"
  3970       unfolding setsum_shift_bounds_Suc_ivl[symmetric]
  3970       unfolding setsum_shift_bounds_Suc_ivl[symmetric]
  3971       unfolding setsum_head_upt_Suc[OF zero_less_Suc] ..
  3971       unfolding setsum_head_upt_Suc[OF zero_less_Suc] ..
  3972     def C \<equiv> "xs!x - c"
  3972     define C where "C = xs!x - c"
  3973 
  3973 
  3974     {
  3974     {
  3975       fix t::real assume t: "t \<in> {lx .. ux}"
  3975       fix t::real assume t: "t \<in> {lx .. ux}"
  3976       hence "bounded_by [xs!x] [vs!x]"
  3976       hence "bounded_by [xs!x] [vs!x]"
  3977         using \<open>bounded_by xs vs\<close>[THEN bounded_byE, OF \<open>x < length vs\<close>]
  3977         using \<open>bounded_by xs vs\<close>[THEN bounded_byE, OF \<open>x < length vs\<close>]
  4004     and bnd_c: "real_of_float c \<in> {lx .. ux}"
  4004     and bnd_c: "real_of_float c \<in> {lx .. ux}"
  4005     and "x < length vs" and "x < length xs"
  4005     and "x < length vs" and "x < length xs"
  4006     and ate: "Some (l, u) = approx_tse prec x s c 1 f vs"
  4006     and ate: "Some (l, u) = approx_tse prec x s c 1 f vs"
  4007   shows "interpret_floatarith f xs \<in> {l .. u}"
  4007   shows "interpret_floatarith f xs \<in> {l .. u}"
  4008 proof -
  4008 proof -
  4009   def F \<equiv> "\<lambda>n z. interpret_floatarith ((DERIV_floatarith x ^^ n) f) (xs[x := z])"
  4009   define F where [abs_def]: "F n z =
       
  4010     interpret_floatarith ((DERIV_floatarith x ^^ n) f) (xs[x := z])" for n z
  4010   hence F0: "F 0 = (\<lambda> z. interpret_floatarith f (xs[x := z]))" by auto
  4011   hence F0: "F 0 = (\<lambda> z. interpret_floatarith f (xs[x := z]))" by auto
  4011 
  4012 
  4012   hence "bounded_by (xs[x := c]) vs" and "x < length vs" "x < length xs"
  4013   hence "bounded_by (xs[x := c]) vs" and "x < length vs" "x < length xs"
  4013     using \<open>bounded_by xs vs\<close> bnd_x bnd_c \<open>x < length vs\<close> \<open>x < length xs\<close>
  4014     using \<open>bounded_by xs vs\<close> bnd_x bnd_c \<open>x < length vs\<close> \<open>x < length xs\<close>
  4014     by (auto intro!: bounded_by_update_var)
  4015     by (auto intro!: bounded_by_update_var)