100 (is "?lb") |
100 (is "?lb") |
101 and "(\<Sum>j=0..<n. (- 1) ^ j * (1 / (f (j' + j))) * (x ^ j)) \<le> (ub n ((F ^^ j') s) (f j') x)" |
101 and "(\<Sum>j=0..<n. (- 1) ^ j * (1 / (f (j' + j))) * (x ^ j)) \<le> (ub n ((F ^^ j') s) (f j') x)" |
102 (is "?ub") |
102 (is "?ub") |
103 proof - |
103 proof - |
104 have "?lb \<and> ?ub" |
104 have "?lb \<and> ?ub" |
105 using horner_bounds'[where lb=lb, OF \<open>0 \<le> real x\<close> f_Suc lb_0 lb_Suc ub_0 ub_Suc] |
105 using horner_bounds'[where lb=lb, OF \<open>0 \<le> real_of_float x\<close> f_Suc lb_0 lb_Suc ub_0 ub_Suc] |
106 unfolding horner_schema[where f=f, OF f_Suc] . |
106 unfolding horner_schema[where f=f, OF f_Suc] by simp |
107 thus "?lb" and "?ub" by auto |
107 thus "?lb" and "?ub" by auto |
108 qed |
108 qed |
109 |
109 |
110 lemma horner_bounds_nonpos: |
110 lemma horner_bounds_nonpos: |
111 fixes F :: "nat \<Rightarrow> nat" and G :: "nat \<Rightarrow> nat \<Rightarrow> nat" |
111 fixes F :: "nat \<Rightarrow> nat" and G :: "nat \<Rightarrow> nat \<Rightarrow> nat" |
112 assumes "real x \<le> 0" and f_Suc: "\<And>n. f (Suc n) = G ((F ^^ n) s) (f n)" |
112 assumes "real_of_float x \<le> 0" and f_Suc: "\<And>n. f (Suc n) = G ((F ^^ n) s) (f n)" |
113 and lb_0: "\<And> i k x. lb 0 i k x = 0" |
113 and lb_0: "\<And> i k x. lb 0 i k x = 0" |
114 and lb_Suc: "\<And> n i k x. lb (Suc n) i k x = float_plus_down prec |
114 and lb_Suc: "\<And> n i k x. lb (Suc n) i k x = float_plus_down prec |
115 (lapprox_rat prec 1 k) |
115 (lapprox_rat prec 1 k) |
116 (float_round_down prec (x * (ub n (F i) (G i k) x)))" |
116 (float_round_down prec (x * (ub n (F i) (G i k) x)))" |
117 and ub_0: "\<And> i k x. ub 0 i k x = 0" |
117 and ub_0: "\<And> i k x. ub 0 i k x = 0" |
118 and ub_Suc: "\<And> n i k x. ub (Suc n) i k x = float_plus_up prec |
118 and ub_Suc: "\<And> n i k x. ub (Suc n) i k x = float_plus_up prec |
119 (rapprox_rat prec 1 k) |
119 (rapprox_rat prec 1 k) |
120 (float_round_up prec (x * (lb n (F i) (G i k) x)))" |
120 (float_round_up prec (x * (lb n (F i) (G i k) x)))" |
121 shows "(lb n ((F ^^ j') s) (f j') x) \<le> (\<Sum>j=0..<n. (1 / (f (j' + j))) * real x ^ j)" (is "?lb") |
121 shows "(lb n ((F ^^ j') s) (f j') x) \<le> (\<Sum>j=0..<n. (1 / (f (j' + j))) * real_of_float x ^ j)" (is "?lb") |
122 and "(\<Sum>j=0..<n. (1 / (f (j' + j))) * real x ^ j) \<le> (ub n ((F ^^ j') s) (f j') x)" (is "?ub") |
122 and "(\<Sum>j=0..<n. (1 / (f (j' + j))) * real_of_float x ^ j) \<le> (ub n ((F ^^ j') s) (f j') x)" (is "?ub") |
123 proof - |
123 proof - |
124 have diff_mult_minus: "x - y * z = x + - y * z" for x y z :: float by simp |
124 have diff_mult_minus: "x - y * z = x + - y * z" for x y z :: float by simp |
125 have sum_eq: "(\<Sum>j=0..<n. (1 / (f (j' + j))) * real x ^ j) = |
125 have sum_eq: "(\<Sum>j=0..<n. (1 / (f (j' + j))) * real_of_float x ^ j) = |
126 (\<Sum>j = 0..<n. (- 1) ^ j * (1 / (f (j' + j))) * real (- x) ^ j)" |
126 (\<Sum>j = 0..<n. (- 1) ^ j * (1 / (f (j' + j))) * real_of_float (- x) ^ j)" |
127 by (auto simp add: field_simps power_mult_distrib[symmetric]) |
127 by (auto simp add: field_simps power_mult_distrib[symmetric]) |
128 have "0 \<le> real (-x)" using assms by auto |
128 have "0 \<le> real_of_float (-x)" using assms by auto |
129 from horner_bounds[where G=G and F=F and f=f and s=s and prec=prec |
129 from horner_bounds[where G=G and F=F and f=f and s=s and prec=prec |
130 and lb="\<lambda> n i k x. lb n i k (-x)" and ub="\<lambda> n i k x. ub n i k (-x)", |
130 and lb="\<lambda> n i k x. lb n i k (-x)" and ub="\<lambda> n i k x. ub n i k (-x)", |
131 unfolded lb_Suc ub_Suc diff_mult_minus, |
131 unfolded lb_Suc ub_Suc diff_mult_minus, |
132 OF this f_Suc lb_0 _ ub_0 _] |
132 OF this f_Suc lb_0 _ ub_0 _] |
133 show "?lb" and "?ub" unfolding minus_minus sum_eq |
133 show "?lb" and "?ub" unfolding minus_minus sum_eq |
318 finally show ?case |
318 finally show ?case |
319 unfolding sqrt_iteration.simps Let_def distrib_left . |
319 unfolding sqrt_iteration.simps Let_def distrib_left . |
320 qed |
320 qed |
321 |
321 |
322 lemma sqrt_iteration_lower_bound: |
322 lemma sqrt_iteration_lower_bound: |
323 assumes "0 < real x" |
323 assumes "0 < real_of_float x" |
324 shows "0 < real (sqrt_iteration prec n x)" (is "0 < ?sqrt") |
324 shows "0 < real_of_float (sqrt_iteration prec n x)" (is "0 < ?sqrt") |
325 proof - |
325 proof - |
326 have "0 < sqrt x" using assms by auto |
326 have "0 < sqrt x" using assms by auto |
327 also have "\<dots> < ?sqrt" using sqrt_iteration_bound[OF assms] . |
327 also have "\<dots> < ?sqrt" using sqrt_iteration_bound[OF assms] . |
328 finally show ?thesis . |
328 finally show ?thesis . |
329 qed |
329 qed |
330 |
330 |
331 lemma lb_sqrt_lower_bound: |
331 lemma lb_sqrt_lower_bound: |
332 assumes "0 \<le> real x" |
332 assumes "0 \<le> real_of_float x" |
333 shows "0 \<le> real (lb_sqrt prec x)" |
333 shows "0 \<le> real_of_float (lb_sqrt prec x)" |
334 proof (cases "0 < x") |
334 proof (cases "0 < x") |
335 case True |
335 case True |
336 hence "0 < real x" and "0 \<le> x" |
336 hence "0 < real_of_float x" and "0 \<le> x" |
337 using \<open>0 \<le> real x\<close> by auto |
337 using \<open>0 \<le> real_of_float x\<close> by auto |
338 hence "0 < sqrt_iteration prec prec x" |
338 hence "0 < sqrt_iteration prec prec x" |
339 using sqrt_iteration_lower_bound by auto |
339 using sqrt_iteration_lower_bound by auto |
340 hence "0 \<le> real (float_divl prec x (sqrt_iteration prec prec x))" |
340 hence "0 \<le> real_of_float (float_divl prec x (sqrt_iteration prec prec x))" |
341 using float_divl_lower_bound[OF \<open>0 \<le> x\<close>] unfolding less_eq_float_def by auto |
341 using float_divl_lower_bound[OF \<open>0 \<le> x\<close>] unfolding less_eq_float_def by auto |
342 thus ?thesis |
342 thus ?thesis |
343 unfolding lb_sqrt.simps using True by auto |
343 unfolding lb_sqrt.simps using True by auto |
344 next |
344 next |
345 case False |
345 case False |
346 with \<open>0 \<le> real x\<close> have "real x = 0" by auto |
346 with \<open>0 \<le> real_of_float x\<close> have "real_of_float x = 0" by auto |
347 thus ?thesis |
347 thus ?thesis |
348 unfolding lb_sqrt.simps by auto |
348 unfolding lb_sqrt.simps by auto |
349 qed |
349 qed |
350 |
350 |
351 lemma bnds_sqrt': "sqrt x \<in> {(lb_sqrt prec x) .. (ub_sqrt prec x)}" |
351 lemma bnds_sqrt': "sqrt x \<in> {(lb_sqrt prec x) .. (ub_sqrt prec x)}" |
352 proof - |
352 proof - |
353 have lb: "lb_sqrt prec x \<le> sqrt x" if "0 < x" for x :: float |
353 have lb: "lb_sqrt prec x \<le> sqrt x" if "0 < x" for x :: float |
354 proof - |
354 proof - |
355 from that have "0 < real x" and "0 \<le> real x" by auto |
355 from that have "0 < real_of_float x" and "0 \<le> real_of_float x" by auto |
356 hence sqrt_gt0: "0 < sqrt x" by auto |
356 hence sqrt_gt0: "0 < sqrt x" by auto |
357 hence sqrt_ub: "sqrt x < sqrt_iteration prec prec x" |
357 hence sqrt_ub: "sqrt x < sqrt_iteration prec prec x" |
358 using sqrt_iteration_bound by auto |
358 using sqrt_iteration_bound by auto |
359 have "(float_divl prec x (sqrt_iteration prec prec x)) \<le> |
359 have "(float_divl prec x (sqrt_iteration prec prec x)) \<le> |
360 x / (sqrt_iteration prec prec x)" by (rule float_divl) |
360 x / (sqrt_iteration prec prec x)" by (rule float_divl) |
361 also have "\<dots> < x / sqrt x" |
361 also have "\<dots> < x / sqrt x" |
362 by (rule divide_strict_left_mono[OF sqrt_ub \<open>0 < real x\<close> |
362 by (rule divide_strict_left_mono[OF sqrt_ub \<open>0 < real_of_float x\<close> |
363 mult_pos_pos[OF order_less_trans[OF sqrt_gt0 sqrt_ub] sqrt_gt0]]) |
363 mult_pos_pos[OF order_less_trans[OF sqrt_gt0 sqrt_ub] sqrt_gt0]]) |
364 also have "\<dots> = sqrt x" |
364 also have "\<dots> = sqrt x" |
365 unfolding inverse_eq_iff_eq[of _ "sqrt x", symmetric] |
365 unfolding inverse_eq_iff_eq[of _ "sqrt x", symmetric] |
366 sqrt_divide_self_eq[OF \<open>0 \<le> real x\<close>, symmetric] by auto |
366 sqrt_divide_self_eq[OF \<open>0 \<le> real_of_float x\<close>, symmetric] by auto |
367 finally show ?thesis |
367 finally show ?thesis |
368 unfolding lb_sqrt.simps if_P[OF \<open>0 < x\<close>] by auto |
368 unfolding lb_sqrt.simps if_P[OF \<open>0 < x\<close>] by auto |
369 qed |
369 qed |
370 have ub: "sqrt x \<le> ub_sqrt prec x" if "0 < x" for x :: float |
370 have ub: "sqrt x \<le> ub_sqrt prec x" if "0 < x" for x :: float |
371 proof - |
371 proof - |
372 from that have "0 < real x" by auto |
372 from that have "0 < real_of_float x" by auto |
373 hence "0 < sqrt x" by auto |
373 hence "0 < sqrt x" by auto |
374 hence "sqrt x < sqrt_iteration prec prec x" |
374 hence "sqrt x < sqrt_iteration prec prec x" |
375 using sqrt_iteration_bound by auto |
375 using sqrt_iteration_bound by auto |
376 then show ?thesis |
376 then show ?thesis |
377 unfolding ub_sqrt.simps if_P[OF \<open>0 < x\<close>] by auto |
377 unfolding ub_sqrt.simps if_P[OF \<open>0 < x\<close>] by auto |
530 also have "\<dots> \<le> z" using assms by (auto simp: field_simps) |
530 also have "\<dots> \<le> z" using assms by (auto simp: field_simps) |
531 finally show ?thesis using assms by (simp add: field_simps) |
531 finally show ?thesis using assms by (simp add: field_simps) |
532 qed |
532 qed |
533 |
533 |
534 lemma arctan_0_1_bounds_le: |
534 lemma arctan_0_1_bounds_le: |
535 assumes "0 \<le> x" "x \<le> 1" "0 < real xl" "real xl \<le> x * x" "x * x \<le> real xu" "real xu \<le> 1" |
535 assumes "0 \<le> x" "x \<le> 1" "0 < real_of_float xl" "real_of_float xl \<le> x * x" "x * x \<le> real_of_float xu" "real_of_float xu \<le> 1" |
536 shows "arctan x \<in> |
536 shows "arctan x \<in> |
537 {x * lb_arctan_horner p1 (get_even n) 1 xu .. x * ub_arctan_horner p2 (get_odd n) 1 xl}" |
537 {x * lb_arctan_horner p1 (get_even n) 1 xu .. x * ub_arctan_horner p2 (get_odd n) 1 xl}" |
538 proof - |
538 proof - |
539 from assms have "real xl \<le> 1" "sqrt (real xl) \<le> x" "x \<le> sqrt (real xu)" "0 \<le> real xu" |
539 from assms have "real_of_float xl \<le> 1" "sqrt (real_of_float xl) \<le> x" "x \<le> sqrt (real_of_float xu)" "0 \<le> real_of_float xu" |
540 "0 \<le> real xl" "0 < sqrt (real xl)" |
540 "0 \<le> real_of_float xl" "0 < sqrt (real_of_float xl)" |
541 by (auto intro!: real_le_rsqrt real_le_lsqrt simp: power2_eq_square) |
541 by (auto intro!: real_le_rsqrt real_le_lsqrt simp: power2_eq_square) |
542 from arctan_0_1_bounds[OF \<open>0 \<le> real xu\<close> \<open>real xu \<le> 1\<close>] |
542 from arctan_0_1_bounds[OF \<open>0 \<le> real_of_float xu\<close> \<open>real_of_float xu \<le> 1\<close>] |
543 have "sqrt (real xu) * real (lb_arctan_horner p1 (get_even n) 1 xu) \<le> arctan (sqrt (real xu))" |
543 have "sqrt (real_of_float xu) * real_of_float (lb_arctan_horner p1 (get_even n) 1 xu) \<le> arctan (sqrt (real_of_float xu))" |
544 by simp |
544 by simp |
545 from arctan_mult_le[OF \<open>0 \<le> x\<close> \<open>x \<le> sqrt _\<close> this] |
545 from arctan_mult_le[OF \<open>0 \<le> x\<close> \<open>x \<le> sqrt _\<close> this] |
546 have "x * real (lb_arctan_horner p1 (get_even n) 1 xu) \<le> arctan x" . |
546 have "x * real_of_float (lb_arctan_horner p1 (get_even n) 1 xu) \<le> arctan x" . |
547 moreover |
547 moreover |
548 from arctan_0_1_bounds[OF \<open>0 \<le> real xl\<close> \<open>real xl \<le> 1\<close>] |
548 from arctan_0_1_bounds[OF \<open>0 \<le> real_of_float xl\<close> \<open>real_of_float xl \<le> 1\<close>] |
549 have "arctan (sqrt (real xl)) \<le> sqrt (real xl) * real (ub_arctan_horner p2 (get_odd n) 1 xl)" |
549 have "arctan (sqrt (real_of_float xl)) \<le> sqrt (real_of_float xl) * real_of_float (ub_arctan_horner p2 (get_odd n) 1 xl)" |
550 by simp |
550 by simp |
551 from arctan_le_mult[OF \<open>0 < sqrt xl\<close> \<open>sqrt xl \<le> x\<close> this] |
551 from arctan_le_mult[OF \<open>0 < sqrt xl\<close> \<open>sqrt xl \<le> x\<close> this] |
552 have "arctan x \<le> x * real (ub_arctan_horner p2 (get_odd n) 1 xl)" . |
552 have "arctan x \<le> x * real_of_float (ub_arctan_horner p2 (get_odd n) 1 xl)" . |
553 ultimately show ?thesis by simp |
553 ultimately show ?thesis by simp |
554 qed |
554 qed |
555 |
555 |
556 lemma mult_nonneg_le_one: |
|
557 fixes a :: real |
|
558 assumes "0 \<le> a" "0 \<le> b" "a \<le> 1" "b \<le> 1" |
|
559 shows "a * b \<le> 1" |
|
560 proof - |
|
561 have "a * b \<le> 1 * 1" |
|
562 by (intro mult_mono assms) simp_all |
|
563 thus ?thesis by simp |
|
564 qed |
|
565 |
|
566 lemma arctan_0_1_bounds_round: |
556 lemma arctan_0_1_bounds_round: |
567 assumes "0 \<le> real x" "real x \<le> 1" |
557 assumes "0 \<le> real_of_float x" "real_of_float x \<le> 1" |
568 shows "arctan x \<in> |
558 shows "arctan x \<in> |
569 {real x * lb_arctan_horner p1 (get_even n) 1 (float_round_up (Suc p2) (x * x)) .. |
559 {real_of_float x * lb_arctan_horner p1 (get_even n) 1 (float_round_up (Suc p2) (x * x)) .. |
570 real x * ub_arctan_horner p3 (get_odd n) 1 (float_round_down (Suc p4) (x * x))}" |
560 real_of_float x * ub_arctan_horner p3 (get_odd n) 1 (float_round_down (Suc p4) (x * x))}" |
571 using assms |
561 using assms |
572 apply (cases "x > 0") |
562 apply (cases "x > 0") |
573 apply (intro arctan_0_1_bounds_le) |
563 apply (intro arctan_0_1_bounds_le) |
574 apply (auto simp: float_round_down.rep_eq float_round_up.rep_eq |
564 apply (auto simp: float_round_down.rep_eq float_round_up.rep_eq |
575 intro!: truncate_up_le1 mult_nonneg_le_one truncate_down_le truncate_up_le truncate_down_pos |
565 intro!: truncate_up_le1 mult_le_one truncate_down_le truncate_up_le truncate_down_pos |
576 mult_pos_pos) |
566 mult_pos_pos) |
577 done |
567 done |
578 |
568 |
579 |
569 |
580 subsection "Compute \<pi>" |
570 subsection "Compute \<pi>" |
612 assume "1 < k" hence "0 \<le> k" and "0 < k" and "1 \<le> k" by auto |
602 assume "1 < k" hence "0 \<le> k" and "0 < k" and "1 \<le> k" by auto |
613 let ?k = "rapprox_rat prec 1 k" |
603 let ?k = "rapprox_rat prec 1 k" |
614 let ?kl = "float_round_down (Suc prec) (?k * ?k)" |
604 let ?kl = "float_round_down (Suc prec) (?k * ?k)" |
615 have "1 div k = 0" using div_pos_pos_trivial[OF _ \<open>1 < k\<close>] by auto |
605 have "1 div k = 0" using div_pos_pos_trivial[OF _ \<open>1 < k\<close>] by auto |
616 |
606 |
617 have "0 \<le> real ?k" by (rule order_trans[OF _ rapprox_rat]) (auto simp add: \<open>0 \<le> k\<close>) |
607 have "0 \<le> real_of_float ?k" by (rule order_trans[OF _ rapprox_rat]) (auto simp add: \<open>0 \<le> k\<close>) |
618 have "real ?k \<le> 1" |
608 have "real_of_float ?k \<le> 1" |
619 by (auto simp add: \<open>0 < k\<close> \<open>1 \<le> k\<close> less_imp_le |
609 by (auto simp add: \<open>0 < k\<close> \<open>1 \<le> k\<close> less_imp_le |
620 intro!: mult_nonneg_le_one order_trans[OF _ rapprox_rat] rapprox_rat_le1) |
610 intro!: mult_le_one order_trans[OF _ rapprox_rat] rapprox_rat_le1) |
621 have "1 / k \<le> ?k" using rapprox_rat[where x=1 and y=k] by auto |
611 have "1 / k \<le> ?k" using rapprox_rat[where x=1 and y=k] by auto |
622 hence "arctan (1 / k) \<le> arctan ?k" by (rule arctan_monotone') |
612 hence "arctan (1 / k) \<le> arctan ?k" by (rule arctan_monotone') |
623 also have "\<dots> \<le> (?k * ub_arctan_horner prec (get_odd n) 1 ?kl)" |
613 also have "\<dots> \<le> (?k * ub_arctan_horner prec (get_odd n) 1 ?kl)" |
624 using arctan_0_1_bounds_round[OF \<open>0 \<le> real ?k\<close> \<open>real ?k \<le> 1\<close>] |
614 using arctan_0_1_bounds_round[OF \<open>0 \<le> real_of_float ?k\<close> \<open>real_of_float ?k \<le> 1\<close>] |
625 by auto |
615 by auto |
626 finally have "arctan (1 / k) \<le> ?k * ub_arctan_horner prec (get_odd n) 1 ?kl" . |
616 finally have "arctan (1 / k) \<le> ?k * ub_arctan_horner prec (get_odd n) 1 ?kl" . |
627 } note ub_arctan = this |
617 } note ub_arctan = this |
628 |
618 |
629 { |
619 { |
632 assume "1 < k" hence "0 \<le> k" and "0 < k" by auto |
622 assume "1 < k" hence "0 \<le> k" and "0 < k" by auto |
633 let ?k = "lapprox_rat prec 1 k" |
623 let ?k = "lapprox_rat prec 1 k" |
634 let ?ku = "float_round_up (Suc prec) (?k * ?k)" |
624 let ?ku = "float_round_up (Suc prec) (?k * ?k)" |
635 have "1 div k = 0" using div_pos_pos_trivial[OF _ \<open>1 < k\<close>] by auto |
625 have "1 div k = 0" using div_pos_pos_trivial[OF _ \<open>1 < k\<close>] by auto |
636 have "1 / k \<le> 1" using \<open>1 < k\<close> by auto |
626 have "1 / k \<le> 1" using \<open>1 < k\<close> by auto |
637 have "0 \<le> real ?k" using lapprox_rat_nonneg[where x=1 and y=k, OF zero_le_one \<open>0 \<le> k\<close>] |
627 have "0 \<le> real_of_float ?k" using lapprox_rat_nonneg[where x=1 and y=k, OF zero_le_one \<open>0 \<le> k\<close>] |
638 by (auto simp add: \<open>1 div k = 0\<close>) |
628 by (auto simp add: \<open>1 div k = 0\<close>) |
639 have "0 \<le> real (?k * ?k)" by simp |
629 have "0 \<le> real_of_float (?k * ?k)" by simp |
640 have "real ?k \<le> 1" using lapprox_rat by (rule order_trans, auto simp add: \<open>1 / k \<le> 1\<close>) |
630 have "real_of_float ?k \<le> 1" using lapprox_rat by (rule order_trans, auto simp add: \<open>1 / k \<le> 1\<close>) |
641 hence "real (?k * ?k) \<le> 1" using \<open>0 \<le> real ?k\<close> by (auto intro!: mult_nonneg_le_one) |
631 hence "real_of_float (?k * ?k) \<le> 1" using \<open>0 \<le> real_of_float ?k\<close> by (auto intro!: mult_le_one) |
642 |
632 |
643 have "?k \<le> 1 / k" using lapprox_rat[where x=1 and y=k] by auto |
633 have "?k \<le> 1 / k" using lapprox_rat[where x=1 and y=k] by auto |
644 |
634 |
645 have "?k * lb_arctan_horner prec (get_even n) 1 ?ku \<le> arctan ?k" |
635 have "?k * lb_arctan_horner prec (get_even n) 1 ?ku \<le> arctan ?k" |
646 using arctan_0_1_bounds_round[OF \<open>0 \<le> real ?k\<close> \<open>real ?k \<le> 1\<close>] |
636 using arctan_0_1_bounds_round[OF \<open>0 \<le> real_of_float ?k\<close> \<open>real_of_float ?k \<le> 1\<close>] |
647 by auto |
637 by auto |
648 also have "\<dots> \<le> arctan (1 / k)" using \<open>?k \<le> 1 / k\<close> by (rule arctan_monotone') |
638 also have "\<dots> \<le> arctan (1 / k)" using \<open>?k \<le> 1 / k\<close> by (rule arctan_monotone') |
649 finally have "?k * lb_arctan_horner prec (get_even n) 1 ?ku \<le> arctan (1 / k)" . |
639 finally have "?k * lb_arctan_horner prec (get_even n) 1 ?ku \<le> arctan (1 / k)" . |
650 } note lb_arctan = this |
640 } note lb_arctan = this |
651 |
641 |
709 |
699 |
710 declare ub_arctan_horner.simps[simp del] |
700 declare ub_arctan_horner.simps[simp del] |
711 declare lb_arctan_horner.simps[simp del] |
701 declare lb_arctan_horner.simps[simp del] |
712 |
702 |
713 lemma lb_arctan_bound': |
703 lemma lb_arctan_bound': |
714 assumes "0 \<le> real x" |
704 assumes "0 \<le> real_of_float x" |
715 shows "lb_arctan prec x \<le> arctan x" |
705 shows "lb_arctan prec x \<le> arctan x" |
716 proof - |
706 proof - |
717 have "\<not> x < 0" and "0 \<le> x" |
707 have "\<not> x < 0" and "0 \<le> x" |
718 using \<open>0 \<le> real x\<close> by (auto intro!: truncate_up_le ) |
708 using \<open>0 \<le> real_of_float x\<close> by (auto intro!: truncate_up_le ) |
719 |
709 |
720 let "?ub_horner x" = |
710 let "?ub_horner x" = |
721 "x * ub_arctan_horner prec (get_odd (prec div 4 + 1)) 1 (float_round_down (Suc prec) (x * x))" |
711 "x * ub_arctan_horner prec (get_odd (prec div 4 + 1)) 1 (float_round_down (Suc prec) (x * x))" |
722 and "?lb_horner x" = |
712 and "?lb_horner x" = |
723 "x * lb_arctan_horner prec (get_even (prec div 4 + 1)) 1 (float_round_up (Suc prec) (x * x))" |
713 "x * lb_arctan_horner prec (get_even (prec div 4 + 1)) 1 (float_round_up (Suc prec) (x * x))" |
724 |
714 |
725 show ?thesis |
715 show ?thesis |
726 proof (cases "x \<le> Float 1 (- 1)") |
716 proof (cases "x \<le> Float 1 (- 1)") |
727 case True |
717 case True |
728 hence "real x \<le> 1" by simp |
718 hence "real_of_float x \<le> 1" by simp |
729 from arctan_0_1_bounds_round[OF \<open>0 \<le> real x\<close> \<open>real x \<le> 1\<close>] |
719 from arctan_0_1_bounds_round[OF \<open>0 \<le> real_of_float x\<close> \<open>real_of_float x \<le> 1\<close>] |
730 show ?thesis |
720 show ?thesis |
731 unfolding lb_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] if_P[OF True] using \<open>0 \<le> x\<close> |
721 unfolding lb_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] if_P[OF True] using \<open>0 \<le> x\<close> |
732 by (auto intro!: float_round_down_le) |
722 by (auto intro!: float_round_down_le) |
733 next |
723 next |
734 case False |
724 case False |
735 hence "0 < real x" by auto |
725 hence "0 < real_of_float x" by auto |
736 let ?R = "1 + sqrt (1 + real x * real x)" |
726 let ?R = "1 + sqrt (1 + real_of_float x * real_of_float x)" |
737 let ?sxx = "float_plus_up prec 1 (float_round_up prec (x * x))" |
727 let ?sxx = "float_plus_up prec 1 (float_round_up prec (x * x))" |
738 let ?fR = "float_plus_up prec 1 (ub_sqrt prec ?sxx)" |
728 let ?fR = "float_plus_up prec 1 (ub_sqrt prec ?sxx)" |
739 let ?DIV = "float_divl prec x ?fR" |
729 let ?DIV = "float_divl prec x ?fR" |
740 |
730 |
741 have divisor_gt0: "0 < ?R" by (auto intro: add_pos_nonneg) |
731 have divisor_gt0: "0 < ?R" by (auto intro: add_pos_nonneg) |
745 also have "\<dots> \<le> ub_sqrt prec ?sxx" |
735 also have "\<dots> \<le> ub_sqrt prec ?sxx" |
746 using bnds_sqrt'[of ?sxx prec] by auto |
736 using bnds_sqrt'[of ?sxx prec] by auto |
747 finally |
737 finally |
748 have "sqrt (1 + x*x) \<le> ub_sqrt prec ?sxx" . |
738 have "sqrt (1 + x*x) \<le> ub_sqrt prec ?sxx" . |
749 hence "?R \<le> ?fR" by (auto simp: float_plus_up.rep_eq plus_up_def intro!: truncate_up_le) |
739 hence "?R \<le> ?fR" by (auto simp: float_plus_up.rep_eq plus_up_def intro!: truncate_up_le) |
750 hence "0 < ?fR" and "0 < real ?fR" using \<open>0 < ?R\<close> by auto |
740 hence "0 < ?fR" and "0 < real_of_float ?fR" using \<open>0 < ?R\<close> by auto |
751 |
741 |
752 have monotone: "?DIV \<le> x / ?R" |
742 have monotone: "?DIV \<le> x / ?R" |
753 proof - |
743 proof - |
754 have "?DIV \<le> real x / ?fR" by (rule float_divl) |
744 have "?DIV \<le> real_of_float x / ?fR" by (rule float_divl) |
755 also have "\<dots> \<le> x / ?R" by (rule divide_left_mono[OF \<open>?R \<le> ?fR\<close> \<open>0 \<le> real x\<close> mult_pos_pos[OF order_less_le_trans[OF divisor_gt0 \<open>?R \<le> real ?fR\<close>] divisor_gt0]]) |
745 also have "\<dots> \<le> x / ?R" by (rule divide_left_mono[OF \<open>?R \<le> ?fR\<close> \<open>0 \<le> real_of_float x\<close> mult_pos_pos[OF order_less_le_trans[OF divisor_gt0 \<open>?R \<le> real_of_float ?fR\<close>] divisor_gt0]]) |
756 finally show ?thesis . |
746 finally show ?thesis . |
757 qed |
747 qed |
758 |
748 |
759 show ?thesis |
749 show ?thesis |
760 proof (cases "x \<le> Float 1 1") |
750 proof (cases "x \<le> Float 1 1") |
761 case True |
751 case True |
762 have "x \<le> sqrt (1 + x * x)" |
752 have "x \<le> sqrt (1 + x * x)" |
763 using real_sqrt_sum_squares_ge2[where x=1, unfolded numeral_2_eq_2] by auto |
753 using real_sqrt_sum_squares_ge2[where x=1, unfolded numeral_2_eq_2] by auto |
764 also note \<open>\<dots> \<le> (ub_sqrt prec ?sxx)\<close> |
754 also note \<open>\<dots> \<le> (ub_sqrt prec ?sxx)\<close> |
765 finally have "real x \<le> ?fR" |
755 finally have "real_of_float x \<le> ?fR" |
766 by (auto simp: float_plus_up.rep_eq plus_up_def intro!: truncate_up_le) |
756 by (auto simp: float_plus_up.rep_eq plus_up_def intro!: truncate_up_le) |
767 moreover have "?DIV \<le> real x / ?fR" |
757 moreover have "?DIV \<le> real_of_float x / ?fR" |
768 by (rule float_divl) |
758 by (rule float_divl) |
769 ultimately have "real ?DIV \<le> 1" |
759 ultimately have "real_of_float ?DIV \<le> 1" |
770 unfolding divide_le_eq_1_pos[OF \<open>0 < real ?fR\<close>, symmetric] by auto |
760 unfolding divide_le_eq_1_pos[OF \<open>0 < real_of_float ?fR\<close>, symmetric] by auto |
771 |
761 |
772 have "0 \<le> real ?DIV" |
762 have "0 \<le> real_of_float ?DIV" |
773 using float_divl_lower_bound[OF \<open>0 \<le> x\<close>] \<open>0 < ?fR\<close> |
763 using float_divl_lower_bound[OF \<open>0 \<le> x\<close>] \<open>0 < ?fR\<close> |
774 unfolding less_eq_float_def by auto |
764 unfolding less_eq_float_def by auto |
775 |
765 |
776 from arctan_0_1_bounds_round[OF \<open>0 \<le> real (?DIV)\<close> \<open>real (?DIV) \<le> 1\<close>] |
766 from arctan_0_1_bounds_round[OF \<open>0 \<le> real_of_float (?DIV)\<close> \<open>real_of_float (?DIV) \<le> 1\<close>] |
777 have "Float 1 1 * ?lb_horner ?DIV \<le> 2 * arctan ?DIV" |
767 have "Float 1 1 * ?lb_horner ?DIV \<le> 2 * arctan ?DIV" |
778 by simp |
768 by simp |
779 also have "\<dots> \<le> 2 * arctan (x / ?R)" |
769 also have "\<dots> \<le> 2 * arctan (x / ?R)" |
780 using arctan_monotone'[OF monotone] by (auto intro!: mult_left_mono arctan_monotone') |
770 using arctan_monotone'[OF monotone] by (auto intro!: mult_left_mono arctan_monotone') |
781 also have "2 * arctan (x / ?R) = arctan x" |
771 also have "2 * arctan (x / ?R) = arctan x" |
801 unfolding lb_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] |
791 unfolding lb_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] |
802 if_not_P[OF \<open>\<not> x \<le> Float 1 (- 1)\<close>] if_not_P[OF False] if_P[OF True] |
792 if_not_P[OF \<open>\<not> x \<le> Float 1 (- 1)\<close>] if_not_P[OF False] if_P[OF True] |
803 using \<open>0 \<le> arctan x\<close> by auto |
793 using \<open>0 \<le> arctan x\<close> by auto |
804 next |
794 next |
805 case False |
795 case False |
806 hence "real ?invx \<le> 1" by auto |
796 hence "real_of_float ?invx \<le> 1" by auto |
807 have "0 \<le> real ?invx" |
797 have "0 \<le> real_of_float ?invx" |
808 by (rule order_trans[OF _ float_divr]) (auto simp add: \<open>0 \<le> real x\<close>) |
798 by (rule order_trans[OF _ float_divr]) (auto simp add: \<open>0 \<le> real_of_float x\<close>) |
809 |
799 |
810 have "1 / x \<noteq> 0" and "0 < 1 / x" |
800 have "1 / x \<noteq> 0" and "0 < 1 / x" |
811 using \<open>0 < real x\<close> by auto |
801 using \<open>0 < real_of_float x\<close> by auto |
812 |
802 |
813 have "arctan (1 / x) \<le> arctan ?invx" |
803 have "arctan (1 / x) \<le> arctan ?invx" |
814 unfolding one_float.rep_eq[symmetric] by (rule arctan_monotone', rule float_divr) |
804 unfolding one_float.rep_eq[symmetric] by (rule arctan_monotone', rule float_divr) |
815 also have "\<dots> \<le> ?ub_horner ?invx" |
805 also have "\<dots> \<le> ?ub_horner ?invx" |
816 using arctan_0_1_bounds_round[OF \<open>0 \<le> real ?invx\<close> \<open>real ?invx \<le> 1\<close>] |
806 using arctan_0_1_bounds_round[OF \<open>0 \<le> real_of_float ?invx\<close> \<open>real_of_float ?invx \<le> 1\<close>] |
817 by (auto intro!: float_round_up_le) |
807 by (auto intro!: float_round_up_le) |
818 also note float_round_up |
808 also note float_round_up |
819 finally have "pi / 2 - float_round_up prec (?ub_horner ?invx) \<le> arctan x" |
809 finally have "pi / 2 - float_round_up prec (?ub_horner ?invx) \<le> arctan x" |
820 using \<open>0 \<le> arctan x\<close> arctan_inverse[OF \<open>1 / x \<noteq> 0\<close>] |
810 using \<open>0 \<le> arctan x\<close> arctan_inverse[OF \<open>1 / x \<noteq> 0\<close>] |
821 unfolding real_sgn_pos[OF \<open>0 < 1 / real x\<close>] le_diff_eq by auto |
811 unfolding real_sgn_pos[OF \<open>0 < 1 / real_of_float x\<close>] le_diff_eq by auto |
822 moreover |
812 moreover |
823 have "lb_pi prec * Float 1 (- 1) \<le> pi / 2" |
813 have "lb_pi prec * Float 1 (- 1) \<le> pi / 2" |
824 unfolding Float_num times_divide_eq_right mult_1_left using pi_boundaries by simp |
814 unfolding Float_num times_divide_eq_right mult_1_left using pi_boundaries by simp |
825 ultimately |
815 ultimately |
826 show ?thesis |
816 show ?thesis |
831 qed |
821 qed |
832 qed |
822 qed |
833 qed |
823 qed |
834 |
824 |
835 lemma ub_arctan_bound': |
825 lemma ub_arctan_bound': |
836 assumes "0 \<le> real x" |
826 assumes "0 \<le> real_of_float x" |
837 shows "arctan x \<le> ub_arctan prec x" |
827 shows "arctan x \<le> ub_arctan prec x" |
838 proof - |
828 proof - |
839 have "\<not> x < 0" and "0 \<le> x" |
829 have "\<not> x < 0" and "0 \<le> x" |
840 using \<open>0 \<le> real x\<close> by auto |
830 using \<open>0 \<le> real_of_float x\<close> by auto |
841 |
831 |
842 let "?ub_horner x" = |
832 let "?ub_horner x" = |
843 "float_round_up prec (x * ub_arctan_horner prec (get_odd (prec div 4 + 1)) 1 (float_round_down (Suc prec) (x * x)))" |
833 "float_round_up prec (x * ub_arctan_horner prec (get_odd (prec div 4 + 1)) 1 (float_round_down (Suc prec) (x * x)))" |
844 let "?lb_horner x" = |
834 let "?lb_horner x" = |
845 "float_round_down prec (x * lb_arctan_horner prec (get_even (prec div 4 + 1)) 1 (float_round_up (Suc prec) (x * x)))" |
835 "float_round_down prec (x * lb_arctan_horner prec (get_even (prec div 4 + 1)) 1 (float_round_up (Suc prec) (x * x)))" |
846 |
836 |
847 show ?thesis |
837 show ?thesis |
848 proof (cases "x \<le> Float 1 (- 1)") |
838 proof (cases "x \<le> Float 1 (- 1)") |
849 case True |
839 case True |
850 hence "real x \<le> 1" by auto |
840 hence "real_of_float x \<le> 1" by auto |
851 show ?thesis |
841 show ?thesis |
852 unfolding ub_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] if_P[OF True] |
842 unfolding ub_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] if_P[OF True] |
853 using arctan_0_1_bounds_round[OF \<open>0 \<le> real x\<close> \<open>real x \<le> 1\<close>] |
843 using arctan_0_1_bounds_round[OF \<open>0 \<le> real_of_float x\<close> \<open>real_of_float x \<le> 1\<close>] |
854 by (auto intro!: float_round_up_le) |
844 by (auto intro!: float_round_up_le) |
855 next |
845 next |
856 case False |
846 case False |
857 hence "0 < real x" by auto |
847 hence "0 < real_of_float x" by auto |
858 let ?R = "1 + sqrt (1 + real x * real x)" |
848 let ?R = "1 + sqrt (1 + real_of_float x * real_of_float x)" |
859 let ?sxx = "float_plus_down prec 1 (float_round_down prec (x * x))" |
849 let ?sxx = "float_plus_down prec 1 (float_round_down prec (x * x))" |
860 let ?fR = "float_plus_down (Suc prec) 1 (lb_sqrt prec ?sxx)" |
850 let ?fR = "float_plus_down (Suc prec) 1 (lb_sqrt prec ?sxx)" |
861 let ?DIV = "float_divr prec x ?fR" |
851 let ?DIV = "float_divr prec x ?fR" |
862 |
852 |
863 have sqr_ge0: "0 \<le> 1 + real x * real x" |
853 have sqr_ge0: "0 \<le> 1 + real_of_float x * real_of_float x" |
864 using sum_power2_ge_zero[of 1 "real x", unfolded numeral_2_eq_2] by auto |
854 using sum_power2_ge_zero[of 1 "real_of_float x", unfolded numeral_2_eq_2] by auto |
865 hence "0 \<le> real (1 + x*x)" by auto |
855 hence "0 \<le> real_of_float (1 + x*x)" by auto |
866 |
856 |
867 hence divisor_gt0: "0 < ?R" by (auto intro: add_pos_nonneg) |
857 hence divisor_gt0: "0 < ?R" by (auto intro: add_pos_nonneg) |
868 |
858 |
869 have "lb_sqrt prec ?sxx \<le> sqrt ?sxx" |
859 have "lb_sqrt prec ?sxx \<le> sqrt ?sxx" |
870 using bnds_sqrt'[of ?sxx] by auto |
860 using bnds_sqrt'[of ?sxx] by auto |
871 also have "\<dots> \<le> sqrt (1 + x*x)" |
861 also have "\<dots> \<le> sqrt (1 + x*x)" |
872 by (auto simp: float_plus_down.rep_eq plus_down_def float_round_down.rep_eq truncate_down_le) |
862 by (auto simp: float_plus_down.rep_eq plus_down_def float_round_down.rep_eq truncate_down_le) |
873 finally have "lb_sqrt prec ?sxx \<le> sqrt (1 + x*x)" . |
863 finally have "lb_sqrt prec ?sxx \<le> sqrt (1 + x*x)" . |
874 hence "?fR \<le> ?R" |
864 hence "?fR \<le> ?R" |
875 by (auto simp: float_plus_down.rep_eq plus_down_def truncate_down_le) |
865 by (auto simp: float_plus_down.rep_eq plus_down_def truncate_down_le) |
876 have "0 < real ?fR" |
866 have "0 < real_of_float ?fR" |
877 by (auto simp: float_plus_down.rep_eq plus_down_def float_round_down.rep_eq |
867 by (auto simp: float_plus_down.rep_eq plus_down_def float_round_down.rep_eq |
878 intro!: truncate_down_ge1 lb_sqrt_lower_bound order_less_le_trans[OF zero_less_one] |
868 intro!: truncate_down_ge1 lb_sqrt_lower_bound order_less_le_trans[OF zero_less_one] |
879 truncate_down_nonneg add_nonneg_nonneg) |
869 truncate_down_nonneg add_nonneg_nonneg) |
880 have monotone: "x / ?R \<le> (float_divr prec x ?fR)" |
870 have monotone: "x / ?R \<le> (float_divr prec x ?fR)" |
881 proof - |
871 proof - |
882 from divide_left_mono[OF \<open>?fR \<le> ?R\<close> \<open>0 \<le> real x\<close> mult_pos_pos[OF divisor_gt0 \<open>0 < real ?fR\<close>]] |
872 from divide_left_mono[OF \<open>?fR \<le> ?R\<close> \<open>0 \<le> real_of_float x\<close> mult_pos_pos[OF divisor_gt0 \<open>0 < real_of_float ?fR\<close>]] |
883 have "x / ?R \<le> x / ?fR" . |
873 have "x / ?R \<le> x / ?fR" . |
884 also have "\<dots> \<le> ?DIV" by (rule float_divr) |
874 also have "\<dots> \<le> ?DIV" by (rule float_divr) |
885 finally show ?thesis . |
875 finally show ?thesis . |
886 qed |
876 qed |
887 |
877 |
897 show ?thesis |
887 show ?thesis |
898 unfolding ub_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] |
888 unfolding ub_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] |
899 if_not_P[OF \<open>\<not> x \<le> Float 1 (- 1)\<close>] if_P[OF \<open>x \<le> Float 1 1\<close>] if_P[OF True] . |
889 if_not_P[OF \<open>\<not> x \<le> Float 1 (- 1)\<close>] if_P[OF \<open>x \<le> Float 1 1\<close>] if_P[OF True] . |
900 next |
890 next |
901 case False |
891 case False |
902 hence "real ?DIV \<le> 1" by auto |
892 hence "real_of_float ?DIV \<le> 1" by auto |
903 |
893 |
904 have "0 \<le> x / ?R" |
894 have "0 \<le> x / ?R" |
905 using \<open>0 \<le> real x\<close> \<open>0 < ?R\<close> unfolding zero_le_divide_iff by auto |
895 using \<open>0 \<le> real_of_float x\<close> \<open>0 < ?R\<close> unfolding zero_le_divide_iff by auto |
906 hence "0 \<le> real ?DIV" |
896 hence "0 \<le> real_of_float ?DIV" |
907 using monotone by (rule order_trans) |
897 using monotone by (rule order_trans) |
908 |
898 |
909 have "arctan x = 2 * arctan (x / ?R)" |
899 have "arctan x = 2 * arctan (x / ?R)" |
910 using arctan_half unfolding numeral_2_eq_2 power_Suc2 power_0 mult_1_left . |
900 using arctan_half unfolding numeral_2_eq_2 power_Suc2 power_0 mult_1_left . |
911 also have "\<dots> \<le> 2 * arctan (?DIV)" |
901 also have "\<dots> \<le> 2 * arctan (?DIV)" |
912 using arctan_monotone'[OF monotone] by (auto intro!: mult_left_mono) |
902 using arctan_monotone'[OF monotone] by (auto intro!: mult_left_mono) |
913 also have "\<dots> \<le> (Float 1 1 * ?ub_horner ?DIV)" unfolding Float_num |
903 also have "\<dots> \<le> (Float 1 1 * ?ub_horner ?DIV)" unfolding Float_num |
914 using arctan_0_1_bounds_round[OF \<open>0 \<le> real ?DIV\<close> \<open>real ?DIV \<le> 1\<close>] |
904 using arctan_0_1_bounds_round[OF \<open>0 \<le> real_of_float ?DIV\<close> \<open>real_of_float ?DIV \<le> 1\<close>] |
915 by (auto intro!: float_round_up_le) |
905 by (auto intro!: float_round_up_le) |
916 finally show ?thesis |
906 finally show ?thesis |
917 unfolding ub_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] |
907 unfolding ub_arctan.simps Let_def if_not_P[OF \<open>\<not> x < 0\<close>] |
918 if_not_P[OF \<open>\<not> x \<le> Float 1 (- 1)\<close>] if_P[OF \<open>x \<le> Float 1 1\<close>] if_not_P[OF False] . |
908 if_not_P[OF \<open>\<not> x \<le> Float 1 (- 1)\<close>] if_P[OF \<open>x \<le> Float 1 1\<close>] if_not_P[OF False] . |
919 qed |
909 qed |
920 next |
910 next |
921 case False |
911 case False |
922 hence "2 < real x" by auto |
912 hence "2 < real_of_float x" by auto |
923 hence "1 \<le> real x" by auto |
913 hence "1 \<le> real_of_float x" by auto |
924 hence "0 < real x" by auto |
914 hence "0 < real_of_float x" by auto |
925 hence "0 < x" by auto |
915 hence "0 < x" by auto |
926 |
916 |
927 let "?invx" = "float_divl prec 1 x" |
917 let "?invx" = "float_divl prec 1 x" |
928 have "0 \<le> arctan x" |
918 have "0 \<le> arctan x" |
929 using arctan_monotone'[OF \<open>0 \<le> real x\<close>] and arctan_tan[of 0, unfolded tan_zero] by auto |
919 using arctan_monotone'[OF \<open>0 \<le> real_of_float x\<close>] and arctan_tan[of 0, unfolded tan_zero] by auto |
930 |
920 |
931 have "real ?invx \<le> 1" |
921 have "real_of_float ?invx \<le> 1" |
932 unfolding less_float_def |
922 unfolding less_float_def |
933 by (rule order_trans[OF float_divl]) |
923 by (rule order_trans[OF float_divl]) |
934 (auto simp add: \<open>1 \<le> real x\<close> divide_le_eq_1_pos[OF \<open>0 < real x\<close>]) |
924 (auto simp add: \<open>1 \<le> real_of_float x\<close> divide_le_eq_1_pos[OF \<open>0 < real_of_float x\<close>]) |
935 have "0 \<le> real ?invx" |
925 have "0 \<le> real_of_float ?invx" |
936 using \<open>0 < x\<close> by (intro float_divl_lower_bound) auto |
926 using \<open>0 < x\<close> by (intro float_divl_lower_bound) auto |
937 |
927 |
938 have "1 / x \<noteq> 0" and "0 < 1 / x" |
928 have "1 / x \<noteq> 0" and "0 < 1 / x" |
939 using \<open>0 < real x\<close> by auto |
929 using \<open>0 < real_of_float x\<close> by auto |
940 |
930 |
941 have "(?lb_horner ?invx) \<le> arctan (?invx)" |
931 have "(?lb_horner ?invx) \<le> arctan (?invx)" |
942 using arctan_0_1_bounds_round[OF \<open>0 \<le> real ?invx\<close> \<open>real ?invx \<le> 1\<close>] |
932 using arctan_0_1_bounds_round[OF \<open>0 \<le> real_of_float ?invx\<close> \<open>real_of_float ?invx \<le> 1\<close>] |
943 by (auto intro!: float_round_down_le) |
933 by (auto intro!: float_round_down_le) |
944 also have "\<dots> \<le> arctan (1 / x)" |
934 also have "\<dots> \<le> arctan (1 / x)" |
945 unfolding one_float.rep_eq[symmetric] by (rule arctan_monotone') (rule float_divl) |
935 unfolding one_float.rep_eq[symmetric] by (rule arctan_monotone') (rule float_divl) |
946 finally have "arctan x \<le> pi / 2 - (?lb_horner ?invx)" |
936 finally have "arctan x \<le> pi / 2 - (?lb_horner ?invx)" |
947 using \<open>0 \<le> arctan x\<close> arctan_inverse[OF \<open>1 / x \<noteq> 0\<close>] |
937 using \<open>0 \<le> arctan x\<close> arctan_inverse[OF \<open>1 / x \<noteq> 0\<close>] |
960 qed |
950 qed |
961 |
951 |
962 lemma arctan_boundaries: "arctan x \<in> {(lb_arctan prec x) .. (ub_arctan prec x)}" |
952 lemma arctan_boundaries: "arctan x \<in> {(lb_arctan prec x) .. (ub_arctan prec x)}" |
963 proof (cases "0 \<le> x") |
953 proof (cases "0 \<le> x") |
964 case True |
954 case True |
965 hence "0 \<le> real x" by auto |
955 hence "0 \<le> real_of_float x" by auto |
966 show ?thesis |
956 show ?thesis |
967 using ub_arctan_bound'[OF \<open>0 \<le> real x\<close>] lb_arctan_bound'[OF \<open>0 \<le> real x\<close>] |
957 using ub_arctan_bound'[OF \<open>0 \<le> real_of_float x\<close>] lb_arctan_bound'[OF \<open>0 \<le> real_of_float x\<close>] |
968 unfolding atLeastAtMost_iff by auto |
958 unfolding atLeastAtMost_iff by auto |
969 next |
959 next |
970 case False |
960 case False |
971 let ?mx = "-x" |
961 let ?mx = "-x" |
972 from False have "x < 0" and "0 \<le> real ?mx" |
962 from False have "x < 0" and "0 \<le> real_of_float ?mx" |
973 by auto |
963 by auto |
974 hence bounds: "lb_arctan prec ?mx \<le> arctan ?mx \<and> arctan ?mx \<le> ub_arctan prec ?mx" |
964 hence bounds: "lb_arctan prec ?mx \<le> arctan ?mx \<and> arctan ?mx \<le> ub_arctan prec ?mx" |
975 using ub_arctan_bound'[OF \<open>0 \<le> real ?mx\<close>] lb_arctan_bound'[OF \<open>0 \<le> real ?mx\<close>] by auto |
965 using ub_arctan_bound'[OF \<open>0 \<le> real_of_float ?mx\<close>] lb_arctan_bound'[OF \<open>0 \<le> real_of_float ?mx\<close>] by auto |
976 show ?thesis |
966 show ?thesis |
977 unfolding minus_float.rep_eq arctan_minus lb_arctan.simps[where x=x] |
967 unfolding minus_float.rep_eq arctan_minus lb_arctan.simps[where x=x] |
978 ub_arctan.simps[where x=x] Let_def if_P[OF \<open>x < 0\<close>] |
968 ub_arctan.simps[where x=x] Let_def if_P[OF \<open>x < 0\<close>] |
979 unfolding atLeastAtMost_iff using bounds[unfolded minus_float.rep_eq arctan_minus] |
969 unfolding atLeastAtMost_iff using bounds[unfolded minus_float.rep_eq arctan_minus] |
980 by (simp add: arctan_minus) |
970 by (simp add: arctan_minus) |
1025 |
1015 |
1026 lemma cos_aux: |
1016 lemma cos_aux: |
1027 shows "(lb_sin_cos_aux prec n 1 1 (x * x)) \<le> (\<Sum> i=0..<n. (- 1) ^ i * (1/(fact (2 * i))) * x ^(2 * i))" (is "?lb") |
1017 shows "(lb_sin_cos_aux prec n 1 1 (x * x)) \<le> (\<Sum> i=0..<n. (- 1) ^ i * (1/(fact (2 * i))) * x ^(2 * i))" (is "?lb") |
1028 and "(\<Sum> i=0..<n. (- 1) ^ i * (1/(fact (2 * i))) * x^(2 * i)) \<le> (ub_sin_cos_aux prec n 1 1 (x * x))" (is "?ub") |
1018 and "(\<Sum> i=0..<n. (- 1) ^ i * (1/(fact (2 * i))) * x^(2 * i)) \<le> (ub_sin_cos_aux prec n 1 1 (x * x))" (is "?ub") |
1029 proof - |
1019 proof - |
1030 have "0 \<le> real (x * x)" by auto |
1020 have "0 \<le> real_of_float (x * x)" by auto |
1031 let "?f n" = "fact (2 * n) :: nat" |
1021 let "?f n" = "fact (2 * n) :: nat" |
1032 have f_eq: "?f (Suc n) = ?f n * ((\<lambda>i. i + 2) ^^ n) 1 * (((\<lambda>i. i + 2) ^^ n) 1 + 1)" for n |
1022 have f_eq: "?f (Suc n) = ?f n * ((\<lambda>i. i + 2) ^^ n) 1 * (((\<lambda>i. i + 2) ^^ n) 1 + 1)" for n |
1033 proof - |
1023 proof - |
1034 have "\<And>m. ((\<lambda>i. i + 2) ^^ n) m = m + 2 * n" by (induct n) auto |
1024 have "\<And>m. ((\<lambda>i. i + 2) ^^ n) m = m + 2 * n" by (induct n) auto |
1035 then show ?thesis by auto |
1025 then show ?thesis by auto |
1036 qed |
1026 qed |
1037 from horner_bounds[where lb="lb_sin_cos_aux prec" and ub="ub_sin_cos_aux prec" and j'=0, |
1027 from horner_bounds[where lb="lb_sin_cos_aux prec" and ub="ub_sin_cos_aux prec" and j'=0, |
1038 OF \<open>0 \<le> real (x * x)\<close> f_eq lb_sin_cos_aux.simps ub_sin_cos_aux.simps] |
1028 OF \<open>0 \<le> real_of_float (x * x)\<close> f_eq lb_sin_cos_aux.simps ub_sin_cos_aux.simps] |
1039 show ?lb and ?ub |
1029 show ?lb and ?ub |
1040 by (auto simp add: power_mult power2_eq_square[of "real x"]) |
1030 by (auto simp add: power_mult power2_eq_square[of "real_of_float x"]) |
1041 qed |
1031 qed |
1042 |
1032 |
1043 lemma lb_sin_cos_aux_zero_le_one: "lb_sin_cos_aux prec n i j 0 \<le> 1" |
1033 lemma lb_sin_cos_aux_zero_le_one: "lb_sin_cos_aux prec n i j 0 \<le> 1" |
1044 by (cases j n rule: nat.exhaust[case_product nat.exhaust]) |
1034 by (cases j n rule: nat.exhaust[case_product nat.exhaust]) |
1045 (auto intro!: float_plus_down_le order_trans[OF lapprox_rat]) |
1035 (auto intro!: float_plus_down_le order_trans[OF lapprox_rat]) |
1046 |
1036 |
1047 lemma one_le_ub_sin_cos_aux: "odd n \<Longrightarrow> 1 \<le> ub_sin_cos_aux prec n i (Suc 0) 0" |
1037 lemma one_le_ub_sin_cos_aux: "odd n \<Longrightarrow> 1 \<le> ub_sin_cos_aux prec n i (Suc 0) 0" |
1048 by (cases n) (auto intro!: float_plus_up_le order_trans[OF _ rapprox_rat]) |
1038 by (cases n) (auto intro!: float_plus_up_le order_trans[OF _ rapprox_rat]) |
1049 |
1039 |
1050 lemma cos_boundaries: |
1040 lemma cos_boundaries: |
1051 assumes "0 \<le> real x" and "x \<le> pi / 2" |
1041 assumes "0 \<le> real_of_float x" and "x \<le> pi / 2" |
1052 shows "cos x \<in> {(lb_sin_cos_aux prec (get_even n) 1 1 (x * x)) .. (ub_sin_cos_aux prec (get_odd n) 1 1 (x * x))}" |
1042 shows "cos x \<in> {(lb_sin_cos_aux prec (get_even n) 1 1 (x * x)) .. (ub_sin_cos_aux prec (get_odd n) 1 1 (x * x))}" |
1053 proof (cases "real x = 0") |
1043 proof (cases "real_of_float x = 0") |
1054 case False |
1044 case False |
1055 hence "real x \<noteq> 0" by auto |
1045 hence "real_of_float x \<noteq> 0" by auto |
1056 hence "0 < x" and "0 < real x" |
1046 hence "0 < x" and "0 < real_of_float x" |
1057 using \<open>0 \<le> real x\<close> by auto |
1047 using \<open>0 \<le> real_of_float x\<close> by auto |
1058 have "0 < x * x" |
1048 have "0 < x * x" |
1059 using \<open>0 < x\<close> by simp |
1049 using \<open>0 < x\<close> by simp |
1060 |
1050 |
1061 have morph_to_if_power: "(\<Sum> i=0..<n. (-1::real) ^ i * (1/(fact (2 * i))) * x ^ (2 * i)) = |
1051 have morph_to_if_power: "(\<Sum> i=0..<n. (-1::real) ^ i * (1/(fact (2 * i))) * x ^ (2 * i)) = |
1062 (\<Sum> i = 0 ..< 2 * n. (if even(i) then ((- 1) ^ (i div 2))/((fact i)) else 0) * x ^ i)" |
1052 (\<Sum> i = 0 ..< 2 * n. (if even(i) then ((- 1) ^ (i div 2))/((fact i)) else 0) * x ^ i)" |
1072 finally show ?thesis . |
1062 finally show ?thesis . |
1073 qed |
1063 qed |
1074 |
1064 |
1075 { fix n :: nat assume "0 < n" |
1065 { fix n :: nat assume "0 < n" |
1076 hence "0 < 2 * n" by auto |
1066 hence "0 < 2 * n" by auto |
1077 obtain t where "0 < t" and "t < real x" and |
1067 obtain t where "0 < t" and "t < real_of_float x" and |
1078 cos_eq: "cos x = (\<Sum> i = 0 ..< 2 * n. (if even(i) then ((- 1) ^ (i div 2))/((fact i)) else 0) * (real x) ^ i) |
1068 cos_eq: "cos x = (\<Sum> i = 0 ..< 2 * n. (if even(i) then ((- 1) ^ (i div 2))/((fact i)) else 0) * (real_of_float x) ^ i) |
1079 + (cos (t + 1/2 * (2 * n) * pi) / (fact (2*n))) * (real x)^(2*n)" |
1069 + (cos (t + 1/2 * (2 * n) * pi) / (fact (2*n))) * (real_of_float x)^(2*n)" |
1080 (is "_ = ?SUM + ?rest / ?fact * ?pow") |
1070 (is "_ = ?SUM + ?rest / ?fact * ?pow") |
1081 using Maclaurin_cos_expansion2[OF \<open>0 < real x\<close> \<open>0 < 2 * n\<close>] |
1071 using Maclaurin_cos_expansion2[OF \<open>0 < real_of_float x\<close> \<open>0 < 2 * n\<close>] |
1082 unfolding cos_coeff_def atLeast0LessThan by auto |
1072 unfolding cos_coeff_def atLeast0LessThan by auto |
1083 |
1073 |
1084 have "cos t * (- 1) ^ n = cos t * cos (n * pi) + sin t * sin (n * pi)" by auto |
1074 have "cos t * (- 1) ^ n = cos t * cos (n * pi) + sin t * sin (n * pi)" by auto |
1085 also have "\<dots> = cos (t + n * pi)" by (simp add: cos_add) |
1075 also have "\<dots> = cos (t + n * pi)" by (simp add: cos_add) |
1086 also have "\<dots> = ?rest" by auto |
1076 also have "\<dots> = ?rest" by auto |
1087 finally have "cos t * (- 1) ^ n = ?rest" . |
1077 finally have "cos t * (- 1) ^ n = ?rest" . |
1088 moreover |
1078 moreover |
1089 have "t \<le> pi / 2" using \<open>t < real x\<close> and \<open>x \<le> pi / 2\<close> by auto |
1079 have "t \<le> pi / 2" using \<open>t < real_of_float x\<close> and \<open>x \<le> pi / 2\<close> by auto |
1090 hence "0 \<le> cos t" using \<open>0 < t\<close> and cos_ge_zero by auto |
1080 hence "0 \<le> cos t" using \<open>0 < t\<close> and cos_ge_zero by auto |
1091 ultimately have even: "even n \<Longrightarrow> 0 \<le> ?rest" and odd: "odd n \<Longrightarrow> 0 \<le> - ?rest " by auto |
1081 ultimately have even: "even n \<Longrightarrow> 0 \<le> ?rest" and odd: "odd n \<Longrightarrow> 0 \<le> - ?rest " by auto |
1092 |
1082 |
1093 have "0 < ?fact" by auto |
1083 have "0 < ?fact" by auto |
1094 have "0 < ?pow" using \<open>0 < real x\<close> by auto |
1084 have "0 < ?pow" using \<open>0 < real_of_float x\<close> by auto |
1095 |
1085 |
1096 { |
1086 { |
1097 assume "even n" |
1087 assume "even n" |
1098 have "(lb_sin_cos_aux prec n 1 1 (x * x)) \<le> ?SUM" |
1088 have "(lb_sin_cos_aux prec n 1 1 (x * x)) \<le> ?SUM" |
1099 unfolding morph_to_if_power[symmetric] using cos_aux by auto |
1089 unfolding morph_to_if_power[symmetric] using cos_aux by auto |
1145 using lb_sin_cos_aux_zero_le_one one_le_ub_sin_cos_aux |
1135 using lb_sin_cos_aux_zero_le_one one_le_ub_sin_cos_aux |
1146 by simp |
1136 by simp |
1147 qed |
1137 qed |
1148 |
1138 |
1149 lemma sin_aux: |
1139 lemma sin_aux: |
1150 assumes "0 \<le> real x" |
1140 assumes "0 \<le> real_of_float x" |
1151 shows "(x * lb_sin_cos_aux prec n 2 1 (x * x)) \<le> |
1141 shows "(x * lb_sin_cos_aux prec n 2 1 (x * x)) \<le> |
1152 (\<Sum> i=0..<n. (- 1) ^ i * (1/(fact (2 * i + 1))) * x^(2 * i + 1))" (is "?lb") |
1142 (\<Sum> i=0..<n. (- 1) ^ i * (1/(fact (2 * i + 1))) * x^(2 * i + 1))" (is "?lb") |
1153 and "(\<Sum> i=0..<n. (- 1) ^ i * (1/(fact (2 * i + 1))) * x^(2 * i + 1)) \<le> |
1143 and "(\<Sum> i=0..<n. (- 1) ^ i * (1/(fact (2 * i + 1))) * x^(2 * i + 1)) \<le> |
1154 (x * ub_sin_cos_aux prec n 2 1 (x * x))" (is "?ub") |
1144 (x * ub_sin_cos_aux prec n 2 1 (x * x))" (is "?ub") |
1155 proof - |
1145 proof - |
1156 have "0 \<le> real (x * x)" by auto |
1146 have "0 \<le> real_of_float (x * x)" by auto |
1157 let "?f n" = "fact (2 * n + 1) :: nat" |
1147 let "?f n" = "fact (2 * n + 1) :: nat" |
1158 have f_eq: "?f (Suc n) = ?f n * ((\<lambda>i. i + 2) ^^ n) 2 * (((\<lambda>i. i + 2) ^^ n) 2 + 1)" for n |
1148 have f_eq: "?f (Suc n) = ?f n * ((\<lambda>i. i + 2) ^^ n) 2 * (((\<lambda>i. i + 2) ^^ n) 2 + 1)" for n |
1159 proof - |
1149 proof - |
1160 have F: "\<And>m. ((\<lambda>i. i + 2) ^^ n) m = m + 2 * n" by (induct n) auto |
1150 have F: "\<And>m. ((\<lambda>i. i + 2) ^^ n) m = m + 2 * n" by (induct n) auto |
1161 show ?thesis |
1151 show ?thesis |
1162 unfolding F by auto |
1152 unfolding F by auto |
1163 qed |
1153 qed |
1164 from horner_bounds[where lb="lb_sin_cos_aux prec" and ub="ub_sin_cos_aux prec" and j'=0, |
1154 from horner_bounds[where lb="lb_sin_cos_aux prec" and ub="ub_sin_cos_aux prec" and j'=0, |
1165 OF \<open>0 \<le> real (x * x)\<close> f_eq lb_sin_cos_aux.simps ub_sin_cos_aux.simps] |
1155 OF \<open>0 \<le> real_of_float (x * x)\<close> f_eq lb_sin_cos_aux.simps ub_sin_cos_aux.simps] |
1166 show "?lb" and "?ub" using \<open>0 \<le> real x\<close> |
1156 show "?lb" and "?ub" using \<open>0 \<le> real_of_float x\<close> |
1167 unfolding power_add power_one_right mult.assoc[symmetric] setsum_left_distrib[symmetric] |
1157 unfolding power_add power_one_right mult.assoc[symmetric] setsum_left_distrib[symmetric] |
1168 unfolding mult.commute[where 'a=real] real_fact_nat |
1158 unfolding mult.commute[where 'a=real] of_nat_fact |
1169 by (auto intro!: mult_left_mono simp add: power_mult power2_eq_square[of "real x"]) |
1159 by (auto intro!: mult_left_mono simp add: power_mult power2_eq_square[of "real_of_float x"]) |
1170 qed |
1160 qed |
1171 |
1161 |
1172 lemma sin_boundaries: |
1162 lemma sin_boundaries: |
1173 assumes "0 \<le> real x" |
1163 assumes "0 \<le> real_of_float x" |
1174 and "x \<le> pi / 2" |
1164 and "x \<le> pi / 2" |
1175 shows "sin x \<in> {(x * lb_sin_cos_aux prec (get_even n) 2 1 (x * x)) .. (x * ub_sin_cos_aux prec (get_odd n) 2 1 (x * x))}" |
1165 shows "sin x \<in> {(x * lb_sin_cos_aux prec (get_even n) 2 1 (x * x)) .. (x * ub_sin_cos_aux prec (get_odd n) 2 1 (x * x))}" |
1176 proof (cases "real x = 0") |
1166 proof (cases "real_of_float x = 0") |
1177 case False |
1167 case False |
1178 hence "real x \<noteq> 0" by auto |
1168 hence "real_of_float x \<noteq> 0" by auto |
1179 hence "0 < x" and "0 < real x" |
1169 hence "0 < x" and "0 < real_of_float x" |
1180 using \<open>0 \<le> real x\<close> by auto |
1170 using \<open>0 \<le> real_of_float x\<close> by auto |
1181 have "0 < x * x" |
1171 have "0 < x * x" |
1182 using \<open>0 < x\<close> by simp |
1172 using \<open>0 < x\<close> by simp |
1183 |
1173 |
1184 have setsum_morph: "(\<Sum>j = 0 ..< n. (- 1) ^ (((2 * j + 1) - Suc 0) div 2) / ((fact (2 * j + 1))) * x ^(2 * j + 1)) = |
1174 have setsum_morph: "(\<Sum>j = 0 ..< n. (- 1) ^ (((2 * j + 1) - Suc 0) div 2) / ((fact (2 * j + 1))) * x ^(2 * j + 1)) = |
1185 (\<Sum> i = 0 ..< 2 * n. (if even(i) then 0 else ((- 1) ^ ((i - Suc 0) div 2))/((fact i))) * x ^ i)" |
1175 (\<Sum> i = 0 ..< 2 * n. (if even(i) then 0 else ((- 1) ^ ((i - Suc 0) div 2))/((fact i))) * x ^ i)" |
1196 finally show ?thesis . |
1186 finally show ?thesis . |
1197 qed |
1187 qed |
1198 |
1188 |
1199 { fix n :: nat assume "0 < n" |
1189 { fix n :: nat assume "0 < n" |
1200 hence "0 < 2 * n + 1" by auto |
1190 hence "0 < 2 * n + 1" by auto |
1201 obtain t where "0 < t" and "t < real x" and |
1191 obtain t where "0 < t" and "t < real_of_float x" and |
1202 sin_eq: "sin x = (\<Sum> i = 0 ..< 2 * n + 1. (if even(i) then 0 else ((- 1) ^ ((i - Suc 0) div 2))/((fact i))) * (real x) ^ i) |
1192 sin_eq: "sin x = (\<Sum> i = 0 ..< 2 * n + 1. (if even(i) then 0 else ((- 1) ^ ((i - Suc 0) div 2))/((fact i))) * (real_of_float x) ^ i) |
1203 + (sin (t + 1/2 * (2 * n + 1) * pi) / (fact (2*n + 1))) * (real x)^(2*n + 1)" |
1193 + (sin (t + 1/2 * (2 * n + 1) * pi) / (fact (2*n + 1))) * (real_of_float x)^(2*n + 1)" |
1204 (is "_ = ?SUM + ?rest / ?fact * ?pow") |
1194 (is "_ = ?SUM + ?rest / ?fact * ?pow") |
1205 using Maclaurin_sin_expansion3[OF \<open>0 < 2 * n + 1\<close> \<open>0 < real x\<close>] |
1195 using Maclaurin_sin_expansion3[OF \<open>0 < 2 * n + 1\<close> \<open>0 < real_of_float x\<close>] |
1206 unfolding sin_coeff_def atLeast0LessThan by auto |
1196 unfolding sin_coeff_def atLeast0LessThan by auto |
1207 |
1197 |
1208 have "?rest = cos t * (- 1) ^ n" |
1198 have "?rest = cos t * (- 1) ^ n" |
1209 unfolding sin_add cos_add real_of_nat_add distrib_right distrib_left by auto |
1199 unfolding sin_add cos_add of_nat_add distrib_right distrib_left by auto |
1210 moreover |
1200 moreover |
1211 have "t \<le> pi / 2" |
1201 have "t \<le> pi / 2" |
1212 using \<open>t < real x\<close> and \<open>x \<le> pi / 2\<close> by auto |
1202 using \<open>t < real_of_float x\<close> and \<open>x \<le> pi / 2\<close> by auto |
1213 hence "0 \<le> cos t" |
1203 hence "0 \<le> cos t" |
1214 using \<open>0 < t\<close> and cos_ge_zero by auto |
1204 using \<open>0 < t\<close> and cos_ge_zero by auto |
1215 ultimately have even: "even n \<Longrightarrow> 0 \<le> ?rest" and odd: "odd n \<Longrightarrow> 0 \<le> - ?rest" |
1205 ultimately have even: "even n \<Longrightarrow> 0 \<le> ?rest" and odd: "odd n \<Longrightarrow> 0 \<le> - ?rest" |
1216 by auto |
1206 by auto |
1217 |
1207 |
1218 have "0 < ?fact" |
1208 have "0 < ?fact" |
1219 by (simp del: fact_Suc) |
1209 by (simp del: fact_Suc) |
1220 have "0 < ?pow" |
1210 have "0 < ?pow" |
1221 using \<open>0 < real x\<close> by (rule zero_less_power) |
1211 using \<open>0 < real_of_float x\<close> by (rule zero_less_power) |
1222 |
1212 |
1223 { |
1213 { |
1224 assume "even n" |
1214 assume "even n" |
1225 have "(x * lb_sin_cos_aux prec n 2 1 (x * x)) \<le> |
1215 have "(x * lb_sin_cos_aux prec n 2 1 (x * x)) \<le> |
1226 (\<Sum> i = 0 ..< 2 * n. (if even(i) then 0 else ((- 1) ^ ((i - Suc 0) div 2))/((fact i))) * (real x) ^ i)" |
1216 (\<Sum> i = 0 ..< 2 * n. (if even(i) then 0 else ((- 1) ^ ((i - Suc 0) div 2))/((fact i))) * (real_of_float x) ^ i)" |
1227 using sin_aux[OF \<open>0 \<le> real x\<close>] unfolding setsum_morph[symmetric] by auto |
1217 using sin_aux[OF \<open>0 \<le> real_of_float x\<close>] unfolding setsum_morph[symmetric] by auto |
1228 also have "\<dots> \<le> ?SUM" by auto |
1218 also have "\<dots> \<le> ?SUM" by auto |
1229 also have "\<dots> \<le> sin x" |
1219 also have "\<dots> \<le> sin x" |
1230 proof - |
1220 proof - |
1231 from even[OF \<open>even n\<close>] \<open>0 < ?fact\<close> \<open>0 < ?pow\<close> |
1221 from even[OF \<open>even n\<close>] \<open>0 < ?fact\<close> \<open>0 < ?pow\<close> |
1232 have "0 \<le> (?rest / ?fact) * ?pow" by simp |
1222 have "0 \<le> (?rest / ?fact) * ?pow" by simp |
1418 using \<open>\<not> x < 0\<close> \<open>\<not> x < Float 1 (- 1)\<close> \<open>x < 1\<close> by auto |
1408 using \<open>\<not> x < 0\<close> \<open>\<not> x < Float 1 (- 1)\<close> \<open>x < 1\<close> by auto |
1419 qed |
1409 qed |
1420 ultimately show ?thesis by auto |
1410 ultimately show ?thesis by auto |
1421 next |
1411 next |
1422 case False |
1412 case False |
1423 have "0 \<le> real ?x4" and "?x4 \<le> pi / 2" |
1413 have "0 \<le> real_of_float ?x4" and "?x4 \<le> pi / 2" |
1424 using pi_ge_two \<open>0 \<le> real x\<close> \<open>x \<le> pi\<close> unfolding Float_num by auto |
1414 using pi_ge_two \<open>0 \<le> real_of_float x\<close> \<open>x \<le> pi\<close> unfolding Float_num by auto |
1425 from cos_boundaries[OF this] |
1415 from cos_boundaries[OF this] |
1426 have lb: "(?lb_horner ?x4) \<le> ?cos ?x4" and ub: "?cos ?x4 \<le> (?ub_horner ?x4)" |
1416 have lb: "(?lb_horner ?x4) \<le> ?cos ?x4" and ub: "?cos ?x4 \<le> (?ub_horner ?x4)" |
1427 by auto |
1417 by auto |
1428 |
1418 |
1429 have eq_4: "?x2 * Float 1 (- 1) = x * Float 1 (- 2)" |
1419 have eq_4: "?x2 * Float 1 (- 1) = x * Float 1 (- 2)" |
1430 by transfer simp |
1420 by transfer simp |
1431 |
1421 |
1432 have "(?lb x) \<le> ?cos x" |
1422 have "(?lb x) \<le> ?cos x" |
1433 proof - |
1423 proof - |
1434 have "-pi \<le> ?x2" and "?x2 \<le> pi" |
1424 have "-pi \<le> ?x2" and "?x2 \<le> pi" |
1435 using pi_ge_two \<open>0 \<le> real x\<close> \<open>x \<le> pi\<close> by auto |
1425 using pi_ge_two \<open>0 \<le> real_of_float x\<close> \<open>x \<le> pi\<close> by auto |
1436 from lb_half[OF lb_half[OF lb this] \<open>-pi \<le> x\<close> \<open>x \<le> pi\<close>, unfolded eq_4] |
1426 from lb_half[OF lb_half[OF lb this] \<open>-pi \<le> x\<close> \<open>x \<le> pi\<close>, unfolded eq_4] |
1437 show ?thesis |
1427 show ?thesis |
1438 unfolding lb_cos_def[where x=x] if_not_P[OF \<open>\<not> x < 0\<close>] |
1428 unfolding lb_cos_def[where x=x] if_not_P[OF \<open>\<not> x < 0\<close>] |
1439 if_not_P[OF \<open>\<not> x < Float 1 (- 1)\<close>] if_not_P[OF \<open>\<not> x < 1\<close>] Let_def . |
1429 if_not_P[OF \<open>\<not> x < Float 1 (- 1)\<close>] if_not_P[OF \<open>\<not> x < 1\<close>] Let_def . |
1440 qed |
1430 qed |
1441 moreover have "?cos x \<le> (?ub x)" |
1431 moreover have "?cos x \<le> (?ub x)" |
1442 proof - |
1432 proof - |
1443 have "-pi \<le> ?x2" and "?x2 \<le> pi" |
1433 have "-pi \<le> ?x2" and "?x2 \<le> pi" |
1444 using pi_ge_two \<open>0 \<le> real x\<close> \<open> x \<le> pi\<close> by auto |
1434 using pi_ge_two \<open>0 \<le> real_of_float x\<close> \<open> x \<le> pi\<close> by auto |
1445 from ub_half[OF ub_half[OF ub this] \<open>-pi \<le> x\<close> \<open>x \<le> pi\<close>, unfolded eq_4] |
1435 from ub_half[OF ub_half[OF ub this] \<open>-pi \<le> x\<close> \<open>x \<le> pi\<close>, unfolded eq_4] |
1446 show ?thesis |
1436 show ?thesis |
1447 unfolding ub_cos_def[where x=x] if_not_P[OF \<open>\<not> x < 0\<close>] |
1437 unfolding ub_cos_def[where x=x] if_not_P[OF \<open>\<not> x < 0\<close>] |
1448 if_not_P[OF \<open>\<not> x < Float 1 (- 1)\<close>] if_not_P[OF \<open>\<not> x < 1\<close>] Let_def . |
1438 if_not_P[OF \<open>\<not> x < Float 1 (- 1)\<close>] if_not_P[OF \<open>\<not> x < 1\<close>] Let_def . |
1449 qed |
1439 qed |
1540 simp add: k [symmetric] uminus_add_conv_diff [symmetric] |
1530 simp add: k [symmetric] uminus_add_conv_diff [symmetric] |
1541 simp del: float_of_numeral uminus_add_conv_diff) |
1531 simp del: float_of_numeral uminus_add_conv_diff) |
1542 hence "?lx \<le> x - k * (2 * pi) \<and> x - k * (2 * pi) \<le> ?ux" |
1532 hence "?lx \<le> x - k * (2 * pi) \<and> x - k * (2 * pi) \<le> ?ux" |
1543 by (auto intro!: float_plus_down_le float_plus_up_le) |
1533 by (auto intro!: float_plus_down_le float_plus_up_le) |
1544 note lx = this[THEN conjunct1] and ux = this[THEN conjunct2] |
1534 note lx = this[THEN conjunct1] and ux = this[THEN conjunct2] |
1545 hence lx_less_ux: "?lx \<le> real ?ux" by (rule order_trans) |
1535 hence lx_less_ux: "?lx \<le> real_of_float ?ux" by (rule order_trans) |
1546 |
1536 |
1547 { assume "- ?lpi \<le> ?lx" and x_le_0: "x - k * (2 * pi) \<le> 0" |
1537 { assume "- ?lpi \<le> ?lx" and x_le_0: "x - k * (2 * pi) \<le> 0" |
1548 with lpi[THEN le_imp_neg_le] lx |
1538 with lpi[THEN le_imp_neg_le] lx |
1549 have pi_lx: "- pi \<le> ?lx" and lx_0: "real ?lx \<le> 0" |
1539 have pi_lx: "- pi \<le> ?lx" and lx_0: "real_of_float ?lx \<le> 0" |
1550 by simp_all |
1540 by simp_all |
1551 |
1541 |
1552 have "(lb_cos prec (- ?lx)) \<le> cos (real (- ?lx))" |
1542 have "(lb_cos prec (- ?lx)) \<le> cos (real_of_float (- ?lx))" |
1553 using lb_cos_minus[OF pi_lx lx_0] by simp |
1543 using lb_cos_minus[OF pi_lx lx_0] by simp |
1554 also have "\<dots> \<le> cos (x + (-k) * (2 * pi))" |
1544 also have "\<dots> \<le> cos (x + (-k) * (2 * pi))" |
1555 using cos_monotone_minus_pi_0'[OF pi_lx lx x_le_0] |
1545 using cos_monotone_minus_pi_0'[OF pi_lx lx x_le_0] |
1556 by (simp only: uminus_float.rep_eq real_of_int_minus |
1546 by (simp only: uminus_float.rep_eq of_int_minus |
1557 cos_minus mult_minus_left) simp |
1547 cos_minus mult_minus_left) simp |
1558 finally have "(lb_cos prec (- ?lx)) \<le> cos x" |
1548 finally have "(lb_cos prec (- ?lx)) \<le> cos x" |
1559 unfolding cos_periodic_int . } |
1549 unfolding cos_periodic_int . } |
1560 note negative_lx = this |
1550 note negative_lx = this |
1561 |
1551 |
1562 { assume "0 \<le> ?lx" and pi_x: "x - k * (2 * pi) \<le> pi" |
1552 { assume "0 \<le> ?lx" and pi_x: "x - k * (2 * pi) \<le> pi" |
1563 with lx |
1553 with lx |
1564 have pi_lx: "?lx \<le> pi" and lx_0: "0 \<le> real ?lx" |
1554 have pi_lx: "?lx \<le> pi" and lx_0: "0 \<le> real_of_float ?lx" |
1565 by auto |
1555 by auto |
1566 |
1556 |
1567 have "cos (x + (-k) * (2 * pi)) \<le> cos ?lx" |
1557 have "cos (x + (-k) * (2 * pi)) \<le> cos ?lx" |
1568 using cos_monotone_0_pi_le[OF lx_0 lx pi_x] |
1558 using cos_monotone_0_pi_le[OF lx_0 lx pi_x] |
1569 by (simp only: real_of_int_minus |
1559 by (simp only: of_int_minus |
1570 cos_minus mult_minus_left) simp |
1560 cos_minus mult_minus_left) simp |
1571 also have "\<dots> \<le> (ub_cos prec ?lx)" |
1561 also have "\<dots> \<le> (ub_cos prec ?lx)" |
1572 using lb_cos[OF lx_0 pi_lx] by simp |
1562 using lb_cos[OF lx_0 pi_lx] by simp |
1573 finally have "cos x \<le> (ub_cos prec ?lx)" |
1563 finally have "cos x \<le> (ub_cos prec ?lx)" |
1574 unfolding cos_periodic_int . } |
1564 unfolding cos_periodic_int . } |
1575 note positive_lx = this |
1565 note positive_lx = this |
1576 |
1566 |
1577 { assume pi_x: "- pi \<le> x - k * (2 * pi)" and "?ux \<le> 0" |
1567 { assume pi_x: "- pi \<le> x - k * (2 * pi)" and "?ux \<le> 0" |
1578 with ux |
1568 with ux |
1579 have pi_ux: "- pi \<le> ?ux" and ux_0: "real ?ux \<le> 0" |
1569 have pi_ux: "- pi \<le> ?ux" and ux_0: "real_of_float ?ux \<le> 0" |
1580 by simp_all |
1570 by simp_all |
1581 |
1571 |
1582 have "cos (x + (-k) * (2 * pi)) \<le> cos (real (- ?ux))" |
1572 have "cos (x + (-k) * (2 * pi)) \<le> cos (real_of_float (- ?ux))" |
1583 using cos_monotone_minus_pi_0'[OF pi_x ux ux_0] |
1573 using cos_monotone_minus_pi_0'[OF pi_x ux ux_0] |
1584 by (simp only: uminus_float.rep_eq real_of_int_minus |
1574 by (simp only: uminus_float.rep_eq of_int_minus |
1585 cos_minus mult_minus_left) simp |
1575 cos_minus mult_minus_left) simp |
1586 also have "\<dots> \<le> (ub_cos prec (- ?ux))" |
1576 also have "\<dots> \<le> (ub_cos prec (- ?ux))" |
1587 using lb_cos_minus[OF pi_ux ux_0, of prec] by simp |
1577 using lb_cos_minus[OF pi_ux ux_0, of prec] by simp |
1588 finally have "cos x \<le> (ub_cos prec (- ?ux))" |
1578 finally have "cos x \<le> (ub_cos prec (- ?ux))" |
1589 unfolding cos_periodic_int . } |
1579 unfolding cos_periodic_int . } |
1590 note negative_ux = this |
1580 note negative_ux = this |
1591 |
1581 |
1592 { assume "?ux \<le> ?lpi" and x_ge_0: "0 \<le> x - k * (2 * pi)" |
1582 { assume "?ux \<le> ?lpi" and x_ge_0: "0 \<le> x - k * (2 * pi)" |
1593 with lpi ux |
1583 with lpi ux |
1594 have pi_ux: "?ux \<le> pi" and ux_0: "0 \<le> real ?ux" |
1584 have pi_ux: "?ux \<le> pi" and ux_0: "0 \<le> real_of_float ?ux" |
1595 by simp_all |
1585 by simp_all |
1596 |
1586 |
1597 have "(lb_cos prec ?ux) \<le> cos ?ux" |
1587 have "(lb_cos prec ?ux) \<le> cos ?ux" |
1598 using lb_cos[OF ux_0 pi_ux] by simp |
1588 using lb_cos[OF ux_0 pi_ux] by simp |
1599 also have "\<dots> \<le> cos (x + (-k) * (2 * pi))" |
1589 also have "\<dots> \<le> cos (x + (-k) * (2 * pi))" |
1600 using cos_monotone_0_pi_le[OF x_ge_0 ux pi_ux] |
1590 using cos_monotone_0_pi_le[OF x_ge_0 ux pi_ux] |
1601 by (simp only: real_of_int_minus |
1591 by (simp only: of_int_minus |
1602 cos_minus mult_minus_left) simp |
1592 cos_minus mult_minus_left) simp |
1603 finally have "(lb_cos prec ?ux) \<le> cos x" |
1593 finally have "(lb_cos prec ?ux) \<le> cos x" |
1604 unfolding cos_periodic_int . } |
1594 unfolding cos_periodic_int . } |
1605 note positive_ux = this |
1595 note positive_ux = this |
1606 |
1596 |
1774 note bounds = horner_bounds_nonpos[where f="fact" and lb="lb_exp_horner prec" and ub="ub_exp_horner prec" and j'=0 and s=1, |
1764 note bounds = horner_bounds_nonpos[where f="fact" and lb="lb_exp_horner prec" and ub="ub_exp_horner prec" and j'=0 and s=1, |
1775 OF assms f_eq lb_exp_horner.simps ub_exp_horner.simps] |
1765 OF assms f_eq lb_exp_horner.simps ub_exp_horner.simps] |
1776 |
1766 |
1777 have "lb_exp_horner prec (get_even n) 1 1 x \<le> exp x" |
1767 have "lb_exp_horner prec (get_even n) 1 1 x \<le> exp x" |
1778 proof - |
1768 proof - |
1779 have "lb_exp_horner prec (get_even n) 1 1 x \<le> (\<Sum>j = 0..<get_even n. 1 / (fact j) * real x ^ j)" |
1769 have "lb_exp_horner prec (get_even n) 1 1 x \<le> (\<Sum>j = 0..<get_even n. 1 / (fact j) * real_of_float x ^ j)" |
1780 using bounds(1) by auto |
1770 using bounds(1) by auto |
1781 also have "\<dots> \<le> exp x" |
1771 also have "\<dots> \<le> exp x" |
1782 proof - |
1772 proof - |
1783 obtain t where "\<bar>t\<bar> \<le> \<bar>real x\<bar>" and "exp x = (\<Sum>m = 0..<get_even n. real x ^ m / (fact m)) + exp t / (fact (get_even n)) * (real x) ^ (get_even n)" |
1773 obtain t where "\<bar>t\<bar> \<le> \<bar>real_of_float x\<bar>" and "exp x = (\<Sum>m = 0..<get_even n. real_of_float x ^ m / (fact m)) + exp t / (fact (get_even n)) * (real_of_float x) ^ (get_even n)" |
1784 using Maclaurin_exp_le unfolding atLeast0LessThan by blast |
1774 using Maclaurin_exp_le unfolding atLeast0LessThan by blast |
1785 moreover have "0 \<le> exp t / (fact (get_even n)) * (real x) ^ (get_even n)" |
1775 moreover have "0 \<le> exp t / (fact (get_even n)) * (real_of_float x) ^ (get_even n)" |
1786 by (auto simp: zero_le_even_power) |
1776 by (auto simp: zero_le_even_power) |
1787 ultimately show ?thesis using get_odd exp_gt_zero by auto |
1777 ultimately show ?thesis using get_odd exp_gt_zero by auto |
1788 qed |
1778 qed |
1789 finally show ?thesis . |
1779 finally show ?thesis . |
1790 qed |
1780 qed |
1791 moreover |
1781 moreover |
1792 have "exp x \<le> ub_exp_horner prec (get_odd n) 1 1 x" |
1782 have "exp x \<le> ub_exp_horner prec (get_odd n) 1 1 x" |
1793 proof - |
1783 proof - |
1794 have x_less_zero: "real x ^ get_odd n \<le> 0" |
1784 have x_less_zero: "real_of_float x ^ get_odd n \<le> 0" |
1795 proof (cases "real x = 0") |
1785 proof (cases "real_of_float x = 0") |
1796 case True |
1786 case True |
1797 have "(get_odd n) \<noteq> 0" using get_odd[THEN odd_pos] by auto |
1787 have "(get_odd n) \<noteq> 0" using get_odd[THEN odd_pos] by auto |
1798 thus ?thesis unfolding True power_0_left by auto |
1788 thus ?thesis unfolding True power_0_left by auto |
1799 next |
1789 next |
1800 case False hence "real x < 0" using \<open>real x \<le> 0\<close> by auto |
1790 case False hence "real_of_float x < 0" using \<open>real_of_float x \<le> 0\<close> by auto |
1801 show ?thesis by (rule less_imp_le, auto simp add: power_less_zero_eq \<open>real x < 0\<close>) |
1791 show ?thesis by (rule less_imp_le, auto simp add: power_less_zero_eq \<open>real_of_float x < 0\<close>) |
1802 qed |
1792 qed |
1803 obtain t where "\<bar>t\<bar> \<le> \<bar>real x\<bar>" |
1793 obtain t where "\<bar>t\<bar> \<le> \<bar>real_of_float x\<bar>" |
1804 and "exp x = (\<Sum>m = 0..<get_odd n. (real x) ^ m / (fact m)) + exp t / (fact (get_odd n)) * (real x) ^ (get_odd n)" |
1794 and "exp x = (\<Sum>m = 0..<get_odd n. (real_of_float x) ^ m / (fact m)) + exp t / (fact (get_odd n)) * (real_of_float x) ^ (get_odd n)" |
1805 using Maclaurin_exp_le unfolding atLeast0LessThan by blast |
1795 using Maclaurin_exp_le unfolding atLeast0LessThan by blast |
1806 moreover have "exp t / (fact (get_odd n)) * (real x) ^ (get_odd n) \<le> 0" |
1796 moreover have "exp t / (fact (get_odd n)) * (real_of_float x) ^ (get_odd n) \<le> 0" |
1807 by (auto intro!: mult_nonneg_nonpos divide_nonpos_pos simp add: x_less_zero) |
1797 by (auto intro!: mult_nonneg_nonpos divide_nonpos_pos simp add: x_less_zero) |
1808 ultimately have "exp x \<le> (\<Sum>j = 0..<get_odd n. 1 / (fact j) * real x ^ j)" |
1798 ultimately have "exp x \<le> (\<Sum>j = 0..<get_odd n. 1 / (fact j) * real_of_float x ^ j)" |
1809 using get_odd exp_gt_zero by auto |
1799 using get_odd exp_gt_zero by auto |
1810 also have "\<dots> \<le> ub_exp_horner prec (get_odd n) 1 1 x" |
1800 also have "\<dots> \<le> ub_exp_horner prec (get_odd n) 1 1 x" |
1811 using bounds(2) by auto |
1801 using bounds(2) by auto |
1812 finally show ?thesis . |
1802 finally show ?thesis . |
1813 qed |
1803 qed |
1814 ultimately show ?thesis by auto |
1804 ultimately show ?thesis by auto |
1815 qed |
1805 qed |
1816 |
1806 |
1817 lemma ub_exp_horner_nonneg: "real x \<le> 0 \<Longrightarrow> |
1807 lemma ub_exp_horner_nonneg: "real_of_float x \<le> 0 \<Longrightarrow> |
1818 0 \<le> real (ub_exp_horner prec (get_odd n) (Suc 0) (Suc 0) x)" |
1808 0 \<le> real_of_float (ub_exp_horner prec (get_odd n) (Suc 0) (Suc 0) x)" |
1819 using bnds_exp_horner[of x prec n] |
1809 using bnds_exp_horner[of x prec n] |
1820 by (intro order_trans[OF exp_ge_zero]) auto |
1810 by (intro order_trans[OF exp_ge_zero]) auto |
1821 |
1811 |
1822 |
1812 |
1823 subsection "Compute the exponential function on the entire domain" |
1813 subsection "Compute the exponential function on the entire domain" |
1882 shows "exp x \<in> { (lb_exp prec x) .. (ub_exp prec x)}" |
1872 shows "exp x \<in> { (lb_exp prec x) .. (ub_exp prec x)}" |
1883 proof - |
1873 proof - |
1884 let "?lb_exp_horner x" = "lb_exp_horner prec (get_even (prec + 2)) 1 1 x" |
1874 let "?lb_exp_horner x" = "lb_exp_horner prec (get_even (prec + 2)) 1 1 x" |
1885 let "?ub_exp_horner x" = "ub_exp_horner prec (get_odd (prec + 2)) 1 1 x" |
1875 let "?ub_exp_horner x" = "ub_exp_horner prec (get_odd (prec + 2)) 1 1 x" |
1886 |
1876 |
1887 have "real x \<le> 0" and "\<not> x > 0" |
1877 have "real_of_float x \<le> 0" and "\<not> x > 0" |
1888 using \<open>x \<le> 0\<close> by auto |
1878 using \<open>x \<le> 0\<close> by auto |
1889 show ?thesis |
1879 show ?thesis |
1890 proof (cases "x < - 1") |
1880 proof (cases "x < - 1") |
1891 case False |
1881 case False |
1892 hence "- 1 \<le> real x" by auto |
1882 hence "- 1 \<le> real_of_float x" by auto |
1893 show ?thesis |
1883 show ?thesis |
1894 proof (cases "?lb_exp_horner x \<le> 0") |
1884 proof (cases "?lb_exp_horner x \<le> 0") |
1895 case True |
1885 case True |
1896 from \<open>\<not> x < - 1\<close> |
1886 from \<open>\<not> x < - 1\<close> |
1897 have "- 1 \<le> real x" by auto |
1887 have "- 1 \<le> real_of_float x" by auto |
1898 hence "exp (- 1) \<le> exp x" |
1888 hence "exp (- 1) \<le> exp x" |
1899 unfolding exp_le_cancel_iff . |
1889 unfolding exp_le_cancel_iff . |
1900 from order_trans[OF exp_m1_ge_quarter this] have "Float 1 (- 2) \<le> exp x" |
1890 from order_trans[OF exp_m1_ge_quarter this] have "Float 1 (- 2) \<le> exp x" |
1901 unfolding Float_num . |
1891 unfolding Float_num . |
1902 with True show ?thesis |
1892 with True show ?thesis |
1903 using bnds_exp_horner \<open>real x \<le> 0\<close> \<open>\<not> x > 0\<close> \<open>\<not> x < - 1\<close> by auto |
1893 using bnds_exp_horner \<open>real_of_float x \<le> 0\<close> \<open>\<not> x > 0\<close> \<open>\<not> x < - 1\<close> by auto |
1904 next |
1894 next |
1905 case False |
1895 case False |
1906 thus ?thesis |
1896 thus ?thesis |
1907 using bnds_exp_horner \<open>real x \<le> 0\<close> \<open>\<not> x > 0\<close> \<open>\<not> x < - 1\<close> by (auto simp add: Let_def) |
1897 using bnds_exp_horner \<open>real_of_float x \<le> 0\<close> \<open>\<not> x > 0\<close> \<open>\<not> x < - 1\<close> by (auto simp add: Let_def) |
1908 qed |
1898 qed |
1909 next |
1899 next |
1910 case True |
1900 case True |
1911 let ?num = "nat (- int_floor_fl x)" |
1901 let ?num = "nat (- int_floor_fl x)" |
1912 |
1902 |
1913 have "real (int_floor_fl x) < - 1" |
1903 have "real_of_int (int_floor_fl x) < - 1" |
1914 using int_floor_fl[of x] \<open>x < - 1\<close> by simp |
1904 using int_floor_fl[of x] \<open>x < - 1\<close> by simp |
1915 hence "real (int_floor_fl x) < 0" by simp |
1905 hence "real_of_int (int_floor_fl x) < 0" by simp |
1916 hence "int_floor_fl x < 0" by auto |
1906 hence "int_floor_fl x < 0" by auto |
1917 hence "1 \<le> - int_floor_fl x" by auto |
1907 hence "1 \<le> - int_floor_fl x" by auto |
1918 hence "0 < nat (- int_floor_fl x)" by auto |
1908 hence "0 < nat (- int_floor_fl x)" by auto |
1919 hence "0 < ?num" by auto |
1909 hence "0 < ?num" by auto |
1920 hence "real ?num \<noteq> 0" by auto |
1910 hence "real ?num \<noteq> 0" by auto |
1921 have num_eq: "real ?num = - int_floor_fl x" |
1911 have num_eq: "real ?num = - int_floor_fl x" |
1922 using \<open>0 < nat (- int_floor_fl x)\<close> by auto |
1912 using \<open>0 < nat (- int_floor_fl x)\<close> by auto |
1923 have "0 < - int_floor_fl x" |
1913 have "0 < - int_floor_fl x" |
1924 using \<open>0 < ?num\<close>[unfolded real_of_nat_less_iff[symmetric]] by simp |
1914 using \<open>0 < ?num\<close>[unfolded of_nat_less_iff[symmetric]] by simp |
1925 hence "real (int_floor_fl x) < 0" |
1915 hence "real_of_int (int_floor_fl x) < 0" |
1926 unfolding less_float_def by auto |
1916 unfolding less_float_def by auto |
1927 have fl_eq: "real (- int_floor_fl x) = real (- floor_fl x)" |
1917 have fl_eq: "real_of_int (- int_floor_fl x) = real_of_float (- floor_fl x)" |
1928 by (simp add: floor_fl_def int_floor_fl_def) |
1918 by (simp add: floor_fl_def int_floor_fl_def) |
1929 from \<open>0 < - int_floor_fl x\<close> have "0 \<le> real (- floor_fl x)" |
1919 from \<open>0 < - int_floor_fl x\<close> have "0 \<le> real_of_float (- floor_fl x)" |
1930 by (simp add: floor_fl_def int_floor_fl_def) |
1920 by (simp add: floor_fl_def int_floor_fl_def) |
1931 from \<open>real (int_floor_fl x) < 0\<close> have "real (floor_fl x) < 0" |
1921 from \<open>real_of_int (int_floor_fl x) < 0\<close> have "real_of_float (floor_fl x) < 0" |
1932 by (simp add: floor_fl_def int_floor_fl_def) |
1922 by (simp add: floor_fl_def int_floor_fl_def) |
1933 have "exp x \<le> ub_exp prec x" |
1923 have "exp x \<le> ub_exp prec x" |
1934 proof - |
1924 proof - |
1935 have div_less_zero: "real (float_divr prec x (- floor_fl x)) \<le> 0" |
1925 have div_less_zero: "real_of_float (float_divr prec x (- floor_fl x)) \<le> 0" |
1936 using float_divr_nonpos_pos_upper_bound[OF \<open>real x \<le> 0\<close> \<open>0 \<le> real (- floor_fl x)\<close>] |
1926 using float_divr_nonpos_pos_upper_bound[OF \<open>real_of_float x \<le> 0\<close> \<open>0 \<le> real_of_float (- floor_fl x)\<close>] |
1937 unfolding less_eq_float_def zero_float.rep_eq . |
1927 unfolding less_eq_float_def zero_float.rep_eq . |
1938 |
1928 |
1939 have "exp x = exp (?num * (x / ?num))" |
1929 have "exp x = exp (?num * (x / ?num))" |
1940 using \<open>real ?num \<noteq> 0\<close> by auto |
1930 using \<open>real ?num \<noteq> 0\<close> by auto |
1941 also have "\<dots> = exp (x / ?num) ^ ?num" |
1931 also have "\<dots> = exp (x / ?num) ^ ?num" |
1944 unfolding num_eq fl_eq |
1934 unfolding num_eq fl_eq |
1945 by (rule power_mono, rule exp_le_cancel_iff[THEN iffD2], rule float_divr) auto |
1935 by (rule power_mono, rule exp_le_cancel_iff[THEN iffD2], rule float_divr) auto |
1946 also have "\<dots> \<le> (?ub_exp_horner (float_divr prec x (- floor_fl x))) ^ ?num" |
1936 also have "\<dots> \<le> (?ub_exp_horner (float_divr prec x (- floor_fl x))) ^ ?num" |
1947 unfolding real_of_float_power |
1937 unfolding real_of_float_power |
1948 by (rule power_mono, rule bnds_exp_horner[OF div_less_zero, unfolded atLeastAtMost_iff, THEN conjunct2], auto) |
1938 by (rule power_mono, rule bnds_exp_horner[OF div_less_zero, unfolded atLeastAtMost_iff, THEN conjunct2], auto) |
1949 also have "\<dots> \<le> real (power_up_fl prec (?ub_exp_horner (float_divr prec x (- floor_fl x))) ?num)" |
1939 also have "\<dots> \<le> real_of_float (power_up_fl prec (?ub_exp_horner (float_divr prec x (- floor_fl x))) ?num)" |
1950 by (auto simp add: real_power_up_fl intro!: power_up ub_exp_horner_nonneg div_less_zero) |
1940 by (auto simp add: real_power_up_fl intro!: power_up ub_exp_horner_nonneg div_less_zero) |
1951 finally show ?thesis |
1941 finally show ?thesis |
1952 unfolding ub_exp.simps if_not_P[OF \<open>\<not> 0 < x\<close>] if_P[OF \<open>x < - 1\<close>] floor_fl_def Let_def . |
1942 unfolding ub_exp.simps if_not_P[OF \<open>\<not> 0 < x\<close>] if_P[OF \<open>x < - 1\<close>] floor_fl_def Let_def . |
1953 qed |
1943 qed |
1954 moreover |
1944 moreover |
1958 let ?horner = "?lb_exp_horner ?divl" |
1948 let ?horner = "?lb_exp_horner ?divl" |
1959 |
1949 |
1960 show ?thesis |
1950 show ?thesis |
1961 proof (cases "?horner \<le> 0") |
1951 proof (cases "?horner \<le> 0") |
1962 case False |
1952 case False |
1963 hence "0 \<le> real ?horner" by auto |
1953 hence "0 \<le> real_of_float ?horner" by auto |
1964 |
1954 |
1965 have div_less_zero: "real (float_divl prec x (- floor_fl x)) \<le> 0" |
1955 have div_less_zero: "real_of_float (float_divl prec x (- floor_fl x)) \<le> 0" |
1966 using \<open>real (floor_fl x) < 0\<close> \<open>real x \<le> 0\<close> |
1956 using \<open>real_of_float (floor_fl x) < 0\<close> \<open>real_of_float x \<le> 0\<close> |
1967 by (auto intro!: order_trans[OF float_divl] divide_nonpos_neg) |
1957 by (auto intro!: order_trans[OF float_divl] divide_nonpos_neg) |
1968 |
1958 |
1969 have "(?lb_exp_horner (float_divl prec x (- floor_fl x))) ^ ?num \<le> |
1959 have "(?lb_exp_horner (float_divl prec x (- floor_fl x))) ^ ?num \<le> |
1970 exp (float_divl prec x (- floor_fl x)) ^ ?num" |
1960 exp (float_divl prec x (- floor_fl x)) ^ ?num" |
1971 using \<open>0 \<le> real ?horner\<close>[unfolded floor_fl_def[symmetric]] |
1961 using \<open>0 \<le> real_of_float ?horner\<close>[unfolded floor_fl_def[symmetric]] |
1972 bnds_exp_horner[OF div_less_zero, unfolded atLeastAtMost_iff, THEN conjunct1] |
1962 bnds_exp_horner[OF div_less_zero, unfolded atLeastAtMost_iff, THEN conjunct1] |
1973 by (auto intro!: power_mono) |
1963 by (auto intro!: power_mono) |
1974 also have "\<dots> \<le> exp (x / ?num) ^ ?num" |
1964 also have "\<dots> \<le> exp (x / ?num) ^ ?num" |
1975 unfolding num_eq fl_eq |
1965 unfolding num_eq fl_eq |
1976 using float_divl by (auto intro!: power_mono simp del: uminus_float.rep_eq) |
1966 using float_divl by (auto intro!: power_mono simp del: uminus_float.rep_eq) |
1986 next |
1976 next |
1987 case True |
1977 case True |
1988 have "power_down_fl prec (Float 1 (- 2)) ?num \<le> (Float 1 (- 2)) ^ ?num" |
1978 have "power_down_fl prec (Float 1 (- 2)) ?num \<le> (Float 1 (- 2)) ^ ?num" |
1989 by (metis Float_le_zero_iff less_imp_le linorder_not_less |
1979 by (metis Float_le_zero_iff less_imp_le linorder_not_less |
1990 not_numeral_le_zero numeral_One power_down_fl) |
1980 not_numeral_le_zero numeral_One power_down_fl) |
1991 then have "power_down_fl prec (Float 1 (- 2)) ?num \<le> real (Float 1 (- 2)) ^ ?num" |
1981 then have "power_down_fl prec (Float 1 (- 2)) ?num \<le> real_of_float (Float 1 (- 2)) ^ ?num" |
1992 by simp |
1982 by simp |
1993 also |
1983 also |
1994 have "real (floor_fl x) \<noteq> 0" and "real (floor_fl x) \<le> 0" |
1984 have "real_of_float (floor_fl x) \<noteq> 0" and "real_of_float (floor_fl x) \<le> 0" |
1995 using \<open>real (floor_fl x) < 0\<close> by auto |
1985 using \<open>real_of_float (floor_fl x) < 0\<close> by auto |
1996 from divide_right_mono_neg[OF floor_fl[of x] \<open>real (floor_fl x) \<le> 0\<close>, unfolded divide_self[OF \<open>real (floor_fl x) \<noteq> 0\<close>]] |
1986 from divide_right_mono_neg[OF floor_fl[of x] \<open>real_of_float (floor_fl x) \<le> 0\<close>, unfolded divide_self[OF \<open>real_of_float (floor_fl x) \<noteq> 0\<close>]] |
1997 have "- 1 \<le> x / (- floor_fl x)" |
1987 have "- 1 \<le> x / (- floor_fl x)" |
1998 unfolding minus_float.rep_eq by auto |
1988 unfolding minus_float.rep_eq by auto |
1999 from order_trans[OF exp_m1_ge_quarter this[unfolded exp_le_cancel_iff[where x="- 1", symmetric]]] |
1989 from order_trans[OF exp_m1_ge_quarter this[unfolded exp_le_cancel_iff[where x="- 1", symmetric]]] |
2000 have "Float 1 (- 2) \<le> exp (x / (- floor_fl x))" |
1990 have "Float 1 (- 2) \<le> exp (x / (- floor_fl x))" |
2001 unfolding Float_num . |
1991 unfolding Float_num . |
2002 hence "real (Float 1 (- 2)) ^ ?num \<le> exp (x / (- floor_fl x)) ^ ?num" |
1992 hence "real_of_float (Float 1 (- 2)) ^ ?num \<le> exp (x / (- floor_fl x)) ^ ?num" |
2003 by (metis Float_num(5) power_mono zero_le_divide_1_iff zero_le_numeral) |
1993 by (metis Float_num(5) power_mono zero_le_divide_1_iff zero_le_numeral) |
2004 also have "\<dots> = exp x" |
1994 also have "\<dots> = exp x" |
2005 unfolding num_eq fl_eq exp_real_of_nat_mult[symmetric] |
1995 unfolding num_eq fl_eq exp_real_of_nat_mult[symmetric] |
2006 using \<open>real (floor_fl x) \<noteq> 0\<close> by auto |
1996 using \<open>real_of_float (floor_fl x) \<noteq> 0\<close> by auto |
2007 finally show ?thesis |
1997 finally show ?thesis |
2008 unfolding lb_exp.simps if_not_P[OF \<open>\<not> 0 < x\<close>] if_P[OF \<open>x < - 1\<close>] |
1998 unfolding lb_exp.simps if_not_P[OF \<open>\<not> 0 < x\<close>] if_P[OF \<open>x < - 1\<close>] |
2009 int_floor_fl_def Let_def if_P[OF True] real_of_float_power . |
1999 int_floor_fl_def Let_def if_P[OF True] real_of_float_power . |
2010 qed |
2000 qed |
2011 qed |
2001 qed |
2131 show ?lb and ?ub |
2121 show ?lb and ?ub |
2132 unfolding atLeast0LessThan by auto |
2122 unfolding atLeast0LessThan by auto |
2133 qed |
2123 qed |
2134 |
2124 |
2135 lemma ln_float_bounds: |
2125 lemma ln_float_bounds: |
2136 assumes "0 \<le> real x" |
2126 assumes "0 \<le> real_of_float x" |
2137 and "real x < 1" |
2127 and "real_of_float x < 1" |
2138 shows "x * lb_ln_horner prec (get_even n) 1 x \<le> ln (x + 1)" (is "?lb \<le> ?ln") |
2128 shows "x * lb_ln_horner prec (get_even n) 1 x \<le> ln (x + 1)" (is "?lb \<le> ?ln") |
2139 and "ln (x + 1) \<le> x * ub_ln_horner prec (get_odd n) 1 x" (is "?ln \<le> ?ub") |
2129 and "ln (x + 1) \<le> x * ub_ln_horner prec (get_odd n) 1 x" (is "?ln \<le> ?ub") |
2140 proof - |
2130 proof - |
2141 obtain ev where ev: "get_even n = 2 * ev" using get_even_double .. |
2131 obtain ev where ev: "get_even n = 2 * ev" using get_even_double .. |
2142 obtain od where od: "get_odd n = 2 * od + 1" using get_odd_double .. |
2132 obtain od where od: "get_odd n = 2 * od + 1" using get_odd_double .. |
2143 |
2133 |
2144 let "?s n" = "(- 1) ^ n * (1 / real (1 + n)) * (real x)^(Suc n)" |
2134 let "?s n" = "(- 1) ^ n * (1 / real (1 + n)) * (real_of_float x)^(Suc n)" |
2145 |
2135 |
2146 have "?lb \<le> setsum ?s {0 ..< 2 * ev}" |
2136 have "?lb \<le> setsum ?s {0 ..< 2 * ev}" |
2147 unfolding power_Suc2 mult.assoc[symmetric] times_float.rep_eq setsum_left_distrib[symmetric] |
2137 unfolding power_Suc2 mult.assoc[symmetric] times_float.rep_eq setsum_left_distrib[symmetric] |
2148 unfolding mult.commute[of "real x"] ev |
2138 unfolding mult.commute[of "real_of_float x"] ev |
2149 using horner_bounds(1)[where G="\<lambda> i k. Suc k" and F="\<lambda>x. x" and f="\<lambda>x. x" and lb="\<lambda>n i k x. lb_ln_horner prec n k x" and ub="\<lambda>n i k x. ub_ln_horner prec n k x" and j'=1 and n="2*ev", |
2139 using horner_bounds(1)[where G="\<lambda> i k. Suc k" and F="\<lambda>x. x" and f="\<lambda>x. x" |
2150 OF \<open>0 \<le> real x\<close> refl lb_ln_horner.simps ub_ln_horner.simps] \<open>0 \<le> real x\<close> |
2140 and lb="\<lambda>n i k x. lb_ln_horner prec n k x" |
|
2141 and ub="\<lambda>n i k x. ub_ln_horner prec n k x" and j'=1 and n="2*ev", |
|
2142 OF \<open>0 \<le> real_of_float x\<close> refl lb_ln_horner.simps ub_ln_horner.simps] \<open>0 \<le> real_of_float x\<close> |
|
2143 unfolding real_of_float_power |
2151 by (rule mult_right_mono) |
2144 by (rule mult_right_mono) |
2152 also have "\<dots> \<le> ?ln" |
2145 also have "\<dots> \<le> ?ln" |
2153 using ln_bounds(1)[OF \<open>0 \<le> real x\<close> \<open>real x < 1\<close>] by auto |
2146 using ln_bounds(1)[OF \<open>0 \<le> real_of_float x\<close> \<open>real_of_float x < 1\<close>] by auto |
2154 finally show "?lb \<le> ?ln" . |
2147 finally show "?lb \<le> ?ln" . |
2155 |
2148 |
2156 have "?ln \<le> setsum ?s {0 ..< 2 * od + 1}" |
2149 have "?ln \<le> setsum ?s {0 ..< 2 * od + 1}" |
2157 using ln_bounds(2)[OF \<open>0 \<le> real x\<close> \<open>real x < 1\<close>] by auto |
2150 using ln_bounds(2)[OF \<open>0 \<le> real_of_float x\<close> \<open>real_of_float x < 1\<close>] by auto |
2158 also have "\<dots> \<le> ?ub" |
2151 also have "\<dots> \<le> ?ub" |
2159 unfolding power_Suc2 mult.assoc[symmetric] times_float.rep_eq setsum_left_distrib[symmetric] |
2152 unfolding power_Suc2 mult.assoc[symmetric] times_float.rep_eq setsum_left_distrib[symmetric] |
2160 unfolding mult.commute[of "real x"] od |
2153 unfolding mult.commute[of "real_of_float x"] od |
2161 using horner_bounds(2)[where G="\<lambda> i k. Suc k" and F="\<lambda>x. x" and f="\<lambda>x. x" and lb="\<lambda>n i k x. lb_ln_horner prec n k x" and ub="\<lambda>n i k x. ub_ln_horner prec n k x" and j'=1 and n="2*od+1", |
2154 using horner_bounds(2)[where G="\<lambda> i k. Suc k" and F="\<lambda>x. x" and f="\<lambda>x. x" and lb="\<lambda>n i k x. lb_ln_horner prec n k x" and ub="\<lambda>n i k x. ub_ln_horner prec n k x" and j'=1 and n="2*od+1", |
2162 OF \<open>0 \<le> real x\<close> refl lb_ln_horner.simps ub_ln_horner.simps] \<open>0 \<le> real x\<close> |
2155 OF \<open>0 \<le> real_of_float x\<close> refl lb_ln_horner.simps ub_ln_horner.simps] \<open>0 \<le> real_of_float x\<close> |
|
2156 unfolding real_of_float_power |
2163 by (rule mult_right_mono) |
2157 by (rule mult_right_mono) |
2164 finally show "?ln \<le> ?ub" . |
2158 finally show "?ln \<le> ?ub" . |
2165 qed |
2159 qed |
2166 |
2160 |
2167 lemma ln_add: |
2161 lemma ln_add: |
2199 let ?lthird = "lapprox_rat prec 1 3" |
2193 let ?lthird = "lapprox_rat prec 1 3" |
2200 |
2194 |
2201 have ln2_sum: "ln 2 = ln (1/2 + 1) + ln (1 / 3 + 1::real)" |
2195 have ln2_sum: "ln 2 = ln (1/2 + 1) + ln (1 / 3 + 1::real)" |
2202 using ln_add[of "3 / 2" "1 / 2"] by auto |
2196 using ln_add[of "3 / 2" "1 / 2"] by auto |
2203 have lb3: "?lthird \<le> 1 / 3" using lapprox_rat[of prec 1 3] by auto |
2197 have lb3: "?lthird \<le> 1 / 3" using lapprox_rat[of prec 1 3] by auto |
2204 hence lb3_ub: "real ?lthird < 1" by auto |
2198 hence lb3_ub: "real_of_float ?lthird < 1" by auto |
2205 have lb3_lb: "0 \<le> real ?lthird" using lapprox_rat_nonneg[of 1 3] by auto |
2199 have lb3_lb: "0 \<le> real_of_float ?lthird" using lapprox_rat_nonneg[of 1 3] by auto |
2206 have ub3: "1 / 3 \<le> ?uthird" using rapprox_rat[of 1 3] by auto |
2200 have ub3: "1 / 3 \<le> ?uthird" using rapprox_rat[of 1 3] by auto |
2207 hence ub3_lb: "0 \<le> real ?uthird" by auto |
2201 hence ub3_lb: "0 \<le> real_of_float ?uthird" by auto |
2208 |
2202 |
2209 have lb2: "0 \<le> real (Float 1 (- 1))" and ub2: "real (Float 1 (- 1)) < 1" |
2203 have lb2: "0 \<le> real_of_float (Float 1 (- 1))" and ub2: "real_of_float (Float 1 (- 1)) < 1" |
2210 unfolding Float_num by auto |
2204 unfolding Float_num by auto |
2211 |
2205 |
2212 have "0 \<le> (1::int)" and "0 < (3::int)" by auto |
2206 have "0 \<le> (1::int)" and "0 < (3::int)" by auto |
2213 have ub3_ub: "real ?uthird < 1" |
2207 have ub3_ub: "real_of_float ?uthird < 1" |
2214 by (simp add: Float.compute_rapprox_rat Float.compute_lapprox_rat rapprox_posrat_less1) |
2208 by (simp add: Float.compute_rapprox_rat Float.compute_lapprox_rat rapprox_posrat_less1) |
2215 |
2209 |
2216 have third_gt0: "(0 :: real) < 1 / 3 + 1" by auto |
2210 have third_gt0: "(0 :: real) < 1 / 3 + 1" by auto |
2217 have uthird_gt0: "0 < real ?uthird + 1" using ub3_lb by auto |
2211 have uthird_gt0: "0 < real_of_float ?uthird + 1" using ub3_lb by auto |
2218 have lthird_gt0: "0 < real ?lthird + 1" using lb3_lb by auto |
2212 have lthird_gt0: "0 < real_of_float ?lthird + 1" using lb3_lb by auto |
2219 |
2213 |
2220 show ?ub_ln2 |
2214 show ?ub_ln2 |
2221 unfolding ub_ln2_def Let_def ln2_sum Float_num(4)[symmetric] |
2215 unfolding ub_ln2_def Let_def ln2_sum Float_num(4)[symmetric] |
2222 proof (rule float_plus_up_le, rule add_mono, fact ln_float_bounds(2)[OF lb2 ub2]) |
2216 proof (rule float_plus_up_le, rule add_mono, fact ln_float_bounds(2)[OF lb2 ub2]) |
2223 have "ln (1 / 3 + 1) \<le> ln (real ?uthird + 1)" |
2217 have "ln (1 / 3 + 1) \<le> ln (real_of_float ?uthird + 1)" |
2224 unfolding ln_le_cancel_iff[OF third_gt0 uthird_gt0] using ub3 by auto |
2218 unfolding ln_le_cancel_iff[OF third_gt0 uthird_gt0] using ub3 by auto |
2225 also have "\<dots> \<le> ?uthird * ub_ln_horner prec (get_odd prec) 1 ?uthird" |
2219 also have "\<dots> \<le> ?uthird * ub_ln_horner prec (get_odd prec) 1 ?uthird" |
2226 using ln_float_bounds(2)[OF ub3_lb ub3_ub] . |
2220 using ln_float_bounds(2)[OF ub3_lb ub3_ub] . |
2227 also note float_round_up |
2221 also note float_round_up |
2228 finally show "ln (1 / 3 + 1) \<le> float_round_up prec (?uthird * ub_ln_horner prec (get_odd prec) 1 ?uthird)" . |
2222 finally show "ln (1 / 3 + 1) \<le> float_round_up prec (?uthird * ub_ln_horner prec (get_odd prec) 1 ?uthird)" . |
2229 qed |
2223 qed |
2230 show ?lb_ln2 |
2224 show ?lb_ln2 |
2231 unfolding lb_ln2_def Let_def ln2_sum Float_num(4)[symmetric] |
2225 unfolding lb_ln2_def Let_def ln2_sum Float_num(4)[symmetric] |
2232 proof (rule float_plus_down_le, rule add_mono, fact ln_float_bounds(1)[OF lb2 ub2]) |
2226 proof (rule float_plus_down_le, rule add_mono, fact ln_float_bounds(1)[OF lb2 ub2]) |
2233 have "?lthird * lb_ln_horner prec (get_even prec) 1 ?lthird \<le> ln (real ?lthird + 1)" |
2227 have "?lthird * lb_ln_horner prec (get_even prec) 1 ?lthird \<le> ln (real_of_float ?lthird + 1)" |
2234 using ln_float_bounds(1)[OF lb3_lb lb3_ub] . |
2228 using ln_float_bounds(1)[OF lb3_lb lb3_ub] . |
2235 note float_round_down_le[OF this] |
2229 note float_round_down_le[OF this] |
2236 also have "\<dots> \<le> ln (1 / 3 + 1)" |
2230 also have "\<dots> \<le> ln (1 / 3 + 1)" |
2237 unfolding ln_le_cancel_iff[OF lthird_gt0 third_gt0] |
2231 unfolding ln_le_cancel_iff[OF lthird_gt0 third_gt0] |
2238 using lb3 by auto |
2232 using lb3 by auto |
2263 by pat_completeness auto |
2257 by pat_completeness auto |
2264 |
2258 |
2265 termination |
2259 termination |
2266 proof (relation "measure (\<lambda> v. let (prec, x) = case_sum id id v in (if x < 1 then 1 else 0))", auto) |
2260 proof (relation "measure (\<lambda> v. let (prec, x) = case_sum id id v in (if x < 1 then 1 else 0))", auto) |
2267 fix prec and x :: float |
2261 fix prec and x :: float |
2268 assume "\<not> real x \<le> 0" and "real x < 1" and "real (float_divl (max prec (Suc 0)) 1 x) < 1" |
2262 assume "\<not> real_of_float x \<le> 0" and "real_of_float x < 1" and "real_of_float (float_divl (max prec (Suc 0)) 1 x) < 1" |
2269 hence "0 < real x" "1 \<le> max prec (Suc 0)" "real x < 1" |
2263 hence "0 < real_of_float x" "1 \<le> max prec (Suc 0)" "real_of_float x < 1" |
2270 by auto |
2264 by auto |
2271 from float_divl_pos_less1_bound[OF \<open>0 < real x\<close> \<open>real x < 1\<close>[THEN less_imp_le] \<open>1 \<le> max prec (Suc 0)\<close>] |
2265 from float_divl_pos_less1_bound[OF \<open>0 < real_of_float x\<close> \<open>real_of_float x < 1\<close>[THEN less_imp_le] \<open>1 \<le> max prec (Suc 0)\<close>] |
2272 show False |
2266 show False |
2273 using \<open>real (float_divl (max prec (Suc 0)) 1 x) < 1\<close> by auto |
2267 using \<open>real_of_float (float_divl (max prec (Suc 0)) 1 x) < 1\<close> by auto |
2274 next |
2268 next |
2275 fix prec x |
2269 fix prec x |
2276 assume "\<not> real x \<le> 0" and "real x < 1" and "real (float_divr prec 1 x) < 1" |
2270 assume "\<not> real_of_float x \<le> 0" and "real_of_float x < 1" and "real_of_float (float_divr prec 1 x) < 1" |
2277 hence "0 < x" by auto |
2271 hence "0 < x" by auto |
2278 from float_divr_pos_less1_lower_bound[OF \<open>0 < x\<close>, of prec] \<open>real x < 1\<close> show False |
2272 from float_divr_pos_less1_lower_bound[OF \<open>0 < x\<close>, of prec] \<open>real_of_float x < 1\<close> show False |
2279 using \<open>real (float_divr prec 1 x) < 1\<close> by auto |
2273 using \<open>real_of_float (float_divr prec 1 x) < 1\<close> by auto |
2280 qed |
2274 qed |
2281 |
2275 |
2282 lemma float_pos_eq_mantissa_pos: "x > 0 \<longleftrightarrow> mantissa x > 0" |
2276 lemma float_pos_eq_mantissa_pos: "x > 0 \<longleftrightarrow> mantissa x > 0" |
2283 apply (subst Float_mantissa_exponent[of x, symmetric]) |
2277 apply (subst Float_mantissa_exponent[of x, symmetric]) |
2284 apply (auto simp add: zero_less_mult_iff zero_float_def dest: less_zeroE) |
2278 apply (auto simp add: zero_less_mult_iff zero_float_def dest: less_zeroE) |
2348 assumes "0 < m" |
2342 assumes "0 < m" |
2349 shows "ln (Float m e) = ln 2 * (e + (bitlen m - 1)) + ln (Float m (- (bitlen m - 1)))" |
2343 shows "ln (Float m e) = ln 2 * (e + (bitlen m - 1)) + ln (Float m (- (bitlen m - 1)))" |
2350 proof - |
2344 proof - |
2351 let ?B = "2^nat (bitlen m - 1)" |
2345 let ?B = "2^nat (bitlen m - 1)" |
2352 def bl \<equiv> "bitlen m - 1" |
2346 def bl \<equiv> "bitlen m - 1" |
2353 have "0 < real m" and "\<And>X. (0 :: real) < 2^X" and "0 < (2 :: real)" and "m \<noteq> 0" |
2347 have "0 < real_of_int m" and "\<And>X. (0 :: real) < 2^X" and "0 < (2 :: real)" and "m \<noteq> 0" |
2354 using assms by auto |
2348 using assms by auto |
2355 hence "0 \<le> bl" by (simp add: bitlen_def bl_def) |
2349 hence "0 \<le> bl" by (simp add: bitlen_def bl_def) |
2356 show ?thesis |
2350 show ?thesis |
2357 proof (cases "0 \<le> e") |
2351 proof (cases "0 \<le> e") |
2358 case True |
2352 case True |
2359 thus ?thesis |
2353 thus ?thesis |
2360 unfolding bl_def[symmetric] using \<open>0 < real m\<close> \<open>0 \<le> bl\<close> |
2354 unfolding bl_def[symmetric] using \<open>0 < real_of_int m\<close> \<open>0 \<le> bl\<close> |
2361 apply (simp add: ln_mult) |
2355 apply (simp add: ln_mult) |
2362 apply (cases "e=0") |
2356 apply (cases "e=0") |
2363 apply (cases "bl = 0", simp_all add: powr_minus ln_inverse ln_powr) |
2357 apply (cases "bl = 0", simp_all add: powr_minus ln_inverse ln_powr) |
2364 apply (cases "bl = 0", simp_all add: powr_minus ln_inverse ln_powr field_simps) |
2358 apply (cases "bl = 0", simp_all add: powr_minus ln_inverse ln_powr field_simps) |
2365 done |
2359 done |
2366 next |
2360 next |
2367 case False |
2361 case False |
2368 hence "0 < -e" by auto |
2362 hence "0 < -e" by auto |
2369 have lne: "ln (2 powr real e) = ln (inverse (2 powr - e))" |
2363 have lne: "ln (2 powr real_of_int e) = ln (inverse (2 powr - e))" |
2370 by (simp add: powr_minus) |
2364 by (simp add: powr_minus) |
2371 hence pow_gt0: "(0::real) < 2^nat (-e)" |
2365 hence pow_gt0: "(0::real) < 2^nat (-e)" |
2372 by auto |
2366 by auto |
2373 hence inv_gt0: "(0::real) < inverse (2^nat (-e))" |
2367 hence inv_gt0: "(0::real) < inverse (2^nat (-e))" |
2374 by auto |
2368 by auto |
2375 show ?thesis |
2369 show ?thesis |
2376 using False unfolding bl_def[symmetric] |
2370 using False unfolding bl_def[symmetric] |
2377 using \<open>0 < real m\<close> \<open>0 \<le> bl\<close> |
2371 using \<open>0 < real_of_int m\<close> \<open>0 \<le> bl\<close> |
2378 by (auto simp add: lne ln_mult ln_powr ln_div field_simps) |
2372 by (auto simp add: lne ln_mult ln_powr ln_div field_simps) |
2379 qed |
2373 qed |
2380 qed |
2374 qed |
2381 |
2375 |
2382 lemma ub_ln_lb_ln_bounds': |
2376 lemma ub_ln_lb_ln_bounds': |
2383 assumes "1 \<le> x" |
2377 assumes "1 \<le> x" |
2384 shows "the (lb_ln prec x) \<le> ln x \<and> ln x \<le> the (ub_ln prec x)" |
2378 shows "the (lb_ln prec x) \<le> ln x \<and> ln x \<le> the (ub_ln prec x)" |
2385 (is "?lb \<le> ?ln \<and> ?ln \<le> ?ub") |
2379 (is "?lb \<le> ?ln \<and> ?ln \<le> ?ub") |
2386 proof (cases "x < Float 1 1") |
2380 proof (cases "x < Float 1 1") |
2387 case True |
2381 case True |
2388 hence "real (x - 1) < 1" and "real x < 2" by auto |
2382 hence "real_of_float (x - 1) < 1" and "real_of_float x < 2" by auto |
2389 have "\<not> x \<le> 0" and "\<not> x < 1" using \<open>1 \<le> x\<close> by auto |
2383 have "\<not> x \<le> 0" and "\<not> x < 1" using \<open>1 \<le> x\<close> by auto |
2390 hence "0 \<le> real (x - 1)" using \<open>1 \<le> x\<close> by auto |
2384 hence "0 \<le> real_of_float (x - 1)" using \<open>1 \<le> x\<close> by auto |
2391 |
2385 |
2392 have [simp]: "(Float 3 (- 1)) = 3 / 2" by simp |
2386 have [simp]: "(Float 3 (- 1)) = 3 / 2" by simp |
2393 |
2387 |
2394 show ?thesis |
2388 show ?thesis |
2395 proof (cases "x \<le> Float 3 (- 1)") |
2389 proof (cases "x \<le> Float 3 (- 1)") |
2396 case True |
2390 case True |
2397 show ?thesis |
2391 show ?thesis |
2398 unfolding lb_ln.simps |
2392 unfolding lb_ln.simps |
2399 unfolding ub_ln.simps Let_def |
2393 unfolding ub_ln.simps Let_def |
2400 using ln_float_bounds[OF \<open>0 \<le> real (x - 1)\<close> \<open>real (x - 1) < 1\<close>, of prec] |
2394 using ln_float_bounds[OF \<open>0 \<le> real_of_float (x - 1)\<close> \<open>real_of_float (x - 1) < 1\<close>, of prec] |
2401 \<open>\<not> x \<le> 0\<close> \<open>\<not> x < 1\<close> True |
2395 \<open>\<not> x \<le> 0\<close> \<open>\<not> x < 1\<close> True |
2402 by (auto intro!: float_round_down_le float_round_up_le) |
2396 by (auto intro!: float_round_down_le float_round_up_le) |
2403 next |
2397 next |
2404 case False |
2398 case False |
2405 hence *: "3 / 2 < x" by auto |
2399 hence *: "3 / 2 < x" by auto |
2406 |
2400 |
2407 with ln_add[of "3 / 2" "x - 3 / 2"] |
2401 with ln_add[of "3 / 2" "x - 3 / 2"] |
2408 have add: "ln x = ln (3 / 2) + ln (real x * 2 / 3)" |
2402 have add: "ln x = ln (3 / 2) + ln (real_of_float x * 2 / 3)" |
2409 by (auto simp add: algebra_simps diff_divide_distrib) |
2403 by (auto simp add: algebra_simps diff_divide_distrib) |
2410 |
2404 |
2411 let "?ub_horner x" = "float_round_up prec (x * ub_ln_horner prec (get_odd prec) 1 x)" |
2405 let "?ub_horner x" = "float_round_up prec (x * ub_ln_horner prec (get_odd prec) 1 x)" |
2412 let "?lb_horner x" = "float_round_down prec (x * lb_ln_horner prec (get_even prec) 1 x)" |
2406 let "?lb_horner x" = "float_round_down prec (x * lb_ln_horner prec (get_even prec) 1 x)" |
2413 |
2407 |
2414 { have up: "real (rapprox_rat prec 2 3) \<le> 1" |
2408 { have up: "real_of_float (rapprox_rat prec 2 3) \<le> 1" |
2415 by (rule rapprox_rat_le1) simp_all |
2409 by (rule rapprox_rat_le1) simp_all |
2416 have low: "2 / 3 \<le> rapprox_rat prec 2 3" |
2410 have low: "2 / 3 \<le> rapprox_rat prec 2 3" |
2417 by (rule order_trans[OF _ rapprox_rat]) simp |
2411 by (rule order_trans[OF _ rapprox_rat]) simp |
2418 from mult_less_le_imp_less[OF * low] * |
2412 from mult_less_le_imp_less[OF * low] * |
2419 have pos: "0 < real (x * rapprox_rat prec 2 3 - 1)" by auto |
2413 have pos: "0 < real_of_float (x * rapprox_rat prec 2 3 - 1)" by auto |
2420 |
2414 |
2421 have "ln (real x * 2/3) |
2415 have "ln (real_of_float x * 2/3) |
2422 \<le> ln (real (x * rapprox_rat prec 2 3 - 1) + 1)" |
2416 \<le> ln (real_of_float (x * rapprox_rat prec 2 3 - 1) + 1)" |
2423 proof (rule ln_le_cancel_iff[symmetric, THEN iffD1]) |
2417 proof (rule ln_le_cancel_iff[symmetric, THEN iffD1]) |
2424 show "real x * 2 / 3 \<le> real (x * rapprox_rat prec 2 3 - 1) + 1" |
2418 show "real_of_float x * 2 / 3 \<le> real_of_float (x * rapprox_rat prec 2 3 - 1) + 1" |
2425 using * low by auto |
2419 using * low by auto |
2426 show "0 < real x * 2 / 3" using * by simp |
2420 show "0 < real_of_float x * 2 / 3" using * by simp |
2427 show "0 < real (x * rapprox_rat prec 2 3 - 1) + 1" using pos by auto |
2421 show "0 < real_of_float (x * rapprox_rat prec 2 3 - 1) + 1" using pos by auto |
2428 qed |
2422 qed |
2429 also have "\<dots> \<le> ?ub_horner (x * rapprox_rat prec 2 3 - 1)" |
2423 also have "\<dots> \<le> ?ub_horner (x * rapprox_rat prec 2 3 - 1)" |
2430 proof (rule float_round_up_le, rule ln_float_bounds(2)) |
2424 proof (rule float_round_up_le, rule ln_float_bounds(2)) |
2431 from mult_less_le_imp_less[OF \<open>real x < 2\<close> up] low * |
2425 from mult_less_le_imp_less[OF \<open>real_of_float x < 2\<close> up] low * |
2432 show "real (x * rapprox_rat prec 2 3 - 1) < 1" by auto |
2426 show "real_of_float (x * rapprox_rat prec 2 3 - 1) < 1" by auto |
2433 show "0 \<le> real (x * rapprox_rat prec 2 3 - 1)" using pos by auto |
2427 show "0 \<le> real_of_float (x * rapprox_rat prec 2 3 - 1)" using pos by auto |
2434 qed |
2428 qed |
2435 finally have "ln x \<le> ?ub_horner (Float 1 (-1)) |
2429 finally have "ln x \<le> ?ub_horner (Float 1 (-1)) |
2436 + ?ub_horner ((x * rapprox_rat prec 2 3 - 1))" |
2430 + ?ub_horner ((x * rapprox_rat prec 2 3 - 1))" |
2437 using ln_float_bounds(2)[of "Float 1 (- 1)" prec prec] add |
2431 using ln_float_bounds(2)[of "Float 1 (- 1)" prec prec] add |
2438 by (auto intro!: add_mono float_round_up_le) |
2432 by (auto intro!: add_mono float_round_up_le) |
2442 { let ?max = "max (x * lapprox_rat prec 2 3 - 1) 0" |
2436 { let ?max = "max (x * lapprox_rat prec 2 3 - 1) 0" |
2443 |
2437 |
2444 have up: "lapprox_rat prec 2 3 \<le> 2/3" |
2438 have up: "lapprox_rat prec 2 3 \<le> 2/3" |
2445 by (rule order_trans[OF lapprox_rat], simp) |
2439 by (rule order_trans[OF lapprox_rat], simp) |
2446 |
2440 |
2447 have low: "0 \<le> real (lapprox_rat prec 2 3)" |
2441 have low: "0 \<le> real_of_float (lapprox_rat prec 2 3)" |
2448 using lapprox_rat_nonneg[of 2 3 prec] by simp |
2442 using lapprox_rat_nonneg[of 2 3 prec] by simp |
2449 |
2443 |
2450 have "?lb_horner ?max |
2444 have "?lb_horner ?max |
2451 \<le> ln (real ?max + 1)" |
2445 \<le> ln (real_of_float ?max + 1)" |
2452 proof (rule float_round_down_le, rule ln_float_bounds(1)) |
2446 proof (rule float_round_down_le, rule ln_float_bounds(1)) |
2453 from mult_less_le_imp_less[OF \<open>real x < 2\<close> up] * low |
2447 from mult_less_le_imp_less[OF \<open>real_of_float x < 2\<close> up] * low |
2454 show "real ?max < 1" by (cases "real (lapprox_rat prec 2 3) = 0", |
2448 show "real_of_float ?max < 1" by (cases "real_of_float (lapprox_rat prec 2 3) = 0", |
2455 auto simp add: real_of_float_max) |
2449 auto simp add: real_of_float_max) |
2456 show "0 \<le> real ?max" by (auto simp add: real_of_float_max) |
2450 show "0 \<le> real_of_float ?max" by (auto simp add: real_of_float_max) |
2457 qed |
2451 qed |
2458 also have "\<dots> \<le> ln (real x * 2/3)" |
2452 also have "\<dots> \<le> ln (real_of_float x * 2/3)" |
2459 proof (rule ln_le_cancel_iff[symmetric, THEN iffD1]) |
2453 proof (rule ln_le_cancel_iff[symmetric, THEN iffD1]) |
2460 show "0 < real ?max + 1" by (auto simp add: real_of_float_max) |
2454 show "0 < real_of_float ?max + 1" by (auto simp add: real_of_float_max) |
2461 show "0 < real x * 2/3" using * by auto |
2455 show "0 < real_of_float x * 2/3" using * by auto |
2462 show "real ?max + 1 \<le> real x * 2/3" using * up |
2456 show "real_of_float ?max + 1 \<le> real_of_float x * 2/3" using * up |
2463 by (cases "0 < real x * real (lapprox_posrat prec 2 3) - 1", |
2457 by (cases "0 < real_of_float x * real_of_float (lapprox_posrat prec 2 3) - 1", |
2464 auto simp add: max_def) |
2458 auto simp add: max_def) |
2465 qed |
2459 qed |
2466 finally have "?lb_horner (Float 1 (- 1)) + ?lb_horner ?max \<le> ln x" |
2460 finally have "?lb_horner (Float 1 (- 1)) + ?lb_horner ?max \<le> ln x" |
2467 using ln_float_bounds(1)[of "Float 1 (- 1)" prec prec] add |
2461 using ln_float_bounds(1)[of "Float 1 (- 1)" prec prec] add |
2468 by (auto intro!: add_mono float_round_down_le) |
2462 by (auto intro!: add_mono float_round_down_le) |
2493 hence "bl \<ge> 0" |
2487 hence "bl \<ge> 0" |
2494 using \<open>m > 0\<close> by (simp add: bitlen_def) |
2488 using \<open>m > 0\<close> by (simp add: bitlen_def) |
2495 have "1 \<le> Float m e" |
2489 have "1 \<le> Float m e" |
2496 using \<open>1 \<le> x\<close> Float unfolding less_eq_float_def by auto |
2490 using \<open>1 \<le> x\<close> Float unfolding less_eq_float_def by auto |
2497 from bitlen_div[OF \<open>0 < m\<close>] float_gt1_scale[OF \<open>1 \<le> Float m e\<close>] \<open>bl \<ge> 0\<close> |
2491 from bitlen_div[OF \<open>0 < m\<close>] float_gt1_scale[OF \<open>1 \<le> Float m e\<close>] \<open>bl \<ge> 0\<close> |
2498 have x_bnds: "0 \<le> real (?x - 1)" "real (?x - 1) < 1" |
2492 have x_bnds: "0 \<le> real_of_float (?x - 1)" "real_of_float (?x - 1) < 1" |
2499 unfolding bl_def[symmetric] |
2493 unfolding bl_def[symmetric] |
2500 by (auto simp: powr_realpow[symmetric] field_simps inverse_eq_divide) |
2494 by (auto simp: powr_realpow[symmetric] field_simps inverse_eq_divide) |
2501 (auto simp : powr_minus field_simps inverse_eq_divide) |
2495 (auto simp : powr_minus field_simps inverse_eq_divide) |
2502 |
2496 |
2503 { |
2497 { |
2504 have "float_round_down prec (lb_ln2 prec * ?s) \<le> ln 2 * (e + (bitlen m - 1))" |
2498 have "float_round_down prec (lb_ln2 prec * ?s) \<le> ln 2 * (e + (bitlen m - 1))" |
2505 (is "real ?lb2 \<le> _") |
2499 (is "real_of_float ?lb2 \<le> _") |
2506 apply (rule float_round_down_le) |
2500 apply (rule float_round_down_le) |
2507 unfolding nat_0 power_0 mult_1_right times_float.rep_eq |
2501 unfolding nat_0 power_0 mult_1_right times_float.rep_eq |
2508 using lb_ln2[of prec] |
2502 using lb_ln2[of prec] |
2509 proof (rule mult_mono) |
2503 proof (rule mult_mono) |
2510 from float_gt1_scale[OF \<open>1 \<le> Float m e\<close>] |
2504 from float_gt1_scale[OF \<open>1 \<le> Float m e\<close>] |
2511 show "0 \<le> real (Float (e + (bitlen m - 1)) 0)" by simp |
2505 show "0 \<le> real_of_float (Float (e + (bitlen m - 1)) 0)" by simp |
2512 qed auto |
2506 qed auto |
2513 moreover |
2507 moreover |
2514 from ln_float_bounds(1)[OF x_bnds] |
2508 from ln_float_bounds(1)[OF x_bnds] |
2515 have "float_round_down prec ((?x - 1) * lb_ln_horner prec (get_even prec) 1 (?x - 1)) \<le> ln ?x" (is "real ?lb_horner \<le> _") |
2509 have "float_round_down prec ((?x - 1) * lb_ln_horner prec (get_even prec) 1 (?x - 1)) \<le> ln ?x" (is "real_of_float ?lb_horner \<le> _") |
2516 by (auto intro!: float_round_down_le) |
2510 by (auto intro!: float_round_down_le) |
2517 ultimately have "float_plus_down prec ?lb2 ?lb_horner \<le> ln x" |
2511 ultimately have "float_plus_down prec ?lb2 ?lb_horner \<le> ln x" |
2518 unfolding Float ln_shifted_float[OF \<open>0 < m\<close>, of e] by (auto intro!: float_plus_down_le) |
2512 unfolding Float ln_shifted_float[OF \<open>0 < m\<close>, of e] by (auto intro!: float_plus_down_le) |
2519 } |
2513 } |
2520 moreover |
2514 moreover |
2521 { |
2515 { |
2522 from ln_float_bounds(2)[OF x_bnds] |
2516 from ln_float_bounds(2)[OF x_bnds] |
2523 have "ln ?x \<le> float_round_up prec ((?x - 1) * ub_ln_horner prec (get_odd prec) 1 (?x - 1))" |
2517 have "ln ?x \<le> float_round_up prec ((?x - 1) * ub_ln_horner prec (get_odd prec) 1 (?x - 1))" |
2524 (is "_ \<le> real ?ub_horner") |
2518 (is "_ \<le> real_of_float ?ub_horner") |
2525 by (auto intro!: float_round_up_le) |
2519 by (auto intro!: float_round_up_le) |
2526 moreover |
2520 moreover |
2527 have "ln 2 * (e + (bitlen m - 1)) \<le> float_round_up prec (ub_ln2 prec * ?s)" |
2521 have "ln 2 * (e + (bitlen m - 1)) \<le> float_round_up prec (ub_ln2 prec * ?s)" |
2528 (is "_ \<le> real ?ub2") |
2522 (is "_ \<le> real_of_float ?ub2") |
2529 apply (rule float_round_up_le) |
2523 apply (rule float_round_up_le) |
2530 unfolding nat_0 power_0 mult_1_right times_float.rep_eq |
2524 unfolding nat_0 power_0 mult_1_right times_float.rep_eq |
2531 using ub_ln2[of prec] |
2525 using ub_ln2[of prec] |
2532 proof (rule mult_mono) |
2526 proof (rule mult_mono) |
2533 from float_gt1_scale[OF \<open>1 \<le> Float m e\<close>] |
2527 from float_gt1_scale[OF \<open>1 \<le> Float m e\<close>] |
2534 show "0 \<le> real (e + (bitlen m - 1))" by auto |
2528 show "0 \<le> real_of_int (e + (bitlen m - 1))" by auto |
2535 have "0 \<le> ln (2 :: real)" by simp |
2529 have "0 \<le> ln (2 :: real)" by simp |
2536 thus "0 \<le> real (ub_ln2 prec)" using ub_ln2[of prec] by arith |
2530 thus "0 \<le> real_of_float (ub_ln2 prec)" using ub_ln2[of prec] by arith |
2537 qed auto |
2531 qed auto |
2538 ultimately have "ln x \<le> float_plus_up prec ?ub2 ?ub_horner" |
2532 ultimately have "ln x \<le> float_plus_up prec ?ub2 ?ub_horner" |
2539 unfolding Float ln_shifted_float[OF \<open>0 < m\<close>, of e] |
2533 unfolding Float ln_shifted_float[OF \<open>0 < m\<close>, of e] |
2540 by (auto intro!: float_plus_up_le) |
2534 by (auto intro!: float_plus_up_le) |
2541 } |
2535 } |
2560 show ?thesis |
2554 show ?thesis |
2561 using ub_ln_lb_ln_bounds'[OF \<open>1 \<le> x\<close>] . |
2555 using ub_ln_lb_ln_bounds'[OF \<open>1 \<le> x\<close>] . |
2562 next |
2556 next |
2563 case True |
2557 case True |
2564 have "\<not> x \<le> 0" using \<open>0 < x\<close> by auto |
2558 have "\<not> x \<le> 0" using \<open>0 < x\<close> by auto |
2565 from True have "real x \<le> 1" "x \<le> 1" |
2559 from True have "real_of_float x \<le> 1" "x \<le> 1" |
2566 by simp_all |
2560 by simp_all |
2567 have "0 < real x" and "real x \<noteq> 0" |
2561 have "0 < real_of_float x" and "real_of_float x \<noteq> 0" |
2568 using \<open>0 < x\<close> by auto |
2562 using \<open>0 < x\<close> by auto |
2569 hence A: "0 < 1 / real x" by auto |
2563 hence A: "0 < 1 / real_of_float x" by auto |
2570 |
2564 |
2571 { |
2565 { |
2572 let ?divl = "float_divl (max prec 1) 1 x" |
2566 let ?divl = "float_divl (max prec 1) 1 x" |
2573 have A': "1 \<le> ?divl" using float_divl_pos_less1_bound[OF \<open>0 < real x\<close> \<open>real x \<le> 1\<close>] by auto |
2567 have A': "1 \<le> ?divl" using float_divl_pos_less1_bound[OF \<open>0 < real_of_float x\<close> \<open>real_of_float x \<le> 1\<close>] by auto |
2574 hence B: "0 < real ?divl" by auto |
2568 hence B: "0 < real_of_float ?divl" by auto |
2575 |
2569 |
2576 have "ln ?divl \<le> ln (1 / x)" unfolding ln_le_cancel_iff[OF B A] using float_divl[of _ 1 x] by auto |
2570 have "ln ?divl \<le> ln (1 / x)" unfolding ln_le_cancel_iff[OF B A] using float_divl[of _ 1 x] by auto |
2577 hence "ln x \<le> - ln ?divl" unfolding nonzero_inverse_eq_divide[OF \<open>real x \<noteq> 0\<close>, symmetric] ln_inverse[OF \<open>0 < real x\<close>] by auto |
2571 hence "ln x \<le> - ln ?divl" unfolding nonzero_inverse_eq_divide[OF \<open>real_of_float x \<noteq> 0\<close>, symmetric] ln_inverse[OF \<open>0 < real_of_float x\<close>] by auto |
2578 from this ub_ln_lb_ln_bounds'[OF A', THEN conjunct1, THEN le_imp_neg_le] |
2572 from this ub_ln_lb_ln_bounds'[OF A', THEN conjunct1, THEN le_imp_neg_le] |
2579 have "?ln \<le> - the (lb_ln prec ?divl)" unfolding uminus_float.rep_eq by (rule order_trans) |
2573 have "?ln \<le> - the (lb_ln prec ?divl)" unfolding uminus_float.rep_eq by (rule order_trans) |
2580 } moreover |
2574 } moreover |
2581 { |
2575 { |
2582 let ?divr = "float_divr prec 1 x" |
2576 let ?divr = "float_divr prec 1 x" |
2583 have A': "1 \<le> ?divr" using float_divr_pos_less1_lower_bound[OF \<open>0 < x\<close> \<open>x \<le> 1\<close>] unfolding less_eq_float_def less_float_def by auto |
2577 have A': "1 \<le> ?divr" using float_divr_pos_less1_lower_bound[OF \<open>0 < x\<close> \<open>x \<le> 1\<close>] unfolding less_eq_float_def less_float_def by auto |
2584 hence B: "0 < real ?divr" by auto |
2578 hence B: "0 < real_of_float ?divr" by auto |
2585 |
2579 |
2586 have "ln (1 / x) \<le> ln ?divr" unfolding ln_le_cancel_iff[OF A B] using float_divr[of 1 x] by auto |
2580 have "ln (1 / x) \<le> ln ?divr" unfolding ln_le_cancel_iff[OF A B] using float_divr[of 1 x] by auto |
2587 hence "- ln ?divr \<le> ln x" unfolding nonzero_inverse_eq_divide[OF \<open>real x \<noteq> 0\<close>, symmetric] ln_inverse[OF \<open>0 < real x\<close>] by auto |
2581 hence "- ln ?divr \<le> ln x" unfolding nonzero_inverse_eq_divide[OF \<open>real_of_float x \<noteq> 0\<close>, symmetric] ln_inverse[OF \<open>0 < real_of_float x\<close>] by auto |
2588 from ub_ln_lb_ln_bounds'[OF A', THEN conjunct2, THEN le_imp_neg_le] this |
2582 from ub_ln_lb_ln_bounds'[OF A', THEN conjunct2, THEN le_imp_neg_le] this |
2589 have "- the (ub_ln prec ?divr) \<le> ?ln" unfolding uminus_float.rep_eq by (rule order_trans) |
2583 have "- the (ub_ln prec ?divr) \<le> ?ln" unfolding uminus_float.rep_eq by (rule order_trans) |
2590 } |
2584 } |
2591 ultimately show ?thesis unfolding lb_ln.simps[where x=x] ub_ln.simps[where x=x] |
2585 ultimately show ?thesis unfolding lb_ln.simps[where x=x] ub_ln.simps[where x=x] |
2592 unfolding if_not_P[OF \<open>\<not> x \<le> 0\<close>] if_P[OF True] by auto |
2586 unfolding if_not_P[OF \<open>\<not> x \<le> 0\<close>] if_P[OF True] by auto |
2593 qed |
2587 qed |
2594 |
2588 |
2595 lemma lb_ln: |
2589 lemma lb_ln: |
2596 assumes "Some y = lb_ln prec x" |
2590 assumes "Some y = lb_ln prec x" |
2597 shows "y \<le> ln x" and "0 < real x" |
2591 shows "y \<le> ln x" and "0 < real_of_float x" |
2598 proof - |
2592 proof - |
2599 have "0 < x" |
2593 have "0 < x" |
2600 proof (rule ccontr) |
2594 proof (rule ccontr) |
2601 assume "\<not> 0 < x" |
2595 assume "\<not> 0 < x" |
2602 hence "x \<le> 0" |
2596 hence "x \<le> 0" |
2603 unfolding less_eq_float_def less_float_def by auto |
2597 unfolding less_eq_float_def less_float_def by auto |
2604 thus False |
2598 thus False |
2605 using assms by auto |
2599 using assms by auto |
2606 qed |
2600 qed |
2607 thus "0 < real x" by auto |
2601 thus "0 < real_of_float x" by auto |
2608 have "the (lb_ln prec x) \<le> ln x" |
2602 have "the (lb_ln prec x) \<le> ln x" |
2609 using ub_ln_lb_ln_bounds[OF \<open>0 < x\<close>] .. |
2603 using ub_ln_lb_ln_bounds[OF \<open>0 < x\<close>] .. |
2610 thus "y \<le> ln x" |
2604 thus "y \<le> ln x" |
2611 unfolding assms[symmetric] by auto |
2605 unfolding assms[symmetric] by auto |
2612 qed |
2606 qed |
2613 |
2607 |
2614 lemma ub_ln: |
2608 lemma ub_ln: |
2615 assumes "Some y = ub_ln prec x" |
2609 assumes "Some y = ub_ln prec x" |
2616 shows "ln x \<le> y" and "0 < real x" |
2610 shows "ln x \<le> y" and "0 < real_of_float x" |
2617 proof - |
2611 proof - |
2618 have "0 < x" |
2612 have "0 < x" |
2619 proof (rule ccontr) |
2613 proof (rule ccontr) |
2620 assume "\<not> 0 < x" |
2614 assume "\<not> 0 < x" |
2621 hence "x \<le> 0" by auto |
2615 hence "x \<le> 0" by auto |
2622 thus False |
2616 thus False |
2623 using assms by auto |
2617 using assms by auto |
2624 qed |
2618 qed |
2625 thus "0 < real x" by auto |
2619 thus "0 < real_of_float x" by auto |
2626 have "ln x \<le> the (ub_ln prec x)" |
2620 have "ln x \<le> the (ub_ln prec x)" |
2627 using ub_ln_lb_ln_bounds[OF \<open>0 < x\<close>] .. |
2621 using ub_ln_lb_ln_bounds[OF \<open>0 < x\<close>] .. |
2628 thus "ln x \<le> y" |
2622 thus "ln x \<le> y" |
2629 unfolding assms[symmetric] by auto |
2623 unfolding assms[symmetric] by auto |
2630 qed |
2624 qed |
2744 |
2738 |
2745 fun lift_un' :: "(float * float) option \<Rightarrow> (float \<Rightarrow> float \<Rightarrow> (float * float)) \<Rightarrow> (float * float) option" where |
2739 fun lift_un' :: "(float * float) option \<Rightarrow> (float \<Rightarrow> float \<Rightarrow> (float * float)) \<Rightarrow> (float * float) option" where |
2746 "lift_un' (Some (l1, u1)) f = Some (f l1 u1)" | |
2740 "lift_un' (Some (l1, u1)) f = Some (f l1 u1)" | |
2747 "lift_un' b f = None" |
2741 "lift_un' b f = None" |
2748 |
2742 |
2749 definition "bounded_by xs vs \<longleftrightarrow> |
2743 definition bounded_by :: "real list \<Rightarrow> (float \<times> float) option list \<Rightarrow> bool" where |
|
2744 "bounded_by xs vs \<longleftrightarrow> |
2750 (\<forall> i < length vs. case vs ! i of None \<Rightarrow> True |
2745 (\<forall> i < length vs. case vs ! i of None \<Rightarrow> True |
2751 | Some (l, u) \<Rightarrow> xs ! i \<in> { real l .. real u })" |
2746 | Some (l, u) \<Rightarrow> xs ! i \<in> { real_of_float l .. real_of_float u })" |
2752 |
2747 |
2753 lemma bounded_byE: |
2748 lemma bounded_byE: |
2754 assumes "bounded_by xs vs" |
2749 assumes "bounded_by xs vs" |
2755 shows "\<And> i. i < length vs \<Longrightarrow> case vs ! i of None \<Rightarrow> True |
2750 shows "\<And> i. i < length vs \<Longrightarrow> case vs ! i of None \<Rightarrow> True |
2756 | Some (l, u) \<Rightarrow> xs ! i \<in> { real l .. real u }" |
2751 | Some (l, u) \<Rightarrow> xs ! i \<in> { real_of_float l .. real_of_float u }" |
2757 using assms bounded_by_def by blast |
2752 using assms bounded_by_def by blast |
2758 |
2753 |
2759 lemma bounded_by_update: |
2754 lemma bounded_by_update: |
2760 assumes "bounded_by xs vs" |
2755 assumes "bounded_by xs vs" |
2761 and bnd: "xs ! i \<in> { real l .. real u }" |
2756 and bnd: "xs ! i \<in> { real_of_float l .. real_of_float u }" |
2762 shows "bounded_by xs (vs[i := Some (l,u)])" |
2757 shows "bounded_by xs (vs[i := Some (l,u)])" |
2763 proof - |
2758 proof - |
2764 { |
2759 { |
2765 fix j |
2760 fix j |
2766 let ?vs = "vs[i := Some (l,u)]" |
2761 let ?vs = "vs[i := Some (l,u)]" |
2767 assume "j < length ?vs" |
2762 assume "j < length ?vs" |
2768 hence [simp]: "j < length vs" by simp |
2763 hence [simp]: "j < length vs" by simp |
2769 have "case ?vs ! j of None \<Rightarrow> True | Some (l, u) \<Rightarrow> xs ! j \<in> { real l .. real u }" |
2764 have "case ?vs ! j of None \<Rightarrow> True | Some (l, u) \<Rightarrow> xs ! j \<in> { real_of_float l .. real_of_float u }" |
2770 proof (cases "?vs ! j") |
2765 proof (cases "?vs ! j") |
2771 case (Some b) |
2766 case (Some b) |
2772 thus ?thesis |
2767 thus ?thesis |
2773 proof (cases "i = j") |
2768 proof (cases "i = j") |
2774 case True |
2769 case True |
3107 proof (rule ccontr) |
3102 proof (rule ccontr) |
3108 assume P: "\<not> (0 < l1 \<or> u1 < 0)" |
3103 assume P: "\<not> (0 < l1 \<or> u1 < 0)" |
3109 show False |
3104 show False |
3110 using l' unfolding if_not_P[OF P] by auto |
3105 using l' unfolding if_not_P[OF P] by auto |
3111 qed |
3106 qed |
3112 moreover have l1_le_u1: "real l1 \<le> real u1" |
3107 moreover have l1_le_u1: "real_of_float l1 \<le> real_of_float u1" |
3113 using l1 u1 by auto |
3108 using l1 u1 by auto |
3114 ultimately have "real l1 \<noteq> 0" and "real u1 \<noteq> 0" |
3109 ultimately have "real_of_float l1 \<noteq> 0" and "real_of_float u1 \<noteq> 0" |
3115 by auto |
3110 by auto |
3116 |
3111 |
3117 have inv: "inverse u1 \<le> inverse (interpret_floatarith a xs) |
3112 have inv: "inverse u1 \<le> inverse (interpret_floatarith a xs) |
3118 \<and> inverse (interpret_floatarith a xs) \<le> inverse l1" |
3113 \<and> inverse (interpret_floatarith a xs) \<le> inverse l1" |
3119 proof (cases "0 < l1") |
3114 proof (cases "0 < l1") |
3120 case True |
3115 case True |
3121 hence "0 < real u1" and "0 < real l1" "0 < interpret_floatarith a xs" |
3116 hence "0 < real_of_float u1" and "0 < real_of_float l1" "0 < interpret_floatarith a xs" |
3122 using l1_le_u1 l1 by auto |
3117 using l1_le_u1 l1 by auto |
3123 show ?thesis |
3118 show ?thesis |
3124 unfolding inverse_le_iff_le[OF \<open>0 < real u1\<close> \<open>0 < interpret_floatarith a xs\<close>] |
3119 unfolding inverse_le_iff_le[OF \<open>0 < real_of_float u1\<close> \<open>0 < interpret_floatarith a xs\<close>] |
3125 inverse_le_iff_le[OF \<open>0 < interpret_floatarith a xs\<close> \<open>0 < real l1\<close>] |
3120 inverse_le_iff_le[OF \<open>0 < interpret_floatarith a xs\<close> \<open>0 < real_of_float l1\<close>] |
3126 using l1 u1 by auto |
3121 using l1 u1 by auto |
3127 next |
3122 next |
3128 case False |
3123 case False |
3129 hence "u1 < 0" |
3124 hence "u1 < 0" |
3130 using either by blast |
3125 using either by blast |
3131 hence "real u1 < 0" and "real l1 < 0" "interpret_floatarith a xs < 0" |
3126 hence "real_of_float u1 < 0" and "real_of_float l1 < 0" "interpret_floatarith a xs < 0" |
3132 using l1_le_u1 u1 by auto |
3127 using l1_le_u1 u1 by auto |
3133 show ?thesis |
3128 show ?thesis |
3134 unfolding inverse_le_iff_le_neg[OF \<open>real u1 < 0\<close> \<open>interpret_floatarith a xs < 0\<close>] |
3129 unfolding inverse_le_iff_le_neg[OF \<open>real_of_float u1 < 0\<close> \<open>interpret_floatarith a xs < 0\<close>] |
3135 inverse_le_iff_le_neg[OF \<open>interpret_floatarith a xs < 0\<close> \<open>real l1 < 0\<close>] |
3130 inverse_le_iff_le_neg[OF \<open>interpret_floatarith a xs < 0\<close> \<open>real_of_float l1 < 0\<close>] |
3136 using l1 u1 by auto |
3131 using l1 u1 by auto |
3137 qed |
3132 qed |
3138 |
3133 |
3139 from l' have "l = float_divl prec 1 u1" |
3134 from l' have "l = float_divl prec 1 u1" |
3140 by (cases "0 < l1 \<or> u1 < 0") auto |
3135 by (cases "0 < l1 \<or> u1 < 0") auto |
3141 hence "l \<le> inverse u1" |
3136 hence "l \<le> inverse u1" |
3142 unfolding nonzero_inverse_eq_divide[OF \<open>real u1 \<noteq> 0\<close>] |
3137 unfolding nonzero_inverse_eq_divide[OF \<open>real_of_float u1 \<noteq> 0\<close>] |
3143 using float_divl[of prec 1 u1] by auto |
3138 using float_divl[of prec 1 u1] by auto |
3144 also have "\<dots> \<le> inverse (interpret_floatarith a xs)" |
3139 also have "\<dots> \<le> inverse (interpret_floatarith a xs)" |
3145 using inv by auto |
3140 using inv by auto |
3146 finally have "l \<le> inverse (interpret_floatarith a xs)" . |
3141 finally have "l \<le> inverse (interpret_floatarith a xs)" . |
3147 moreover |
3142 moreover |
3148 from u' have "u = float_divr prec 1 l1" |
3143 from u' have "u = float_divr prec 1 l1" |
3149 by (cases "0 < l1 \<or> u1 < 0") auto |
3144 by (cases "0 < l1 \<or> u1 < 0") auto |
3150 hence "inverse l1 \<le> u" |
3145 hence "inverse l1 \<le> u" |
3151 unfolding nonzero_inverse_eq_divide[OF \<open>real l1 \<noteq> 0\<close>] |
3146 unfolding nonzero_inverse_eq_divide[OF \<open>real_of_float l1 \<noteq> 0\<close>] |
3152 using float_divr[of 1 l1 prec] by auto |
3147 using float_divr[of 1 l1 prec] by auto |
3153 hence "inverse (interpret_floatarith a xs) \<le> u" |
3148 hence "inverse (interpret_floatarith a xs) \<le> u" |
3154 by (rule order_trans[OF inv[THEN conjunct2]]) |
3149 by (rule order_trans[OF inv[THEN conjunct2]]) |
3155 ultimately show ?case |
3150 ultimately show ?case |
3156 unfolding interpret_floatarith.simps using l1 u1 by auto |
3151 unfolding interpret_floatarith.simps using l1 u1 by auto |
3353 next |
3348 next |
3354 case (Less a b) |
3349 case (Less a b) |
3355 then obtain l u l' u' |
3350 then obtain l u l' u' |
3356 where l_eq: "Some (l, u) = approx prec a vs" |
3351 where l_eq: "Some (l, u) = approx prec a vs" |
3357 and u_eq: "Some (l', u') = approx prec b vs" |
3352 and u_eq: "Some (l', u') = approx prec b vs" |
3358 and inequality: "real (float_plus_up prec u (-l')) < 0" |
3353 and inequality: "real_of_float (float_plus_up prec u (-l')) < 0" |
3359 by (cases "approx prec a vs", auto, cases "approx prec b vs", auto) |
3354 by (cases "approx prec a vs", auto, cases "approx prec b vs", auto) |
3360 from le_less_trans[OF float_plus_up inequality] |
3355 from le_less_trans[OF float_plus_up inequality] |
3361 approx[OF Less.prems(2) l_eq] approx[OF Less.prems(2) u_eq] |
3356 approx[OF Less.prems(2) l_eq] approx[OF Less.prems(2) u_eq] |
3362 show ?case by auto |
3357 show ?case by auto |
3363 next |
3358 next |
3364 case (LessEqual a b) |
3359 case (LessEqual a b) |
3365 then obtain l u l' u' |
3360 then obtain l u l' u' |
3366 where l_eq: "Some (l, u) = approx prec a vs" |
3361 where l_eq: "Some (l, u) = approx prec a vs" |
3367 and u_eq: "Some (l', u') = approx prec b vs" |
3362 and u_eq: "Some (l', u') = approx prec b vs" |
3368 and inequality: "real (float_plus_up prec u (-l')) \<le> 0" |
3363 and inequality: "real_of_float (float_plus_up prec u (-l')) \<le> 0" |
3369 by (cases "approx prec a vs", auto, cases "approx prec b vs", auto) |
3364 by (cases "approx prec a vs", auto, cases "approx prec b vs", auto) |
3370 from order_trans[OF float_plus_up inequality] |
3365 from order_trans[OF float_plus_up inequality] |
3371 approx[OF LessEqual.prems(2) l_eq] approx[OF LessEqual.prems(2) u_eq] |
3366 approx[OF LessEqual.prems(2) l_eq] approx[OF LessEqual.prems(2) u_eq] |
3372 show ?case by auto |
3367 show ?case by auto |
3373 next |
3368 next |
3374 case (AtLeastAtMost x a b) |
3369 case (AtLeastAtMost x a b) |
3375 then obtain lx ux l u l' u' |
3370 then obtain lx ux l u l' u' |
3376 where x_eq: "Some (lx, ux) = approx prec x vs" |
3371 where x_eq: "Some (lx, ux) = approx prec x vs" |
3377 and l_eq: "Some (l, u) = approx prec a vs" |
3372 and l_eq: "Some (l, u) = approx prec a vs" |
3378 and u_eq: "Some (l', u') = approx prec b vs" |
3373 and u_eq: "Some (l', u') = approx prec b vs" |
3379 and inequality: "real (float_plus_up prec u (-lx)) \<le> 0" "real (float_plus_up prec ux (-l')) \<le> 0" |
3374 and inequality: "real_of_float (float_plus_up prec u (-lx)) \<le> 0" "real_of_float (float_plus_up prec ux (-l')) \<le> 0" |
3380 by (cases "approx prec x vs", auto, |
3375 by (cases "approx prec x vs", auto, |
3381 cases "approx prec a vs", auto, |
3376 cases "approx prec a vs", auto, |
3382 cases "approx prec b vs", auto) |
3377 cases "approx prec b vs", auto) |
3383 from order_trans[OF float_plus_up inequality(1)] order_trans[OF float_plus_up inequality(2)] |
3378 from order_trans[OF float_plus_up inequality(1)] order_trans[OF float_plus_up inequality(2)] |
3384 approx[OF AtLeastAtMost.prems(2) l_eq] approx[OF AtLeastAtMost.prems(2) u_eq] approx[OF AtLeastAtMost.prems(2) x_eq] |
3379 approx[OF AtLeastAtMost.prems(2) l_eq] approx[OF AtLeastAtMost.prems(2) u_eq] approx[OF AtLeastAtMost.prems(2) x_eq] |
3520 qed auto |
3515 qed auto |
3521 |
3516 |
3522 lemma bounded_by_update_var: |
3517 lemma bounded_by_update_var: |
3523 assumes "bounded_by xs vs" |
3518 assumes "bounded_by xs vs" |
3524 and "vs ! i = Some (l, u)" |
3519 and "vs ! i = Some (l, u)" |
3525 and bnd: "x \<in> { real l .. real u }" |
3520 and bnd: "x \<in> { real_of_float l .. real_of_float u }" |
3526 shows "bounded_by (xs[i := x]) vs" |
3521 shows "bounded_by (xs[i := x]) vs" |
3527 proof (cases "i < length xs") |
3522 proof (cases "i < length xs") |
3528 case False |
3523 case False |
3529 thus ?thesis |
3524 thus ?thesis |
3530 using \<open>bounded_by xs vs\<close> by auto |
3525 using \<open>bounded_by xs vs\<close> by auto |
3531 next |
3526 next |
3532 case True |
3527 case True |
3533 let ?xs = "xs[i := x]" |
3528 let ?xs = "xs[i := x]" |
3534 from True have "i < length ?xs" by auto |
3529 from True have "i < length ?xs" by auto |
3535 have "case vs ! j of None \<Rightarrow> True | Some (l, u) \<Rightarrow> ?xs ! j \<in> {real l .. real u}" |
3530 have "case vs ! j of None \<Rightarrow> True | Some (l, u) \<Rightarrow> ?xs ! j \<in> {real_of_float l .. real_of_float u}" |
3536 if "j < length vs" for j |
3531 if "j < length vs" for j |
3537 proof (cases "vs ! j") |
3532 proof (cases "vs ! j") |
3538 case None |
3533 case None |
3539 then show ?thesis by simp |
3534 then show ?thesis by simp |
3540 next |
3535 next |
3687 have bnd: "bounded_by (xs[x:=c]) (vs[x:= Some (c,c)])" |
3682 have bnd: "bounded_by (xs[x:=c]) (vs[x:= Some (c,c)])" |
3688 by (auto intro!: bounded_by_update) |
3683 by (auto intro!: bounded_by_update) |
3689 |
3684 |
3690 from approx[OF this a] |
3685 from approx[OF this a] |
3691 have f_c: "interpret_floatarith ((DERIV_floatarith x ^^ 0) f) (xs[x := c]) \<in> { l1 .. u1 }" |
3686 have f_c: "interpret_floatarith ((DERIV_floatarith x ^^ 0) f) (xs[x := c]) \<in> { l1 .. u1 }" |
3692 (is "?f 0 (real c) \<in> _") |
3687 (is "?f 0 (real_of_float c) \<in> _") |
3693 by auto |
3688 by auto |
3694 |
3689 |
3695 have funpow_Suc[symmetric]: "(f ^^ Suc n) x = (f ^^ n) (f x)" |
3690 have funpow_Suc[symmetric]: "(f ^^ Suc n) x = (f ^^ n) (f x)" |
3696 for f :: "'a \<Rightarrow> 'a" and n :: nat and x :: 'a |
3691 for f :: "'a \<Rightarrow> 'a" and n :: nat and x :: 'a |
3697 by (induct n) auto |
3692 by (induct n) auto |
3698 from Suc.hyps[OF ate, unfolded this] obtain n |
3693 from Suc.hyps[OF ate, unfolded this] obtain n |
3699 where DERIV_hyp: "\<And>m z. \<lbrakk> m < n ; (z::real) \<in> { lx .. ux } \<rbrakk> \<Longrightarrow> |
3694 where DERIV_hyp: "\<And>m z. \<lbrakk> m < n ; (z::real) \<in> { lx .. ux } \<rbrakk> \<Longrightarrow> |
3700 DERIV (?f (Suc m)) z :> ?f (Suc (Suc m)) z" |
3695 DERIV (?f (Suc m)) z :> ?f (Suc (Suc m)) z" |
3701 and hyp: "\<forall>t \<in> {real lx .. real ux}. |
3696 and hyp: "\<forall>t \<in> {real_of_float lx .. real_of_float ux}. |
3702 (\<Sum> i = 0..<n. inverse (real (\<Prod> j \<in> {Suc k..<Suc k + i}. j)) * ?f (Suc i) c * (xs!x - c)^i) + |
3697 (\<Sum> i = 0..<n. inverse (real (\<Prod> j \<in> {Suc k..<Suc k + i}. j)) * ?f (Suc i) c * (xs!x - c)^i) + |
3703 inverse (real (\<Prod> j \<in> {Suc k..<Suc k + n}. j)) * ?f (Suc n) t * (xs!x - c)^n \<in> {l2 .. u2}" |
3698 inverse (real (\<Prod> j \<in> {Suc k..<Suc k + n}. j)) * ?f (Suc n) t * (xs!x - c)^n \<in> {l2 .. u2}" |
3704 (is "\<forall> t \<in> _. ?X (Suc k) f n t \<in> _") |
3699 (is "\<forall> t \<in> _. ?X (Suc k) f n t \<in> _") |
3705 by blast |
3700 by blast |
3706 |
3701 |
3735 |
3730 |
3736 with hyp[THEN bspec, OF t] f_c |
3731 with hyp[THEN bspec, OF t] f_c |
3737 have "bounded_by [?f 0 c, ?X (Suc k) f n t, xs!x] [Some (l1, u1), Some (l2, u2), vs!x]" |
3732 have "bounded_by [?f 0 c, ?X (Suc k) f n t, xs!x] [Some (l1, u1), Some (l2, u2), vs!x]" |
3738 by (auto intro!: bounded_by_Cons) |
3733 by (auto intro!: bounded_by_Cons) |
3739 from approx[OF this final, unfolded atLeastAtMost_iff[symmetric]] |
3734 from approx[OF this final, unfolded atLeastAtMost_iff[symmetric]] |
3740 have "?X (Suc k) f n t * (xs!x - real c) * inverse k + ?f 0 c \<in> {l .. u}" |
3735 have "?X (Suc k) f n t * (xs!x - real_of_float c) * inverse k + ?f 0 c \<in> {l .. u}" |
3741 by (auto simp add: algebra_simps) |
3736 by (auto simp add: algebra_simps) |
3742 also have "?X (Suc k) f n t * (xs!x - real c) * inverse (real k) + ?f 0 c = |
3737 also have "?X (Suc k) f n t * (xs!x - real_of_float c) * inverse (real k) + ?f 0 c = |
3743 (\<Sum> i = 0..<Suc n. inverse (real (\<Prod> j \<in> {k..<k+i}. j)) * ?f i c * (xs!x - c)^i) + |
3738 (\<Sum> i = 0..<Suc n. inverse (real (\<Prod> j \<in> {k..<k+i}. j)) * ?f i c * (xs!x - c)^i) + |
3744 inverse (real (\<Prod> j \<in> {k..<k+Suc n}. j)) * ?f (Suc n) t * (xs!x - c)^Suc n" (is "_ = ?T") |
3739 inverse (real (\<Prod> j \<in> {k..<k+Suc n}. j)) * ?f (Suc n) t * (xs!x - c)^Suc n" (is "_ = ?T") |
3745 unfolding funpow_Suc C_def[symmetric] setsum_move0 setprod_head_Suc |
3740 unfolding funpow_Suc C_def[symmetric] setsum_move0 setprod_head_Suc |
3746 by (auto simp add: algebra_simps) |
3741 by (auto simp add: algebra_simps) |
3747 (simp only: mult.left_commute [of _ "inverse (real k)"] setsum_right_distrib [symmetric]) |
3742 (simp only: mult.left_commute [of _ "inverse (real k)"] setsum_right_distrib [symmetric]) |
3848 from Suc.prems |
3842 from Suc.prems |
3849 have l: "approx_tse_form' prec t f s l ?m cmp" |
3843 have l: "approx_tse_form' prec t f s l ?m cmp" |
3850 and u: "approx_tse_form' prec t f s ?m u cmp" |
3844 and u: "approx_tse_form' prec t f s ?m u cmp" |
3851 by (auto simp add: Let_def lazy_conj) |
3845 by (auto simp add: Let_def lazy_conj) |
3852 |
3846 |
3853 have m_l: "real l \<le> ?m" and m_u: "?m \<le> real u" |
3847 have m_l: "real_of_float l \<le> ?m" and m_u: "?m \<le> real_of_float u" |
3854 unfolding less_eq_float_def using Suc.prems by auto |
3848 unfolding less_eq_float_def using Suc.prems by auto |
3855 with \<open>x \<in> { l .. u }\<close> consider "x \<in> { l .. ?m}" | "x \<in> {?m .. u}" |
3849 with \<open>x \<in> { l .. u }\<close> consider "x \<in> { l .. ?m}" | "x \<in> {?m .. u}" |
3856 by atomize_elim auto |
3850 by atomize_elim auto |
3857 thus ?case |
3851 thus ?case |
3858 proof cases |
3852 proof cases |
3859 case 1 |
3853 case 1 |
3860 from Suc.hyps[OF l this] |
3854 from Suc.hyps[OF l this] |
3861 obtain l' u' ly uy where |
3855 obtain l' u' ly uy where |
3862 "x \<in> {l' .. u'} \<and> real l \<le> l' \<and> real u' \<le> ?m \<and> cmp ly uy \<and> |
3856 "x \<in> {l' .. u'} \<and> real_of_float l \<le> l' \<and> real_of_float u' \<le> ?m \<and> cmp ly uy \<and> |
3863 approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 f [Some (l', u')] = Some (ly, uy)" |
3857 approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 f [Some (l', u')] = Some (ly, uy)" |
3864 by blast |
3858 by blast |
3865 with m_u show ?thesis |
3859 with m_u show ?thesis |
3866 by (auto intro!: exI) |
3860 by (auto intro!: exI) |
3867 next |
3861 next |
3868 case 2 |
3862 case 2 |
3869 from Suc.hyps[OF u this] |
3863 from Suc.hyps[OF u this] |
3870 obtain l' u' ly uy where |
3864 obtain l' u' ly uy where |
3871 "x \<in> { l' .. u' } \<and> ?m \<le> real l' \<and> u' \<le> real u \<and> cmp ly uy \<and> |
3865 "x \<in> { l' .. u' } \<and> ?m \<le> real_of_float l' \<and> u' \<le> real_of_float u \<and> cmp ly uy \<and> |
3872 approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 f [Some (l', u')] = Some (ly, uy)" |
3866 approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 f [Some (l', u')] = Some (ly, uy)" |
3873 by blast |
3867 by blast |
3874 with m_u show ?thesis |
3868 with m_u show ?thesis |
3875 by (auto intro!: exI) |
3869 by (auto intro!: exI) |
3876 qed |
3870 qed |