717 lemma real_of_int_div_mult: |
717 lemma real_of_int_div_mult: |
718 fixes x y c :: int assumes "0 < y" and "0 < c" |
718 fixes x y c :: int assumes "0 < y" and "0 < c" |
719 shows "real (x div y) \<le> real (x * c div y) * inverse (real c)" |
719 shows "real (x div y) \<le> real (x * c div y) * inverse (real c)" |
720 proof - |
720 proof - |
721 have "c * (x div y) + 0 \<le> c * x div y" unfolding zdiv_zmult1_eq[of c x y] |
721 have "c * (x div y) + 0 \<le> c * x div y" unfolding zdiv_zmult1_eq[of c x y] |
722 by (rule zadd_left_mono, |
722 by (rule add_left_mono, |
723 auto intro!: mult_nonneg_nonneg |
723 auto intro!: mult_nonneg_nonneg |
724 simp add: pos_imp_zdiv_nonneg_iff[OF `0 < y`] `0 < c`[THEN less_imp_le] pos_mod_sign[OF `0 < y`]) |
724 simp add: pos_imp_zdiv_nonneg_iff[OF `0 < y`] `0 < c`[THEN less_imp_le] pos_mod_sign[OF `0 < y`]) |
725 hence "real (x div y) * real c \<le> real (x * c div y)" |
725 hence "real (x div y) * real c \<le> real (x * c div y)" |
726 unfolding real_of_int_mult[symmetric] real_of_int_le_iff zmult_commute by auto |
726 unfolding real_of_int_mult[symmetric] real_of_int_le_iff mult_commute by auto |
727 hence "real (x div y) * real c * inverse (real c) \<le> real (x * c div y) * inverse (real c)" |
727 hence "real (x div y) * real c * inverse (real c) \<le> real (x * c div y) * inverse (real c)" |
728 using `0 < c` by auto |
728 using `0 < c` by auto |
729 thus ?thesis unfolding mult_assoc using `0 < c` by auto |
729 thus ?thesis unfolding mult_assoc using `0 < c` by auto |
730 qed |
730 qed |
731 |
731 |
775 have "0 \<le> real y" and "real y \<noteq> 0" using `0 < y` by auto |
775 have "0 \<le> real y" and "real y \<noteq> 0" using `0 < y` by auto |
776 have "0 \<le> real y * 2^?l" by (rule mult_nonneg_nonneg, rule `0 \<le> real y`, auto) |
776 have "0 \<le> real y * 2^?l" by (rule mult_nonneg_nonneg, rule `0 \<le> real y`, auto) |
777 |
777 |
778 have "?X = y * (?X div y) + ?X mod y" by auto |
778 have "?X = y * (?X div y) + ?X mod y" by auto |
779 also have "\<dots> \<le> y * (?X div y) + y" by (rule add_mono, auto simp add: pos_mod_bound[OF `0 < y`, THEN less_imp_le]) |
779 also have "\<dots> \<le> y * (?X div y) + y" by (rule add_mono, auto simp add: pos_mod_bound[OF `0 < y`, THEN less_imp_le]) |
780 also have "\<dots> = y * (?X div y + 1)" unfolding zadd_zmult_distrib2 by auto |
780 also have "\<dots> = y * (?X div y + 1)" unfolding right_distrib by auto |
781 finally have "real ?X \<le> real y * real (?X div y + 1)" unfolding real_of_int_le_iff real_of_int_mult[symmetric] . |
781 finally have "real ?X \<le> real y * real (?X div y + 1)" unfolding real_of_int_le_iff real_of_int_mult[symmetric] . |
782 hence "real ?X / (real y * 2^?l) \<le> real y * real (?X div y + 1) / (real y * 2^?l)" |
782 hence "real ?X / (real y * 2^?l) \<le> real y * real (?X div y + 1) / (real y * 2^?l)" |
783 by (rule divide_right_mono, simp only: `0 \<le> real y * 2^?l`) |
783 by (rule divide_right_mono, simp only: `0 \<le> real y * 2^?l`) |
784 also have "\<dots> = real y * real (?X div y + 1) / real y / 2^?l" by auto |
784 also have "\<dots> = real y * real (?X div y + 1) / real y / 2^?l" by auto |
785 also have "\<dots> = real (?X div y + 1) * inverse (2^?l)" unfolding nonzero_mult_divide_cancel_left[OF `real y \<noteq> 0`] |
785 also have "\<dots> = real (?X div y + 1) * inverse (2^?l)" unfolding nonzero_mult_divide_cancel_left[OF `real y \<noteq> 0`] |
1142 let ?d = "real (2 ^ nat (int prec + bitlen m - 1) div m) * inverse (2 ^ nat (int prec + bitlen m - 1))" |
1142 let ?d = "real (2 ^ nat (int prec + bitlen m - 1) div m) * inverse (2 ^ nat (int prec + bitlen m - 1))" |
1143 { |
1143 { |
1144 have "2^(prec - 1) * m \<le> 2^(prec - 1) * 2^?b" |
1144 have "2^(prec - 1) * m \<le> 2^(prec - 1) * 2^?b" |
1145 using `m < 2^?b`[THEN less_imp_le] by (rule mult_left_mono) auto |
1145 using `m < 2^?b`[THEN less_imp_le] by (rule mult_left_mono) auto |
1146 also have "\<dots> = 2 ^ nat (int prec + bitlen m - 1)" |
1146 also have "\<dots> = 2 ^ nat (int prec + bitlen m - 1)" |
1147 unfolding pow_split zpower_zadd_distrib by auto |
1147 unfolding pow_split power_add by auto |
1148 finally have "2^(prec - 1) * m div m \<le> 2 ^ nat (int prec + bitlen m - 1) div m" |
1148 finally have "2^(prec - 1) * m div m \<le> 2 ^ nat (int prec + bitlen m - 1) div m" |
1149 using `0 < m` by (rule zdiv_mono1) |
1149 using `0 < m` by (rule zdiv_mono1) |
1150 hence "2^(prec - 1) \<le> 2 ^ nat (int prec + bitlen m - 1) div m" |
1150 hence "2^(prec - 1) \<le> 2 ^ nat (int prec + bitlen m - 1) div m" |
1151 unfolding div_mult_self2_is_id[OF `m \<noteq> 0`] . |
1151 unfolding div_mult_self2_is_id[OF `m \<noteq> 0`] . |
1152 hence "2^(prec - 1) * inverse (2 ^ nat (int prec + bitlen m - 1)) \<le> ?d" |
1152 hence "2^(prec - 1) * inverse (2 ^ nat (int prec + bitlen m - 1)) \<le> ?d" |
1271 unfolding Float round_up.simps Let_def if_P[OF `m mod ?p = 0`] if_P[OF `0 < ?d`] |
1271 unfolding Float round_up.simps Let_def if_P[OF `m mod ?p = 0`] if_P[OF `0 < ?d`] |
1272 by auto |
1272 by auto |
1273 next |
1273 next |
1274 case False |
1274 case False |
1275 have "m = m div ?p * ?p + m mod ?p" unfolding zdiv_zmod_equality2[where k=0, unfolded monoid_add_class.add_0_right] .. |
1275 have "m = m div ?p * ?p + m mod ?p" unfolding zdiv_zmod_equality2[where k=0, unfolded monoid_add_class.add_0_right] .. |
1276 also have "\<dots> \<le> (m div ?p + 1) * ?p" unfolding left_distrib zmult_1 by (rule add_left_mono, rule pos_mod_bound[OF `0 < ?p`, THEN less_imp_le]) |
1276 also have "\<dots> \<le> (m div ?p + 1) * ?p" unfolding left_distrib mult_1 by (rule add_left_mono, rule pos_mod_bound[OF `0 < ?p`, THEN less_imp_le]) |
1277 finally have "real (Float m e) \<le> real (Float (m div ?p + 1) (e + ?d))" unfolding real_of_float_simp add_commute[of e] |
1277 finally have "real (Float m e) \<le> real (Float (m div ?p + 1) (e + ?d))" unfolding real_of_float_simp add_commute[of e] |
1278 unfolding pow2_add mult_assoc[symmetric] real_of_int_le_iff[of m, symmetric] |
1278 unfolding pow2_add mult_assoc[symmetric] real_of_int_le_iff[of m, symmetric] |
1279 by (auto intro!: mult_mono simp add: pow2_add `0 < ?d` pow_d) |
1279 by (auto intro!: mult_mono simp add: pow2_add `0 < ?d` pow_d) |
1280 thus ?thesis |
1280 thus ?thesis |
1281 unfolding Float round_up.simps Let_def if_not_P[OF `\<not> m mod ?p = 0`] if_P[OF `0 < ?d`] . |
1281 unfolding Float round_up.simps Let_def if_not_P[OF `\<not> m mod ?p = 0`] if_P[OF `0 < ?d`] . |
1359 next |
1359 next |
1360 case True |
1360 case True |
1361 have "real m \<le> real (m div 2^(nat ?l) + 1) * pow2 ?l" |
1361 have "real m \<le> real (m div 2^(nat ?l) + 1) * pow2 ?l" |
1362 proof - |
1362 proof - |
1363 have "m mod 2^(nat ?l) < 2^(nat ?l)" by (rule pos_mod_bound) auto |
1363 have "m mod 2^(nat ?l) < 2^(nat ?l)" by (rule pos_mod_bound) auto |
1364 hence mod_uneq: "real (m mod 2^(nat ?l)) \<le> 1 * 2^(nat ?l)" unfolding zmult_1 real_of_int_less_iff[symmetric] by auto |
1364 hence mod_uneq: "real (m mod 2^(nat ?l)) \<le> 1 * 2^(nat ?l)" unfolding mult_1 real_of_int_less_iff[symmetric] by auto |
1365 |
1365 |
1366 have "real m = real (2^(nat ?l) * (m div 2^(nat ?l)) + m mod 2^(nat ?l))" unfolding zmod_zdiv_equality[symmetric] .. |
1366 have "real m = real (2^(nat ?l) * (m div 2^(nat ?l)) + m mod 2^(nat ?l))" unfolding zmod_zdiv_equality[symmetric] .. |
1367 also have "\<dots> = real (m div 2^(nat ?l)) * 2^(nat ?l) + real (m mod 2^(nat ?l))" unfolding real_of_int_add by auto |
1367 also have "\<dots> = real (m div 2^(nat ?l)) * 2^(nat ?l) + real (m mod 2^(nat ?l))" unfolding real_of_int_add by auto |
1368 also have "\<dots> \<le> (real (m div 2^(nat ?l)) + 1) * 2^(nat ?l)" unfolding left_distrib using mod_uneq by auto |
1368 also have "\<dots> \<le> (real (m div 2^(nat ?l)) + 1) * 2^(nat ?l)" unfolding left_distrib using mod_uneq by auto |
1369 finally show ?thesis unfolding pow2_int[symmetric] using True by auto |
1369 finally show ?thesis unfolding pow2_int[symmetric] using True by auto |