src/HOL/Decision_Procs/Approximation.thy
changeset 61609 77b453bd616f
parent 60680 589ed01b94fe
child 61610 4f54d2759a0b
equal deleted inserted replaced
61553:933eb9e6a1cc 61609:77b453bd616f
    49     using horner_schema'[of "\<lambda> j. 1 / (f (j' + j))"] by auto
    49     using horner_schema'[of "\<lambda> j. 1 / (f (j' + j))"] by auto
    50 qed
    50 qed
    51 
    51 
    52 lemma horner_bounds':
    52 lemma horner_bounds':
    53   fixes lb :: "nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> float \<Rightarrow> float" and ub :: "nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> float \<Rightarrow> float"
    53   fixes lb :: "nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> float \<Rightarrow> float" and ub :: "nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> float \<Rightarrow> float"
    54   assumes "0 \<le> real x" and f_Suc: "\<And>n. f (Suc n) = G ((F ^^ n) s) (f n)"
    54   assumes "0 \<le> real_of_float x" and f_Suc: "\<And>n. f (Suc n) = G ((F ^^ n) s) (f n)"
    55     and lb_0: "\<And> i k x. lb 0 i k x = 0"
    55     and lb_0: "\<And> i k x. lb 0 i k x = 0"
    56     and lb_Suc: "\<And> n i k x. lb (Suc n) i k x = float_plus_down prec
    56     and lb_Suc: "\<And> n i k x. lb (Suc n) i k x = float_plus_down prec
    57         (lapprox_rat prec 1 k)
    57         (lapprox_rat prec 1 k)
    58         (- float_round_up prec (x * (ub n (F i) (G i k) x)))"
    58         (- float_round_up prec (x * (ub n (F i) (G i k) x)))"
    59     and ub_0: "\<And> i k x. ub 0 i k x = 0"
    59     and ub_0: "\<And> i k x. ub 0 i k x = 0"
    67   case 0
    67   case 0
    68   thus ?case unfolding lb_0 ub_0 horner.simps by auto
    68   thus ?case unfolding lb_0 ub_0 horner.simps by auto
    69 next
    69 next
    70   case (Suc n)
    70   case (Suc n)
    71   thus ?case using lapprox_rat[of prec 1 "f j'"] using rapprox_rat[of 1 "f j'" prec]
    71   thus ?case using lapprox_rat[of prec 1 "f j'"] using rapprox_rat[of 1 "f j'" prec]
    72     Suc[where j'="Suc j'"] \<open>0 \<le> real x\<close>
    72     Suc[where j'="Suc j'"] \<open>0 \<le> real_of_float x\<close>
    73     by (auto intro!: add_mono mult_left_mono float_round_down_le float_round_up_le
    73     by (auto intro!: add_mono mult_left_mono float_round_down_le float_round_up_le
    74       order_trans[OF add_mono[OF _ float_plus_down_le]]
    74       order_trans[OF add_mono[OF _ float_plus_down_le]]
    75       order_trans[OF _ add_mono[OF _ float_plus_up_le]]
    75       order_trans[OF _ add_mono[OF _ float_plus_up_le]]
    76       simp add: lb_Suc ub_Suc field_simps f_Suc)
    76       simp add: lb_Suc ub_Suc field_simps f_Suc)
    77 qed
    77 qed
    85 
    85 
    86 \<close>
    86 \<close>
    87 
    87 
    88 lemma horner_bounds:
    88 lemma horner_bounds:
    89   fixes F :: "nat \<Rightarrow> nat" and G :: "nat \<Rightarrow> nat \<Rightarrow> nat"
    89   fixes F :: "nat \<Rightarrow> nat" and G :: "nat \<Rightarrow> nat \<Rightarrow> nat"
    90   assumes "0 \<le> real x" and f_Suc: "\<And>n. f (Suc n) = G ((F ^^ n) s) (f n)"
    90   assumes "0 \<le> real_of_float x" and f_Suc: "\<And>n. f (Suc n) = G ((F ^^ n) s) (f n)"
    91     and lb_0: "\<And> i k x. lb 0 i k x = 0"
    91     and lb_0: "\<And> i k x. lb 0 i k x = 0"
    92     and lb_Suc: "\<And> n i k x. lb (Suc n) i k x = float_plus_down prec
    92     and lb_Suc: "\<And> n i k x. lb (Suc n) i k x = float_plus_down prec
    93         (lapprox_rat prec 1 k)
    93         (lapprox_rat prec 1 k)
    94         (- float_round_up prec (x * (ub n (F i) (G i k) x)))"
    94         (- float_round_up prec (x * (ub n (F i) (G i k) x)))"
    95     and ub_0: "\<And> i k x. ub 0 i k x = 0"
    95     and ub_0: "\<And> i k x. ub 0 i k x = 0"
   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
   236     by (simp add: field_simps power2_eq_square)
   236     by (simp add: field_simps power2_eq_square)
   237   thus ?thesis by (simp add: field_simps)
   237   thus ?thesis by (simp add: field_simps)
   238 qed
   238 qed
   239 
   239 
   240 lemma sqrt_iteration_bound:
   240 lemma sqrt_iteration_bound:
   241   assumes "0 < real x"
   241   assumes "0 < real_of_float x"
   242   shows "sqrt x < sqrt_iteration prec n x"
   242   shows "sqrt x < sqrt_iteration prec n x"
   243 proof (induct n)
   243 proof (induct n)
   244   case 0
   244   case 0
   245   show ?case
   245   show ?case
   246   proof (cases x)
   246   proof (cases x)
   258       unfolding Float by (auto simp: powr_realpow[symmetric] field_simps powr_add)
   258       unfolding Float by (auto simp: powr_realpow[symmetric] field_simps powr_add)
   259     also have "\<dots> < 1 * 2 powr (e + nat (bitlen m))"
   259     also have "\<dots> < 1 * 2 powr (e + nat (bitlen m))"
   260     proof (rule mult_strict_right_mono, auto)
   260     proof (rule mult_strict_right_mono, auto)
   261       show "m < 2^nat (bitlen m)"
   261       show "m < 2^nat (bitlen m)"
   262         using bitlen_bounds[OF \<open>0 < m\<close>, THEN conjunct2]
   262         using bitlen_bounds[OF \<open>0 < m\<close>, THEN conjunct2]
   263         unfolding real_of_int_less_iff[of m, symmetric] by auto
   263         unfolding of_int_less_iff[of m, symmetric] by auto
   264     qed
   264     qed
   265     finally have "sqrt x < sqrt (2 powr (e + bitlen m))"
   265     finally have "sqrt x < sqrt (2 powr (e + bitlen m))"
   266       unfolding int_nat_bl by auto
   266       unfolding int_nat_bl by auto
   267     also have "\<dots> \<le> 2 powr ((e + bitlen m) div 2 + 1)"
   267     also have "\<dots> \<le> 2 powr ((e + bitlen m) div 2 + 1)"
   268     proof -
   268     proof -
   285       hence E_mod_pow: "sqrt (2 powr (?E mod 2)) < 2" by auto
   285       hence E_mod_pow: "sqrt (2 powr (?E mod 2)) < 2" by auto
   286 
   286 
   287       have E_eq: "2 powr ?E = 2 powr (?E div 2 + ?E div 2 + ?E mod 2)"
   287       have E_eq: "2 powr ?E = 2 powr (?E div 2 + ?E div 2 + ?E mod 2)"
   288         by auto
   288         by auto
   289       have "sqrt (2 powr ?E) = sqrt (2 powr (?E div 2) * 2 powr (?E div 2) * 2 powr (?E mod 2))"
   289       have "sqrt (2 powr ?E) = sqrt (2 powr (?E div 2) * 2 powr (?E div 2) * 2 powr (?E mod 2))"
   290         unfolding E_eq unfolding powr_add[symmetric] by (simp add: int_of_reals del: real_of_ints)
   290         unfolding E_eq unfolding powr_add[symmetric] by (metis of_int_add)
   291       also have "\<dots> = 2 powr (?E div 2) * sqrt (2 powr (?E mod 2))"
   291       also have "\<dots> = 2 powr (?E div 2) * sqrt (2 powr (?E mod 2))"
   292         unfolding real_sqrt_mult[of _ "2 powr (?E mod 2)"] real_sqrt_abs2 by auto
   292         unfolding real_sqrt_mult[of _ "2 powr (?E mod 2)"] real_sqrt_abs2 by auto
   293       also have "\<dots> < 2 powr (?E div 2) * 2 powr 1"
   293       also have "\<dots> < 2 powr (?E div 2) * 2 powr 1"
   294         by (rule mult_strict_left_mono) (auto intro: E_mod_pow)
   294         by (rule mult_strict_left_mono) (auto intro: E_mod_pow)
   295       also have "\<dots> = 2 powr (?E div 2 + 1)"
   295       also have "\<dots> = 2 powr (?E div 2 + 1)"
   302   qed
   302   qed
   303 next
   303 next
   304   case (Suc n)
   304   case (Suc n)
   305   let ?b = "sqrt_iteration prec n x"
   305   let ?b = "sqrt_iteration prec n x"
   306   have "0 < sqrt x"
   306   have "0 < sqrt x"
   307     using \<open>0 < real x\<close> by auto
   307     using \<open>0 < real_of_float x\<close> by auto
   308   also have "\<dots> < real ?b"
   308   also have "\<dots> < real_of_float ?b"
   309     using Suc .
   309     using Suc .
   310   finally have "sqrt x < (?b + x / ?b)/2"
   310   finally have "sqrt x < (?b + x / ?b)/2"
   311     using sqrt_ub_pos_pos_1[OF Suc _ \<open>0 < real x\<close>] by auto
   311     using sqrt_ub_pos_pos_1[OF Suc _ \<open>0 < real_of_float x\<close>] by auto
   312   also have "\<dots> \<le> (?b + (float_divr prec x ?b))/2"
   312   also have "\<dots> \<le> (?b + (float_divr prec x ?b))/2"
   313     by (rule divide_right_mono, auto simp add: float_divr)
   313     by (rule divide_right_mono, auto simp add: float_divr)
   314   also have "\<dots> = (Float 1 (- 1)) * (?b + (float_divr prec x ?b))"
   314   also have "\<dots> = (Float 1 (- 1)) * (?b + (float_divr prec x ?b))"
   315     by simp
   315     by simp
   316   also have "\<dots> \<le> (Float 1 (- 1)) * (float_plus_up prec ?b (float_divr prec x ?b))"
   316   also have "\<dots> \<le> (Float 1 (- 1)) * (float_plus_up prec ?b (float_divr prec x ?b))"
   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
   417 | "lb_arctan_horner prec 0 k x = 0"
   417 | "lb_arctan_horner prec 0 k x = 0"
   418 | "lb_arctan_horner prec (Suc n) k x = float_plus_down prec
   418 | "lb_arctan_horner prec (Suc n) k x = float_plus_down prec
   419       (lapprox_rat prec 1 k) (- float_round_up prec (x * (ub_arctan_horner prec n (k + 2) x)))"
   419       (lapprox_rat prec 1 k) (- float_round_up prec (x * (ub_arctan_horner prec n (k + 2) x)))"
   420 
   420 
   421 lemma arctan_0_1_bounds':
   421 lemma arctan_0_1_bounds':
   422   assumes "0 \<le> real y" "real y \<le> 1"
   422   assumes "0 \<le> real_of_float y" "real_of_float y \<le> 1"
   423     and "even n"
   423     and "even n"
   424   shows "arctan (sqrt y) \<in>
   424   shows "arctan (sqrt y) \<in>
   425       {(sqrt y * lb_arctan_horner prec n 1 y) .. (sqrt y * ub_arctan_horner prec (Suc n) 1 y)}"
   425       {(sqrt y * lb_arctan_horner prec n 1 y) .. (sqrt y * ub_arctan_horner prec (Suc n) 1 y)}"
   426 proof -
   426 proof -
   427   let ?c = "\<lambda>i. (- 1) ^ i * (1 / (i * 2 + (1::nat)) * sqrt y ^ (i * 2 + 1))"
   427   let ?c = "\<lambda>i. (- 1) ^ i * (1 / (i * 2 + (1::nat)) * sqrt y ^ (i * 2 + 1))"
   450   have F: "\<And>n. 2 * Suc n + 1 = 2 * n + 1 + 2" by auto
   450   have F: "\<And>n. 2 * Suc n + 1 = 2 * n + 1 + 2" by auto
   451 
   451 
   452   note bounds = horner_bounds[where s=1 and f="\<lambda>i. 2 * i + 1" and j'=0
   452   note bounds = horner_bounds[where s=1 and f="\<lambda>i. 2 * i + 1" and j'=0
   453     and lb="\<lambda>n i k x. lb_arctan_horner prec n k x"
   453     and lb="\<lambda>n i k x. lb_arctan_horner prec n k x"
   454     and ub="\<lambda>n i k x. ub_arctan_horner prec n k x",
   454     and ub="\<lambda>n i k x. ub_arctan_horner prec n k x",
   455     OF \<open>0 \<le> real y\<close> F lb_arctan_horner.simps ub_arctan_horner.simps]
   455     OF \<open>0 \<le> real_of_float y\<close> F lb_arctan_horner.simps ub_arctan_horner.simps]
   456 
   456 
   457   have "(sqrt y * lb_arctan_horner prec n 1 y) \<le> arctan (sqrt y)"
   457   have "(sqrt y * lb_arctan_horner prec n 1 y) \<le> arctan (sqrt y)"
   458   proof -
   458   proof -
   459     have "(sqrt y * lb_arctan_horner prec n 1 y) \<le> ?S n"
   459     have "(sqrt y * lb_arctan_horner prec n 1 y) \<le> ?S n"
   460       using bounds(1) \<open>0 \<le> sqrt y\<close>
   460       using bounds(1) \<open>0 \<le> sqrt y\<close>
   477   qed
   477   qed
   478   ultimately show ?thesis by auto
   478   ultimately show ?thesis by auto
   479 qed
   479 qed
   480 
   480 
   481 lemma arctan_0_1_bounds:
   481 lemma arctan_0_1_bounds:
   482   assumes "0 \<le> real y" "real y \<le> 1"
   482   assumes "0 \<le> real_of_float y" "real_of_float y \<le> 1"
   483   shows "arctan (sqrt y) \<in>
   483   shows "arctan (sqrt y) \<in>
   484     {(sqrt y * lb_arctan_horner prec (get_even n) 1 y) ..
   484     {(sqrt y * lb_arctan_horner prec (get_even n) 1 y) ..
   485       (sqrt y * ub_arctan_horner prec (get_odd n) 1 y)}"
   485       (sqrt y * ub_arctan_horner prec (get_odd n) 1 y)}"
   486   using
   486   using
   487     arctan_0_1_bounds'[OF assms, of n prec]
   487     arctan_0_1_bounds'[OF assms, of n prec]
   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"
   785           if_not_P[OF \<open>\<not> x \<le> Float 1 (- 1)\<close>] if_P[OF True]
   775           if_not_P[OF \<open>\<not> x \<le> Float 1 (- 1)\<close>] if_P[OF True]
   786         by (auto simp: float_round_down.rep_eq
   776         by (auto simp: float_round_down.rep_eq
   787           intro!: order_trans[OF mult_left_mono[OF truncate_down]])
   777           intro!: order_trans[OF mult_left_mono[OF truncate_down]])
   788     next
   778     next
   789       case False
   779       case False
   790       hence "2 < real x" by auto
   780       hence "2 < real_of_float x" by auto
   791       hence "1 \<le> real x" by auto
   781       hence "1 \<le> real_of_float x" by auto
   792 
   782 
   793       let "?invx" = "float_divr prec 1 x"
   783       let "?invx" = "float_divr prec 1 x"
   794       have "0 \<le> arctan x" using arctan_monotone'[OF \<open>0 \<le> real x\<close>]
   784       have "0 \<le> arctan x" using arctan_monotone'[OF \<open>0 \<le> real_of_float x\<close>]
   795         using arctan_tan[of 0, unfolded tan_zero] by auto
   785         using arctan_tan[of 0, unfolded tan_zero] by auto
   796 
   786 
   797       show ?thesis
   787       show ?thesis
   798       proof (cases "1 < ?invx")
   788       proof (cases "1 < ?invx")
   799         case True
   789         case True
   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
  1129     show ?thesis using lb[OF True get_even] .
  1119     show ?thesis using lb[OF True get_even] .
  1130   next
  1120   next
  1131     case False
  1121     case False
  1132     hence "get_even n = 0" by auto
  1122     hence "get_even n = 0" by auto
  1133     have "- (pi / 2) \<le> x"
  1123     have "- (pi / 2) \<le> x"
  1134       by (rule order_trans[OF _ \<open>0 < real x\<close>[THEN less_imp_le]]) auto
  1124       by (rule order_trans[OF _ \<open>0 < real_of_float x\<close>[THEN less_imp_le]]) auto
  1135     with \<open>x \<le> pi / 2\<close> show ?thesis
  1125     with \<open>x \<le> pi / 2\<close> show ?thesis
  1136       unfolding \<open>get_even n = 0\<close> lb_sin_cos_aux.simps minus_float.rep_eq zero_float.rep_eq
  1126       unfolding \<open>get_even n = 0\<close> lb_sin_cos_aux.simps minus_float.rep_eq zero_float.rep_eq
  1137       using cos_ge_zero by auto
  1127       using cos_ge_zero by auto
  1138   qed
  1128   qed
  1139   ultimately show ?thesis by auto
  1129   ultimately show ?thesis 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
  1242         from \<open>0 < ?fact\<close> and \<open>0 < ?pow\<close> and odd[OF \<open>odd n\<close>]
  1232         from \<open>0 < ?fact\<close> and \<open>0 < ?pow\<close> and odd[OF \<open>odd n\<close>]
  1243         have "0 \<le> (- ?rest) / ?fact * ?pow"
  1233         have "0 \<le> (- ?rest) / ?fact * ?pow"
  1244           by (metis mult_nonneg_nonneg divide_nonneg_pos less_imp_le)
  1234           by (metis mult_nonneg_nonneg divide_nonneg_pos less_imp_le)
  1245         thus ?thesis unfolding sin_eq by auto
  1235         thus ?thesis unfolding sin_eq by auto
  1246       qed
  1236       qed
  1247       also have "\<dots> \<le> (\<Sum> i = 0 ..< 2 * n. (if even(i) then 0 else ((- 1) ^ ((i - Suc 0) div 2))/((fact i))) * (real x) ^ i)"
  1237       also have "\<dots> \<le> (\<Sum> i = 0 ..< 2 * n. (if even(i) then 0 else ((- 1) ^ ((i - Suc 0) div 2))/((fact i))) * (real_of_float x) ^ i)"
  1248          by auto
  1238          by auto
  1249       also have "\<dots> \<le> (x * ub_sin_cos_aux prec n 2 1 (x * x))"
  1239       also have "\<dots> \<le> (x * ub_sin_cos_aux prec n 2 1 (x * x))"
  1250         using sin_aux[OF \<open>0 \<le> real x\<close>] unfolding setsum_morph[symmetric] by auto
  1240         using sin_aux[OF \<open>0 \<le> real_of_float x\<close>] unfolding setsum_morph[symmetric] by auto
  1251       finally have "sin x \<le> (x * ub_sin_cos_aux prec n 2 1 (x * x))" .
  1241       finally have "sin x \<le> (x * ub_sin_cos_aux prec n 2 1 (x * x))" .
  1252     } note ub = this and lb
  1242     } note ub = this and lb
  1253   } note ub = this(1) and lb = this(2)
  1243   } note ub = this(1) and lb = this(2)
  1254 
  1244 
  1255   have "sin x \<le> (x * ub_sin_cos_aux prec (get_odd n) 2 1 (x * x))"
  1245   have "sin x \<le> (x * ub_sin_cos_aux prec (get_odd n) 2 1 (x * x))"
  1260     show ?thesis
  1250     show ?thesis
  1261       using lb[OF True get_even] .
  1251       using lb[OF True get_even] .
  1262   next
  1252   next
  1263     case False
  1253     case False
  1264     hence "get_even n = 0" by auto
  1254     hence "get_even n = 0" by auto
  1265     with \<open>x \<le> pi / 2\<close> \<open>0 \<le> real x\<close>
  1255     with \<open>x \<le> pi / 2\<close> \<open>0 \<le> real_of_float x\<close>
  1266     show ?thesis
  1256     show ?thesis
  1267       unfolding \<open>get_even n = 0\<close> ub_sin_cos_aux.simps minus_float.rep_eq
  1257       unfolding \<open>get_even n = 0\<close> ub_sin_cos_aux.simps minus_float.rep_eq
  1268       using sin_ge_zero by auto
  1258       using sin_ge_zero by auto
  1269   qed
  1259   qed
  1270   ultimately show ?thesis by auto
  1260   ultimately show ?thesis by auto
  1273   show ?thesis
  1263   show ?thesis
  1274   proof (cases "n = 0")
  1264   proof (cases "n = 0")
  1275     case True
  1265     case True
  1276     thus ?thesis
  1266     thus ?thesis
  1277       unfolding \<open>n = 0\<close> get_even_def get_odd_def
  1267       unfolding \<open>n = 0\<close> get_even_def get_odd_def
  1278       using \<open>real x = 0\<close> lapprox_rat[where x="-1" and y=1] by auto
  1268       using \<open>real_of_float x = 0\<close> lapprox_rat[where x="-1" and y=1] by auto
  1279   next
  1269   next
  1280     case False
  1270     case False
  1281     with not0_implies_Suc obtain m where "n = Suc m" by blast
  1271     with not0_implies_Suc obtain m where "n = Suc m" by blast
  1282     thus ?thesis
  1272     thus ?thesis
  1283       unfolding \<open>n = Suc m\<close> get_even_def get_odd_def
  1273       unfolding \<open>n = Suc m\<close> get_even_def get_odd_def
  1284       using \<open>real x = 0\<close> rapprox_rat[where x=1 and y=1] lapprox_rat[where x=1 and y=1]
  1274       using \<open>real_of_float x = 0\<close> rapprox_rat[where x=1 and y=1] lapprox_rat[where x=1 and y=1]
  1285       by (cases "even (Suc m)") auto
  1275       by (cases "even (Suc m)") auto
  1286   qed
  1276   qed
  1287 qed
  1277 qed
  1288 
  1278 
  1289 
  1279 
  1304   in if x < Float 1 (- 1) then horner x
  1294   in if x < Float 1 (- 1) then horner x
  1305 else if x < 1          then half (horner (x * Float 1 (- 1)))
  1295 else if x < 1          then half (horner (x * Float 1 (- 1)))
  1306                        else half (half (horner (x * Float 1 (- 2)))))"
  1296                        else half (half (horner (x * Float 1 (- 2)))))"
  1307 
  1297 
  1308 lemma lb_cos:
  1298 lemma lb_cos:
  1309   assumes "0 \<le> real x" and "x \<le> pi"
  1299   assumes "0 \<le> real_of_float x" and "x \<le> pi"
  1310   shows "cos x \<in> {(lb_cos prec x) .. (ub_cos prec x)}" (is "?cos x \<in> {(?lb x) .. (?ub x) }")
  1300   shows "cos x \<in> {(lb_cos prec x) .. (ub_cos prec x)}" (is "?cos x \<in> {(?lb x) .. (?ub x) }")
  1311 proof -
  1301 proof -
  1312   have x_half[symmetric]: "cos x = 2 * cos (x / 2) * cos (x / 2) - 1" for x :: real
  1302   have x_half[symmetric]: "cos x = 2 * cos (x / 2) * cos (x / 2) - 1" for x :: real
  1313   proof -
  1303   proof -
  1314     have "cos x = cos (x / 2 + x / 2)"
  1304     have "cos x = cos (x / 2 + x / 2)"
  1318     also have "\<dots> = 2 * cos (x / 2) * cos (x / 2) - 1"
  1308     also have "\<dots> = 2 * cos (x / 2) * cos (x / 2) - 1"
  1319       by algebra
  1309       by algebra
  1320     finally show ?thesis .
  1310     finally show ?thesis .
  1321   qed
  1311   qed
  1322 
  1312 
  1323   have "\<not> x < 0" using \<open>0 \<le> real x\<close> by auto
  1313   have "\<not> x < 0" using \<open>0 \<le> real_of_float x\<close> by auto
  1324   let "?ub_horner x" = "ub_sin_cos_aux prec (get_odd (prec div 4 + 1)) 1 1 (x * x)"
  1314   let "?ub_horner x" = "ub_sin_cos_aux prec (get_odd (prec div 4 + 1)) 1 1 (x * x)"
  1325   let "?lb_horner x" = "lb_sin_cos_aux prec (get_even (prec div 4 + 1)) 1 1 (x * x)"
  1315   let "?lb_horner x" = "lb_sin_cos_aux prec (get_even (prec div 4 + 1)) 1 1 (x * x)"
  1326   let "?ub_half x" = "float_plus_up prec (Float 1 1 * x * x) (- 1)"
  1316   let "?ub_half x" = "float_plus_up prec (Float 1 1 * x * x) (- 1)"
  1327   let "?lb_half x" = "if x < 0 then - 1 else float_plus_down prec (Float 1 1 * x * x) (- 1)"
  1317   let "?lb_half x" = "if x < 0 then - 1 else float_plus_down prec (Float 1 1 * x * x) (- 1)"
  1328 
  1318 
  1332     hence "x \<le> pi / 2"
  1322     hence "x \<le> pi / 2"
  1333       using pi_ge_two by auto
  1323       using pi_ge_two by auto
  1334     show ?thesis
  1324     show ?thesis
  1335       unfolding lb_cos_def[where x=x] ub_cos_def[where x=x]
  1325       unfolding lb_cos_def[where x=x] ub_cos_def[where x=x]
  1336         if_not_P[OF \<open>\<not> x < 0\<close>] if_P[OF \<open>x < Float 1 (- 1)\<close>] Let_def
  1326         if_not_P[OF \<open>\<not> x < 0\<close>] if_P[OF \<open>x < Float 1 (- 1)\<close>] Let_def
  1337       using cos_boundaries[OF \<open>0 \<le> real x\<close> \<open>x \<le> pi / 2\<close>] .
  1327       using cos_boundaries[OF \<open>0 \<le> real_of_float x\<close> \<open>x \<le> pi / 2\<close>] .
  1338   next
  1328   next
  1339     case False
  1329     case False
  1340     { fix y x :: float let ?x2 = "(x * Float 1 (- 1))"
  1330     { fix y x :: float let ?x2 = "(x * Float 1 (- 1))"
  1341       assume "y \<le> cos ?x2" and "-pi \<le> x" and "x \<le> pi"
  1331       assume "y \<le> cos ?x2" and "-pi \<le> x" and "x \<le> pi"
  1342       hence "- (pi / 2) \<le> ?x2" and "?x2 \<le> pi / 2"
  1332       hence "- (pi / 2) \<le> ?x2" and "?x2 \<le> pi / 2"
  1349         case True
  1339         case True
  1350         show ?thesis
  1340         show ?thesis
  1351           using cos_ge_minus_one unfolding if_P[OF True] by auto
  1341           using cos_ge_minus_one unfolding if_P[OF True] by auto
  1352       next
  1342       next
  1353         case False
  1343         case False
  1354         hence "0 \<le> real y" by auto
  1344         hence "0 \<le> real_of_float y" by auto
  1355         from mult_mono[OF \<open>y \<le> cos ?x2\<close> \<open>y \<le> cos ?x2\<close> \<open>0 \<le> cos ?x2\<close> this]
  1345         from mult_mono[OF \<open>y \<le> cos ?x2\<close> \<open>y \<le> cos ?x2\<close> \<open>0 \<le> cos ?x2\<close> this]
  1356         have "real y * real y \<le> cos ?x2 * cos ?x2" .
  1346         have "real_of_float y * real_of_float y \<le> cos ?x2 * cos ?x2" .
  1357         hence "2 * real y * real y \<le> 2 * cos ?x2 * cos ?x2"
  1347         hence "2 * real_of_float y * real_of_float y \<le> 2 * cos ?x2 * cos ?x2"
  1358           by auto
  1348           by auto
  1359         hence "2 * real y * real y - 1 \<le> 2 * cos (x / 2) * cos (x / 2) - 1"
  1349         hence "2 * real_of_float y * real_of_float y - 1 \<le> 2 * cos (x / 2) * cos (x / 2) - 1"
  1360           unfolding Float_num by auto
  1350           unfolding Float_num by auto
  1361         thus ?thesis
  1351         thus ?thesis
  1362           unfolding if_not_P[OF False] x_half Float_num
  1352           unfolding if_not_P[OF False] x_half Float_num
  1363           by (auto intro!: float_plus_down_le)
  1353           by (auto intro!: float_plus_down_le)
  1364       qed
  1354       qed
  1370         using pi_ge_two unfolding Float_num by auto
  1360         using pi_ge_two unfolding Float_num by auto
  1371       hence "0 \<le> cos ?x2" by (rule cos_ge_zero)
  1361       hence "0 \<le> cos ?x2" by (rule cos_ge_zero)
  1372 
  1362 
  1373       have "cos x \<le> (?ub_half y)"
  1363       have "cos x \<le> (?ub_half y)"
  1374       proof -
  1364       proof -
  1375         have "0 \<le> real y"
  1365         have "0 \<le> real_of_float y"
  1376           using \<open>0 \<le> cos ?x2\<close> ub by (rule order_trans)
  1366           using \<open>0 \<le> cos ?x2\<close> ub by (rule order_trans)
  1377         from mult_mono[OF ub ub this \<open>0 \<le> cos ?x2\<close>]
  1367         from mult_mono[OF ub ub this \<open>0 \<le> cos ?x2\<close>]
  1378         have "cos ?x2 * cos ?x2 \<le> real y * real y" .
  1368         have "cos ?x2 * cos ?x2 \<le> real_of_float y * real_of_float y" .
  1379         hence "2 * cos ?x2 * cos ?x2 \<le> 2 * real y * real y"
  1369         hence "2 * cos ?x2 * cos ?x2 \<le> 2 * real_of_float y * real_of_float y"
  1380           by auto
  1370           by auto
  1381         hence "2 * cos (x / 2) * cos (x / 2) - 1 \<le> 2 * real y * real y - 1"
  1371         hence "2 * cos (x / 2) * cos (x / 2) - 1 \<le> 2 * real_of_float y * real_of_float y - 1"
  1382           unfolding Float_num by auto
  1372           unfolding Float_num by auto
  1383         thus ?thesis
  1373         thus ?thesis
  1384           unfolding x_half Float_num
  1374           unfolding x_half Float_num
  1385           by (auto intro!: float_plus_up_le)
  1375           by (auto intro!: float_plus_up_le)
  1386       qed
  1376       qed
  1388 
  1378 
  1389     let ?x2 = "x * Float 1 (- 1)"
  1379     let ?x2 = "x * Float 1 (- 1)"
  1390     let ?x4 = "x * Float 1 (- 1) * Float 1 (- 1)"
  1380     let ?x4 = "x * Float 1 (- 1) * Float 1 (- 1)"
  1391 
  1381 
  1392     have "-pi \<le> x"
  1382     have "-pi \<le> x"
  1393       using pi_ge_zero[THEN le_imp_neg_le, unfolded minus_zero] \<open>0 \<le> real x\<close>
  1383       using pi_ge_zero[THEN le_imp_neg_le, unfolded minus_zero] \<open>0 \<le> real_of_float x\<close>
  1394       by (rule order_trans)
  1384       by (rule order_trans)
  1395 
  1385 
  1396     show ?thesis
  1386     show ?thesis
  1397     proof (cases "x < 1")
  1387     proof (cases "x < 1")
  1398       case True
  1388       case True
  1399       hence "real x \<le> 1" by auto
  1389       hence "real_of_float x \<le> 1" by auto
  1400       have "0 \<le> real ?x2" and "?x2 \<le> pi / 2"
  1390       have "0 \<le> real_of_float ?x2" and "?x2 \<le> pi / 2"
  1401         using pi_ge_two \<open>0 \<le> real x\<close> using assms by auto
  1391         using pi_ge_two \<open>0 \<le> real_of_float x\<close> using assms by auto
  1402       from cos_boundaries[OF this]
  1392       from cos_boundaries[OF this]
  1403       have lb: "(?lb_horner ?x2) \<le> ?cos ?x2" and ub: "?cos ?x2 \<le> (?ub_horner ?x2)"
  1393       have lb: "(?lb_horner ?x2) \<le> ?cos ?x2" and ub: "?cos ?x2 \<le> (?ub_horner ?x2)"
  1404         by auto
  1394         by auto
  1405 
  1395 
  1406       have "(?lb x) \<le> ?cos x"
  1396       have "(?lb x) \<le> ?cos x"
  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
  1452   qed
  1442   qed
  1453 qed
  1443 qed
  1454 
  1444 
  1455 lemma lb_cos_minus:
  1445 lemma lb_cos_minus:
  1456   assumes "-pi \<le> x"
  1446   assumes "-pi \<le> x"
  1457     and "real x \<le> 0"
  1447     and "real_of_float x \<le> 0"
  1458   shows "cos (real(-x)) \<in> {(lb_cos prec (-x)) .. (ub_cos prec (-x))}"
  1448   shows "cos (real_of_float(-x)) \<in> {(lb_cos prec (-x)) .. (ub_cos prec (-x))}"
  1459 proof -
  1449 proof -
  1460   have "0 \<le> real (-x)" and "(-x) \<le> pi"
  1450   have "0 \<le> real_of_float (-x)" and "(-x) \<le> pi"
  1461     using \<open>-pi \<le> x\<close> \<open>real x \<le> 0\<close> by auto
  1451     using \<open>-pi \<le> x\<close> \<open>real_of_float x \<le> 0\<close> by auto
  1462   from lb_cos[OF this] show ?thesis .
  1452   from lb_cos[OF this] show ?thesis .
  1463 qed
  1453 qed
  1464 
  1454 
  1465 definition bnds_cos :: "nat \<Rightarrow> float \<Rightarrow> float \<Rightarrow> float * float" where
  1455 definition bnds_cos :: "nat \<Rightarrow> float \<Rightarrow> float \<Rightarrow> float * float" where
  1466 "bnds_cos prec lx ux = (let
  1456 "bnds_cos prec lx ux = (let
  1474   else if - lpi \<le> lx \<and> ux \<le> lpi  then (min (lb_cos prec (-lx)) (lb_cos prec ux), Float 1 0)
  1464   else if - lpi \<le> lx \<and> ux \<le> lpi  then (min (lb_cos prec (-lx)) (lb_cos prec ux), Float 1 0)
  1475   else if 0 \<le> lx \<and> ux \<le> 2 * lpi  then (Float (- 1) 0, max (ub_cos prec lx) (ub_cos prec (- (ux - 2 * lpi))))
  1465   else if 0 \<le> lx \<and> ux \<le> 2 * lpi  then (Float (- 1) 0, max (ub_cos prec lx) (ub_cos prec (- (ux - 2 * lpi))))
  1476   else if -2 * lpi \<le> lx \<and> ux \<le> 0 then (Float (- 1) 0, max (ub_cos prec (lx + 2 * lpi)) (ub_cos prec (-ux)))
  1466   else if -2 * lpi \<le> lx \<and> ux \<le> 0 then (Float (- 1) 0, max (ub_cos prec (lx + 2 * lpi)) (ub_cos prec (-ux)))
  1477                                  else (Float (- 1) 0, Float 1 0))"
  1467                                  else (Float (- 1) 0, Float 1 0))"
  1478 
  1468 
  1479 lemma floor_int: obtains k :: int where "real k = (floor_fl f)"
  1469 lemma floor_int: obtains k :: int where "real_of_int k = (floor_fl f)"
  1480   by (simp add: floor_fl_def)
  1470   by (simp add: floor_fl_def)
  1481 
  1471 
  1482 lemma cos_periodic_nat[simp]:
  1472 lemma cos_periodic_nat[simp]:
  1483   fixes n :: nat
  1473   fixes n :: nat
  1484   shows "cos (x + n * (2 * pi)) = cos x"
  1474   shows "cos (x + n * (2 * pi)) = cos x"
  1486   case 0
  1476   case 0
  1487   then show ?case by simp
  1477   then show ?case by simp
  1488 next
  1478 next
  1489   case (Suc n)
  1479   case (Suc n)
  1490   have split_pi_off: "x + (Suc n) * (2 * pi) = (x + n * (2 * pi)) + 2 * pi"
  1480   have split_pi_off: "x + (Suc n) * (2 * pi) = (x + n * (2 * pi)) + 2 * pi"
  1491     unfolding Suc_eq_plus1 real_of_nat_add real_of_one distrib_right by auto
  1481     unfolding Suc_eq_plus1 of_nat_add of_int_1 distrib_right by auto
  1492   show ?case
  1482   show ?case
  1493     unfolding split_pi_off using Suc by auto
  1483     unfolding split_pi_off using Suc by auto
  1494 qed
  1484 qed
  1495 
  1485 
  1496 lemma cos_periodic_int[simp]:
  1486 lemma cos_periodic_int[simp]:
  1497   fixes i :: int
  1487   fixes i :: int
  1498   shows "cos (x + i * (2 * pi)) = cos x"
  1488   shows "cos (x + i * (2 * pi)) = cos x"
  1499 proof (cases "0 \<le> i")
  1489 proof (cases "0 \<le> i")
  1500   case True
  1490   case True
  1501   hence i_nat: "real i = nat i" by auto
  1491   hence i_nat: "real_of_int i = nat i" by auto
  1502   show ?thesis
  1492   show ?thesis
  1503     unfolding i_nat by auto
  1493     unfolding i_nat by auto
  1504 next
  1494 next
  1505   case False
  1495   case False
  1506     hence i_nat: "i = - real (nat (-i))" by auto
  1496     hence i_nat: "i = - real (nat (-i))" by auto
  1524   let ?lx2 = "(- ?k * 2 * (if ?k < 0 then ?lpi else ?upi))"
  1514   let ?lx2 = "(- ?k * 2 * (if ?k < 0 then ?lpi else ?upi))"
  1525   let ?ux2 = "(- ?k * 2 * (if ?k < 0 then ?upi else ?lpi))"
  1515   let ?ux2 = "(- ?k * 2 * (if ?k < 0 then ?upi else ?lpi))"
  1526   let ?lx = "float_plus_down prec lx ?lx2"
  1516   let ?lx = "float_plus_down prec lx ?lx2"
  1527   let ?ux = "float_plus_up prec ux ?ux2"
  1517   let ?ux = "float_plus_up prec ux ?ux2"
  1528 
  1518 
  1529   obtain k :: int where k: "k = real ?k"
  1519   obtain k :: int where k: "k = real_of_float ?k"
  1530     by (rule floor_int)
  1520     by (rule floor_int)
  1531 
  1521 
  1532   have upi: "pi \<le> ?upi" and lpi: "?lpi \<le> pi"
  1522   have upi: "pi \<le> ?upi" and lpi: "?lpi \<le> pi"
  1533     using float_round_up[of "ub_pi prec" prec] pi_boundaries[of prec]
  1523     using float_round_up[of "ub_pi prec" prec] pi_boundaries[of prec]
  1534       float_round_down[of prec "lb_pi prec"]
  1524       float_round_down[of prec "lb_pi prec"]
  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 
  1646           with bnds 1 2 3
  1636           with bnds 1 2 3
  1647           have l: "l = Float (- 1) 0"
  1637           have l: "l = Float (- 1) 0"
  1648             and u: "u = max (ub_cos prec ?lx) (ub_cos prec (- (?ux - 2 * ?lpi)))"
  1638             and u: "u = max (ub_cos prec ?lx) (ub_cos prec (- (?ux - 2 * ?lpi)))"
  1649             by (auto simp add: bnds_cos_def Let_def)
  1639             by (auto simp add: bnds_cos_def Let_def)
  1650 
  1640 
  1651           have "cos x \<le> real u"
  1641           have "cos x \<le> real_of_float u"
  1652           proof (cases "x - k * (2 * pi) < pi")
  1642           proof (cases "x - k * (2 * pi) < pi")
  1653             case True
  1643             case True
  1654             hence "x - k * (2 * pi) \<le> pi" by simp
  1644             hence "x - k * (2 * pi) \<le> pi" by simp
  1655             from positive_lx[OF Cond[THEN conjunct1] this] show ?thesis
  1645             from positive_lx[OF Cond[THEN conjunct1] this] show ?thesis
  1656               unfolding u by (simp add: real_of_float_max)
  1646               unfolding u by (simp add: real_of_float_max)
  1662             have "?ux \<le> 2 * pi"
  1652             have "?ux \<le> 2 * pi"
  1663               using Cond lpi by auto
  1653               using Cond lpi by auto
  1664             hence "x - k * (2 * pi) - 2 * pi \<le> 0"
  1654             hence "x - k * (2 * pi) - 2 * pi \<le> 0"
  1665               using ux by simp
  1655               using ux by simp
  1666 
  1656 
  1667             have ux_0: "real (?ux - 2 * ?lpi) \<le> 0"
  1657             have ux_0: "real_of_float (?ux - 2 * ?lpi) \<le> 0"
  1668               using Cond by auto
  1658               using Cond by auto
  1669 
  1659 
  1670             from 2 and Cond have "\<not> ?ux \<le> ?lpi" by auto
  1660             from 2 and Cond have "\<not> ?ux \<le> ?lpi" by auto
  1671             hence "- ?lpi \<le> ?ux - 2 * ?lpi" by auto
  1661             hence "- ?lpi \<le> ?ux - 2 * ?lpi" by auto
  1672             hence pi_ux: "- pi \<le> (?ux - 2 * ?lpi)"
  1662             hence pi_ux: "- pi \<le> (?ux - 2 * ?lpi)"
  1676               using ux lpi by auto
  1666               using ux lpi by auto
  1677             have "cos x = cos (x + (-k) * (2 * pi) + (-1::int) * (2 * pi))"
  1667             have "cos x = cos (x + (-k) * (2 * pi) + (-1::int) * (2 * pi))"
  1678               unfolding cos_periodic_int ..
  1668               unfolding cos_periodic_int ..
  1679             also have "\<dots> \<le> cos ((?ux - 2 * ?lpi))"
  1669             also have "\<dots> \<le> cos ((?ux - 2 * ?lpi))"
  1680               using cos_monotone_minus_pi_0'[OF pi_x x_le_ux ux_0]
  1670               using cos_monotone_minus_pi_0'[OF pi_x x_le_ux ux_0]
  1681               by (simp only: minus_float.rep_eq real_of_int_minus real_of_one
  1671               by (simp only: minus_float.rep_eq of_int_minus of_int_1
  1682                 mult_minus_left mult_1_left) simp
  1672                 mult_minus_left mult_1_left) simp
  1683             also have "\<dots> = cos ((- (?ux - 2 * ?lpi)))"
  1673             also have "\<dots> = cos ((- (?ux - 2 * ?lpi)))"
  1684               unfolding uminus_float.rep_eq cos_minus ..
  1674               unfolding uminus_float.rep_eq cos_minus ..
  1685             also have "\<dots> \<le> (ub_cos prec (- (?ux - 2 * ?lpi)))"
  1675             also have "\<dots> \<le> (ub_cos prec (- (?ux - 2 * ?lpi)))"
  1686               using lb_cos_minus[OF pi_ux ux_0] by simp
  1676               using lb_cos_minus[OF pi_ux ux_0] by simp
  1709 
  1699 
  1710               have "-2 * pi \<le> ?lx" using Cond lpi by auto
  1700               have "-2 * pi \<le> ?lx" using Cond lpi by auto
  1711 
  1701 
  1712               hence "0 \<le> x - k * (2 * pi) + 2 * pi" using lx by simp
  1702               hence "0 \<le> x - k * (2 * pi) + 2 * pi" using lx by simp
  1713 
  1703 
  1714               have lx_0: "0 \<le> real (?lx + 2 * ?lpi)"
  1704               have lx_0: "0 \<le> real_of_float (?lx + 2 * ?lpi)"
  1715                 using Cond lpi by auto
  1705                 using Cond lpi by auto
  1716 
  1706 
  1717               from 1 and Cond have "\<not> -?lpi \<le> ?lx" by auto
  1707               from 1 and Cond have "\<not> -?lpi \<le> ?lx" by auto
  1718               hence "?lx + 2 * ?lpi \<le> ?lpi" by auto
  1708               hence "?lx + 2 * ?lpi \<le> ?lpi" by auto
  1719               hence pi_lx: "(?lx + 2 * ?lpi) \<le> pi"
  1709               hence pi_lx: "(?lx + 2 * ?lpi) \<le> pi"
  1724 
  1714 
  1725               have "cos x = cos (x + (-k) * (2 * pi) + (1 :: int) * (2 * pi))"
  1715               have "cos x = cos (x + (-k) * (2 * pi) + (1 :: int) * (2 * pi))"
  1726                 unfolding cos_periodic_int ..
  1716                 unfolding cos_periodic_int ..
  1727               also have "\<dots> \<le> cos ((?lx + 2 * ?lpi))"
  1717               also have "\<dots> \<le> cos ((?lx + 2 * ?lpi))"
  1728                 using cos_monotone_0_pi_le[OF lx_0 lx_le_x pi_x]
  1718                 using cos_monotone_0_pi_le[OF lx_0 lx_le_x pi_x]
  1729                 by (simp only: minus_float.rep_eq real_of_int_minus real_of_one
  1719                 by (simp only: minus_float.rep_eq of_int_minus of_int_1
  1730                   mult_minus_left mult_1_left) simp
  1720                   mult_minus_left mult_1_left) simp
  1731               also have "\<dots> \<le> (ub_cos prec (?lx + 2 * ?lpi))"
  1721               also have "\<dots> \<le> (ub_cos prec (?lx + 2 * ?lpi))"
  1732                 using lb_cos[OF lx_0 pi_lx] by simp
  1722                 using lb_cos[OF lx_0 pi_lx] by simp
  1733               finally show ?thesis unfolding u by (simp add: real_of_float_max)
  1723               finally show ?thesis unfolding u by (simp add: real_of_float_max)
  1734             qed
  1724             qed
  1758 "lb_exp_horner prec 0 i k x       = 0" |
  1748 "lb_exp_horner prec 0 i k x       = 0" |
  1759 "lb_exp_horner prec (Suc n) i k x = float_plus_down prec
  1749 "lb_exp_horner prec (Suc n) i k x = float_plus_down prec
  1760     (lapprox_rat prec 1 (int k)) (float_round_down prec (x * ub_exp_horner prec n (i + 1) (k * i) x))"
  1750     (lapprox_rat prec 1 (int k)) (float_round_down prec (x * ub_exp_horner prec n (i + 1) (k * i) x))"
  1761 
  1751 
  1762 lemma bnds_exp_horner:
  1752 lemma bnds_exp_horner:
  1763   assumes "real x \<le> 0"
  1753   assumes "real_of_float x \<le> 0"
  1764   shows "exp x \<in> {lb_exp_horner prec (get_even n) 1 1 x .. ub_exp_horner prec (get_odd n) 1 1 x}"
  1754   shows "exp x \<in> {lb_exp_horner prec (get_even n) 1 1 x .. ub_exp_horner prec (get_odd n) 1 1 x}"
  1765 proof -
  1755 proof -
  1766   have f_eq: "fact (Suc n) = fact n * ((\<lambda>i::nat. i + 1) ^^ n) 1" for n
  1756   have f_eq: "fact (Suc n) = fact n * ((\<lambda>i::nat. i + 1) ^^ n) 1" for n
  1767   proof -
  1757   proof -
  1768     have F: "\<And> m. ((\<lambda>i. i + 1) ^^ n) m = n + m"
  1758     have F: "\<And> m. ((\<lambda>i. i + 1) ^^ n) m = n + m"
  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"
  1848 proof -
  1838 proof -
  1849   have eq4: "4 = Suc (Suc (Suc (Suc 0)))" by auto
  1839   have eq4: "4 = Suc (Suc (Suc (Suc 0)))" by auto
  1850   have "1 / 4 = (Float 1 (- 2))"
  1840   have "1 / 4 = (Float 1 (- 2))"
  1851     unfolding Float_num by auto
  1841     unfolding Float_num by auto
  1852   also have "\<dots> \<le> lb_exp_horner 3 (get_even 3) 1 1 (- 1)"
  1842   also have "\<dots> \<le> lb_exp_horner 3 (get_even 3) 1 1 (- 1)"
  1853     by code_simp
  1843     by (subst less_eq_float.rep_eq [symmetric]) code_simp
  1854   also have "\<dots> \<le> exp (- 1 :: float)"
  1844   also have "\<dots> \<le> exp (- 1 :: float)"
  1855     using bnds_exp_horner[where x="- 1"] by auto
  1845     using bnds_exp_horner[where x="- 1"] by auto
  1856   finally show ?thesis
  1846   finally show ?thesis
  1857     by simp
  1847     by simp
  1858 qed
  1848 qed
  1863 proof -
  1853 proof -
  1864   let "?lb_horner x" = "lb_exp_horner prec (get_even (prec + 2)) 1 1 x"
  1854   let "?lb_horner x" = "lb_exp_horner prec (get_even (prec + 2)) 1 1 x"
  1865   let "?horner x" = "let y = ?lb_horner x in if y \<le> 0 then Float 1 (- 2) else y"
  1855   let "?horner x" = "let y = ?lb_horner x in if y \<le> 0 then Float 1 (- 2) else y"
  1866   have pos_horner: "0 < ?horner x" for x
  1856   have pos_horner: "0 < ?horner x" for x
  1867     unfolding Let_def by (cases "?lb_horner x \<le> 0") auto
  1857     unfolding Let_def by (cases "?lb_horner x \<le> 0") auto
  1868   moreover have "0 < real ((?horner x) ^ num)" for x :: float and num :: nat
  1858   moreover have "0 < real_of_float ((?horner x) ^ num)" for x :: float and num :: nat
  1869   proof -
  1859   proof -
  1870     have "0 < real (?horner x) ^ num" using \<open>0 < ?horner x\<close> by simp
  1860     have "0 < real_of_float (?horner x) ^ num" using \<open>0 < ?horner x\<close> by simp
  1871     also have "\<dots> = (?horner x) ^ num" by auto
  1861     also have "\<dots> = (?horner x) ^ num" by auto
  1872     finally show ?thesis .
  1862     finally show ?thesis .
  1873   qed
  1863   qed
  1874   ultimately show ?thesis
  1864   ultimately show ?thesis
  1875     unfolding lb_exp.simps if_not_P[OF \<open>\<not> 0 < x\<close>] Let_def
  1865     unfolding lb_exp.simps if_not_P[OF \<open>\<not> 0 < x\<close>] Let_def
  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
  2025     hence "-x \<le> 0" by auto
  2015     hence "-x \<le> 0" by auto
  2026 
  2016 
  2027     have "lb_exp prec x \<le> exp x"
  2017     have "lb_exp prec x \<le> exp x"
  2028     proof -
  2018     proof -
  2029       from exp_boundaries'[OF \<open>-x \<le> 0\<close>]
  2019       from exp_boundaries'[OF \<open>-x \<le> 0\<close>]
  2030       have ub_exp: "exp (- real x) \<le> ub_exp prec (-x)"
  2020       have ub_exp: "exp (- real_of_float x) \<le> ub_exp prec (-x)"
  2031         unfolding atLeastAtMost_iff minus_float.rep_eq by auto
  2021         unfolding atLeastAtMost_iff minus_float.rep_eq by auto
  2032 
  2022 
  2033       have "float_divl prec 1 (ub_exp prec (-x)) \<le> 1 / ub_exp prec (-x)"
  2023       have "float_divl prec 1 (ub_exp prec (-x)) \<le> 1 / ub_exp prec (-x)"
  2034         using float_divl[where x=1] by auto
  2024         using float_divl[where x=1] by auto
  2035       also have "\<dots> \<le> exp x"
  2025       also have "\<dots> \<le> exp x"
  2044     have "exp x \<le> ub_exp prec x"
  2034     have "exp x \<le> ub_exp prec x"
  2045     proof -
  2035     proof -
  2046       have "\<not> 0 < -x" using \<open>0 < x\<close> by auto
  2036       have "\<not> 0 < -x" using \<open>0 < x\<close> by auto
  2047 
  2037 
  2048       from exp_boundaries'[OF \<open>-x \<le> 0\<close>]
  2038       from exp_boundaries'[OF \<open>-x \<le> 0\<close>]
  2049       have lb_exp: "lb_exp prec (-x) \<le> exp (- real x)"
  2039       have lb_exp: "lb_exp prec (-x) \<le> exp (- real_of_float x)"
  2050         unfolding atLeastAtMost_iff minus_float.rep_eq by auto
  2040         unfolding atLeastAtMost_iff minus_float.rep_eq by auto
  2051 
  2041 
  2052       have "exp x \<le> (1 :: float) / lb_exp prec (-x)"
  2042       have "exp x \<le> (1 :: float) / lb_exp prec (-x)"
  2053         using lb_exp lb_exp_pos[OF \<open>\<not> 0 < -x\<close>, of prec]
  2043         using lb_exp lb_exp_pos[OF \<open>\<not> 0 < -x\<close>, of prec]
  2054         by (simp del: lb_exp.simps add: exp_minus inverse_eq_divide field_simps)
  2044         by (simp del: lb_exp.simps add: exp_minus inverse_eq_divide field_simps)
  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)
  2303     by (auto simp add: zero_less_mult_iff intro!: arg_cong2[where f=Float])
  2297     by (auto simp add: zero_less_mult_iff intro!: arg_cong2[where f=Float])
  2304   have "x \<noteq> float_of 0"
  2298   have "x \<noteq> float_of 0"
  2305     unfolding zero_float_def[symmetric] using \<open>0 < x\<close> by auto
  2299     unfolding zero_float_def[symmetric] using \<open>0 < x\<close> by auto
  2306   from denormalize_shift[OF assms(1) this] guess i . note i = this
  2300   from denormalize_shift[OF assms(1) this] guess i . note i = this
  2307 
  2301 
  2308   have "2 powr (1 - (real (bitlen (mantissa x)) + real i)) =
  2302   have "2 powr (1 - (real_of_int (bitlen (mantissa x)) + real_of_int i)) =
  2309     2 powr (1 - (real (bitlen (mantissa x)))) * inverse (2 powr (real i))"
  2303     2 powr (1 - (real_of_int (bitlen (mantissa x)))) * inverse (2 powr (real i))"
  2310     by (simp add: powr_minus[symmetric] powr_add[symmetric] field_simps)
  2304     by (simp add: powr_minus[symmetric] powr_add[symmetric] field_simps)
  2311   hence "real (mantissa x) * 2 powr (1 - real (bitlen (mantissa x))) =
  2305   hence "real_of_int (mantissa x) * 2 powr (1 - real_of_int (bitlen (mantissa x))) =
  2312     (real (mantissa x) * 2 ^ i) * 2 powr (1 - real (bitlen (mantissa x * 2 ^ i)))"
  2306     (real_of_int (mantissa x) * 2 ^ i) * 2 powr (1 - real_of_int (bitlen (mantissa x * 2 ^ i)))"
  2313     using \<open>mantissa x > 0\<close> by (simp add: powr_realpow)
  2307     using \<open>mantissa x > 0\<close> by (simp add: powr_realpow)
  2314   then show ?th2
  2308   then show ?th2
  2315     unfolding i by transfer auto
  2309     unfolding i by transfer auto
  2316 qed
  2310 qed
  2317 
  2311 
  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
  2636   fix lx ux
  2630   fix lx ux
  2637   assume "(Some l, Some u) = (lb_ln prec lx, ub_ln prec ux) \<and> x \<in> {lx .. ux}"
  2631   assume "(Some l, Some u) = (lb_ln prec lx, ub_ln prec ux) \<and> x \<in> {lx .. ux}"
  2638   hence l: "Some l = lb_ln prec lx " and u: "Some u = ub_ln prec ux" and x: "x \<in> {lx .. ux}"
  2632   hence l: "Some l = lb_ln prec lx " and u: "Some u = ub_ln prec ux" and x: "x \<in> {lx .. ux}"
  2639     by auto
  2633     by auto
  2640 
  2634 
  2641   have "ln ux \<le> u" and "0 < real ux"
  2635   have "ln ux \<le> u" and "0 < real_of_float ux"
  2642     using ub_ln u by auto
  2636     using ub_ln u by auto
  2643   have "l \<le> ln lx" and "0 < real lx" and "0 < x"
  2637   have "l \<le> ln lx" and "0 < real_of_float lx" and "0 < x"
  2644     using lb_ln[OF l] x by auto
  2638     using lb_ln[OF l] x by auto
  2645 
  2639 
  2646   from ln_le_cancel_iff[OF \<open>0 < real lx\<close> \<open>0 < x\<close>] \<open>l \<le> ln lx\<close>
  2640   from ln_le_cancel_iff[OF \<open>0 < real_of_float lx\<close> \<open>0 < x\<close>] \<open>l \<le> ln lx\<close>
  2647   have "l \<le> ln x"
  2641   have "l \<le> ln x"
  2648     using x unfolding atLeastAtMost_iff by auto
  2642     using x unfolding atLeastAtMost_iff by auto
  2649   moreover
  2643   moreover
  2650   from ln_le_cancel_iff[OF \<open>0 < x\<close> \<open>0 < real ux\<close>] \<open>ln ux \<le> real u\<close>
  2644   from ln_le_cancel_iff[OF \<open>0 < x\<close> \<open>0 < real_of_float ux\<close>] \<open>ln ux \<le> real_of_float u\<close>
  2651   have "ln x \<le> u"
  2645   have "ln x \<le> u"
  2652     using x unfolding atLeastAtMost_iff by auto
  2646     using x unfolding atLeastAtMost_iff by auto
  2653   ultimately show "l \<le> ln x \<and> ln x \<le> u" ..
  2647   ultimately show "l \<le> ln x \<and> ln x \<le> u" ..
  2654 qed
  2648 qed
  2655 
  2649 
  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
  2947 lemma lift_un'_bnds:
  2942 lemma lift_un'_bnds:
  2948   assumes bnds: "\<forall> (x::real) lx ux. (l, u) = f lx ux \<and> x \<in> { lx .. ux } \<longrightarrow> l \<le> f' x \<and> f' x \<le> u"
  2943   assumes bnds: "\<forall> (x::real) lx ux. (l, u) = f lx ux \<and> x \<in> { lx .. ux } \<longrightarrow> l \<le> f' x \<and> f' x \<le> u"
  2949     and lift_un'_Some: "Some (l, u) = lift_un' (approx' prec a bs) f"
  2944     and lift_un'_Some: "Some (l, u) = lift_un' (approx' prec a bs) f"
  2950     and Pa: "\<And>l u. Some (l, u) = approx prec a bs \<Longrightarrow>
  2945     and Pa: "\<And>l u. Some (l, u) = approx prec a bs \<Longrightarrow>
  2951       l \<le> interpret_floatarith a xs \<and> interpret_floatarith a xs \<le> u"
  2946       l \<le> interpret_floatarith a xs \<and> interpret_floatarith a xs \<le> u"
  2952   shows "real l \<le> f' (interpret_floatarith a xs) \<and> f' (interpret_floatarith a xs) \<le> real u"
  2947   shows "real_of_float l \<le> f' (interpret_floatarith a xs) \<and> f' (interpret_floatarith a xs) \<le> real_of_float u"
  2953 proof -
  2948 proof -
  2954   from lift_un'[OF lift_un'_Some Pa]
  2949   from lift_un'[OF lift_un'_Some Pa]
  2955   obtain l1 u1 where "l1 \<le> interpret_floatarith a xs"
  2950   obtain l1 u1 where "l1 \<le> interpret_floatarith a xs"
  2956     and "interpret_floatarith a xs \<le> u1"
  2951     and "interpret_floatarith a xs \<le> u1"
  2957     and "l = fst (f l1 u1)"
  2952     and "l = fst (f l1 u1)"
  3037 lemma lift_un_bnds:
  3032 lemma lift_un_bnds:
  3038   assumes bnds: "\<forall>(x::real) lx ux. (Some l, Some u) = f lx ux \<and> x \<in> { lx .. ux } \<longrightarrow> l \<le> f' x \<and> f' x \<le> u"
  3033   assumes bnds: "\<forall>(x::real) lx ux. (Some l, Some u) = f lx ux \<and> x \<in> { lx .. ux } \<longrightarrow> l \<le> f' x \<and> f' x \<le> u"
  3039     and lift_un_Some: "Some (l, u) = lift_un (approx' prec a bs) f"
  3034     and lift_un_Some: "Some (l, u) = lift_un (approx' prec a bs) f"
  3040     and Pa: "\<And>l u. Some (l, u) = approx prec a bs \<Longrightarrow>
  3035     and Pa: "\<And>l u. Some (l, u) = approx prec a bs \<Longrightarrow>
  3041       l \<le> interpret_floatarith a xs \<and> interpret_floatarith a xs \<le> u"
  3036       l \<le> interpret_floatarith a xs \<and> interpret_floatarith a xs \<le> u"
  3042   shows "real l \<le> f' (interpret_floatarith a xs) \<and> f' (interpret_floatarith a xs) \<le> real u"
  3037   shows "real_of_float l \<le> f' (interpret_floatarith a xs) \<and> f' (interpret_floatarith a xs) \<le> real_of_float u"
  3043 proof -
  3038 proof -
  3044   from lift_un[OF lift_un_Some Pa]
  3039   from lift_un[OF lift_un_Some Pa]
  3045   obtain l1 u1 where "l1 \<le> interpret_floatarith a xs"
  3040   obtain l1 u1 where "l1 \<le> interpret_floatarith a xs"
  3046     and "interpret_floatarith a xs \<le> u1"
  3041     and "interpret_floatarith a xs \<le> u1"
  3047     and "Some l = fst (f l1 u1)"
  3042     and "Some l = fst (f l1 u1)"
  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
  3272   show thesis by auto
  3267   show thesis by auto
  3273 next
  3268 next
  3274   case (Suc s)
  3269   case (Suc s)
  3275 
  3270 
  3276   let ?m = "(l + u) * Float 1 (- 1)"
  3271   let ?m = "(l + u) * Float 1 (- 1)"
  3277   have "real l \<le> ?m" and "?m \<le> real u"
  3272   have "real_of_float l \<le> ?m" and "?m \<le> real_of_float u"
  3278     unfolding less_eq_float_def using Suc.prems by auto
  3273     unfolding less_eq_float_def using Suc.prems by auto
  3279 
  3274 
  3280   with \<open>x \<in> { l .. u }\<close>
  3275   with \<open>x \<in> { l .. u }\<close>
  3281   have "x \<in> { l .. ?m} \<or> x \<in> { ?m .. u }" by auto
  3276   have "x \<in> { l .. ?m} \<or> x \<in> { ?m .. u }" by auto
  3282   thus thesis
  3277   thus thesis
  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]
  3450            simp del: interpret_floatarith.simps(5)
  3445            simp del: interpret_floatarith.simps(5)
  3451            simp add: interpret_floatarith_sin interpret_floatarith.simps(5)[of a])
  3446            simp add: interpret_floatarith_sin interpret_floatarith.simps(5)[of a])
  3452 next
  3447 next
  3453   case (Power a n)
  3448   case (Power a n)
  3454   thus ?case
  3449   thus ?case
  3455     by (cases n) (auto intro!: derivative_eq_intros simp del: power_Suc simp add: real_of_nat_def)
  3450     by (cases n) (auto intro!: derivative_eq_intros simp del: power_Suc)
  3456 next
  3451 next
  3457   case (Ln a)
  3452   case (Ln a)
  3458   thus ?case by (auto intro!: derivative_eq_intros simp add: divide_inverse)
  3453   thus ?case by (auto intro!: derivative_eq_intros simp add: divide_inverse)
  3459 next
  3454 next
  3460   case (Var i)
  3455   case (Var i)
  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
  3555 qed
  3550 qed
  3556 
  3551 
  3557 lemma isDERIV_approx':
  3552 lemma isDERIV_approx':
  3558   assumes "bounded_by xs vs"
  3553   assumes "bounded_by xs vs"
  3559     and vs_x: "vs ! x = Some (l, u)"
  3554     and vs_x: "vs ! x = Some (l, u)"
  3560     and X_in: "X \<in> {real l .. real u}"
  3555     and X_in: "X \<in> {real_of_float l .. real_of_float u}"
  3561     and approx: "isDERIV_approx prec x f vs"
  3556     and approx: "isDERIV_approx prec x f vs"
  3562   shows "isDERIV x f (xs[x := X])"
  3557   shows "isDERIV x f (xs[x := X])"
  3563 proof -
  3558 proof -
  3564   from bounded_by_update_var[OF \<open>bounded_by xs vs\<close> vs_x X_in] approx
  3559   from bounded_by_update_var[OF \<open>bounded_by xs vs\<close> vs_x X_in] approx
  3565   show ?thesis by (rule isDERIV_approx)
  3560   show ?thesis by (rule isDERIV_approx)
  3610                                        (Var (Suc 0))))) [Some (l1, u1), Some (l2, u2), bs!n])
  3605                                        (Var (Suc 0))))) [Some (l1, u1), Some (l2, u2), bs!n])
  3611   else approx prec f bs)"
  3606   else approx prec f bs)"
  3612 
  3607 
  3613 lemma bounded_by_Cons:
  3608 lemma bounded_by_Cons:
  3614   assumes bnd: "bounded_by xs vs"
  3609   assumes bnd: "bounded_by xs vs"
  3615     and x: "x \<in> { real l .. real u }"
  3610     and x: "x \<in> { real_of_float l .. real_of_float u }"
  3616   shows "bounded_by (x#xs) ((Some (l, u))#vs)"
  3611   shows "bounded_by (x#xs) ((Some (l, u))#vs)"
  3617 proof -
  3612 proof -
  3618   have "case ((Some (l,u))#vs) ! i of Some (l, u) \<Rightarrow> (x#xs)!i \<in> { real l .. real u } | None \<Rightarrow> True"
  3613   have "case ((Some (l,u))#vs) ! i of Some (l, u) \<Rightarrow> (x#xs)!i \<in> { real_of_float l .. real_of_float u } | None \<Rightarrow> True"
  3619     if *: "i < length ((Some (l, u))#vs)" for i
  3614     if *: "i < length ((Some (l, u))#vs)" for i
  3620   proof (cases i)
  3615   proof (cases i)
  3621     case 0
  3616     case 0
  3622     with x show ?thesis by auto
  3617     with x show ?thesis by auto
  3623   next
  3618   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])
  3750     thus ?thesis using DERIV by blast
  3745     thus ?thesis using DERIV by blast
  3751   qed
  3746   qed
  3752 qed
  3747 qed
  3753 
  3748 
  3754 lemma setprod_fact: "real (\<Prod> {1..<1 + k}) = fact (k :: nat)"
  3749 lemma setprod_fact: "real (\<Prod> {1..<1 + k}) = fact (k :: nat)"
  3755   using fact_altdef_nat Suc_eq_plus1_left atLeastLessThanSuc_atLeastAtMost real_fact_nat
  3750 by (metis Suc_eq_plus1_left atLeastLessThanSuc_atLeastAtMost fact_altdef_nat of_nat_fact)
  3756   by presburger
       
  3757 
  3751 
  3758 lemma approx_tse:
  3752 lemma approx_tse:
  3759   assumes "bounded_by xs vs"
  3753   assumes "bounded_by xs vs"
  3760     and bnd_x: "vs ! x = Some (lx, ux)"
  3754     and bnd_x: "vs ! x = Some (lx, ux)"
  3761     and bnd_c: "real c \<in> {lx .. ux}"
  3755     and bnd_c: "real_of_float c \<in> {lx .. ux}"
  3762     and "x < length vs" and "x < length xs"
  3756     and "x < length vs" and "x < length xs"
  3763     and ate: "Some (l, u) = approx_tse prec x s c 1 f vs"
  3757     and ate: "Some (l, u) = approx_tse prec x s c 1 f vs"
  3764   shows "interpret_floatarith f xs \<in> {l .. u}"
  3758   shows "interpret_floatarith f xs \<in> {l .. u}"
  3765 proof -
  3759 proof -
  3766   def F \<equiv> "\<lambda>n z. interpret_floatarith ((DERIV_floatarith x ^^ n) f) (xs[x := z])"
  3760   def F \<equiv> "\<lambda>n z. interpret_floatarith ((DERIV_floatarith x ^^ n) f) (xs[x := z])"
  3770     using \<open>bounded_by xs vs\<close> bnd_x bnd_c \<open>x < length vs\<close> \<open>x < length xs\<close>
  3764     using \<open>bounded_by xs vs\<close> bnd_x bnd_c \<open>x < length vs\<close> \<open>x < length xs\<close>
  3771     by (auto intro!: bounded_by_update_var)
  3765     by (auto intro!: bounded_by_update_var)
  3772 
  3766 
  3773   from approx_tse_generic[OF \<open>bounded_by xs vs\<close> this bnd_x ate]
  3767   from approx_tse_generic[OF \<open>bounded_by xs vs\<close> this bnd_x ate]
  3774   obtain n
  3768   obtain n
  3775     where DERIV: "\<forall> m z. m < n \<and> real lx \<le> z \<and> z \<le> real ux \<longrightarrow> DERIV (F m) z :> F (Suc m) z"
  3769     where DERIV: "\<forall> m z. m < n \<and> real_of_float lx \<le> z \<and> z \<le> real_of_float ux \<longrightarrow> DERIV (F m) z :> F (Suc m) z"
  3776     and hyp: "\<And> (t::real). t \<in> {lx .. ux} \<Longrightarrow>
  3770     and hyp: "\<And> (t::real). t \<in> {lx .. ux} \<Longrightarrow>
  3777            (\<Sum> j = 0..<n. inverse(fact j) * F j c * (xs!x - c)^j) +
  3771            (\<Sum> j = 0..<n. inverse(fact j) * F j c * (xs!x - c)^j) +
  3778              inverse ((fact n)) * F n t * (xs!x - c)^n
  3772              inverse ((fact n)) * F n t * (xs!x - c)^n
  3779              \<in> {l .. u}" (is "\<And> t. _ \<Longrightarrow> ?taylor t \<in> _")
  3773              \<in> {l .. u}" (is "\<And> t. _ \<Longrightarrow> ?taylor t \<in> _")
  3780     unfolding F_def atLeastAtMost_iff[symmetric] setprod_fact
  3774     unfolding F_def atLeastAtMost_iff[symmetric] setprod_fact
  3796       from True[symmetric] hyp[OF bnd_xs] Suc show ?thesis
  3790       from True[symmetric] hyp[OF bnd_xs] Suc show ?thesis
  3797         unfolding F_def Suc setsum_head_upt_Suc[OF zero_less_Suc] setsum_shift_bounds_Suc_ivl
  3791         unfolding F_def Suc setsum_head_upt_Suc[OF zero_less_Suc] setsum_shift_bounds_Suc_ivl
  3798         by auto
  3792         by auto
  3799     next
  3793     next
  3800       case False
  3794       case False
  3801       have "lx \<le> real c" "real c \<le> ux" "lx \<le> xs!x" "xs!x \<le> ux"
  3795       have "lx \<le> real_of_float c" "real_of_float c \<le> ux" "lx \<le> xs!x" "xs!x \<le> ux"
  3802         using Suc bnd_c \<open>bounded_by xs vs\<close>[THEN bounded_byE, OF \<open>x < length vs\<close>] bnd_x by auto
  3796         using Suc bnd_c \<open>bounded_by xs vs\<close>[THEN bounded_byE, OF \<open>x < length vs\<close>] bnd_x by auto
  3803       from Taylor.taylor[OF zero_less_Suc, of F, OF F0 DERIV[unfolded Suc] this False]
  3797       from Taylor.taylor[OF zero_less_Suc, of F, OF F0 DERIV[unfolded Suc] this False]
  3804       obtain t::real where t_bnd: "if xs ! x < c then xs ! x < t \<and> t < c else c < t \<and> t < xs ! x"
  3798       obtain t::real where t_bnd: "if xs ! x < c then xs ! x < t \<and> t < c else c < t \<and> t < xs ! x"
  3805         and fl_eq: "interpret_floatarith f (xs[x := xs ! x]) =
  3799         and fl_eq: "interpret_floatarith f (xs[x := xs ! x]) =
  3806            (\<Sum>m = 0..<Suc n'. F m c / (fact m) * (xs ! x - c) ^ m) +
  3800            (\<Sum>m = 0..<Suc n'. F m c / (fact m) * (xs ! x - c) ^ m) +
  3831 
  3825 
  3832 lemma approx_tse_form':
  3826 lemma approx_tse_form':
  3833   fixes x :: real
  3827   fixes x :: real
  3834   assumes "approx_tse_form' prec t f s l u cmp"
  3828   assumes "approx_tse_form' prec t f s l u cmp"
  3835     and "x \<in> {l .. u}"
  3829     and "x \<in> {l .. u}"
  3836   shows "\<exists>l' u' ly uy. x \<in> {l' .. u'} \<and> real l \<le> l' \<and> u' \<le> real u \<and> cmp ly uy \<and>
  3830   shows "\<exists>l' u' ly uy. x \<in> {l' .. u'} \<and> real_of_float l \<le> l' \<and> u' \<le> real_of_float u \<and> cmp ly uy \<and>
  3837     approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 f [Some (l', u')] = Some (ly, uy)"
  3831     approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 f [Some (l', u')] = Some (ly, uy)"
  3838   using assms
  3832   using assms
  3839 proof (induct s arbitrary: l u)
  3833 proof (induct s arbitrary: l u)
  3840   case 0
  3834   case 0
  3841   then obtain ly uy
  3835   then obtain ly uy
  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
  3883   shows "interpret_floatarith b [x] < interpret_floatarith a [x]"
  3877   shows "interpret_floatarith b [x] < interpret_floatarith a [x]"
  3884 proof -
  3878 proof -
  3885   from approx_tse_form'[OF tse x]
  3879   from approx_tse_form'[OF tse x]
  3886   obtain l' u' ly uy
  3880   obtain l' u' ly uy
  3887     where x': "x \<in> {l' .. u'}"
  3881     where x': "x \<in> {l' .. u'}"
  3888     and "l \<le> real l'"
  3882     and "real_of_float l \<le> real_of_float l'"
  3889     and "real u' \<le> u" and "0 < ly"
  3883     and "real_of_float u' \<le> real_of_float u" and "0 < ly"
  3890     and tse: "approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 (Add a (Minus b)) [Some (l', u')] = Some (ly, uy)"
  3884     and tse: "approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 (Add a (Minus b)) [Some (l', u')] = Some (ly, uy)"
  3891     by blast
  3885     by blast
  3892 
  3886 
  3893   hence "bounded_by [x] [Some (l', u')]"
  3887   hence "bounded_by [x] [Some (l', u')]"
  3894     by (auto simp add: bounded_by_def)
  3888     by (auto simp add: bounded_by_def)
  3906   shows "interpret_floatarith b [x] \<le> interpret_floatarith a [x]"
  3900   shows "interpret_floatarith b [x] \<le> interpret_floatarith a [x]"
  3907 proof -
  3901 proof -
  3908   from approx_tse_form'[OF tse x]
  3902   from approx_tse_form'[OF tse x]
  3909   obtain l' u' ly uy
  3903   obtain l' u' ly uy
  3910     where x': "x \<in> {l' .. u'}"
  3904     where x': "x \<in> {l' .. u'}"
  3911     and "l \<le> real l'"
  3905     and "l \<le> real_of_float l'"
  3912     and "real u' \<le> u" and "0 \<le> ly"
  3906     and "real_of_float u' \<le> u" and "0 \<le> ly"
  3913     and tse: "approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 (Add a (Minus b)) [Some (l', u')] = Some (ly, uy)"
  3907     and tse: "approx_tse prec 0 t ((l' + u') * Float 1 (- 1)) 1 (Add a (Minus b)) [Some (l', u')] = Some (ly, uy)"
  3914     by blast
  3908     by blast
  3915 
  3909 
  3916   hence "bounded_by [x] [Some (l', u')]" by (auto simp add: bounded_by_def)
  3910   hence "bounded_by [x] [Some (l', u')]" by (auto simp add: bounded_by_def)
  3917   from approx_tse[OF this _ _ _ _ tse[symmetric], of l' u'] x'
  3911   from approx_tse[OF this _ _ _ _ tse[symmetric], of l' u'] x'