855 qualified lemma compute_float_up[code]: "float_up p x = - float_down p (-x)" |
855 qualified lemma compute_float_up[code]: "float_up p x = - float_down p (-x)" |
856 by transfer (simp add: round_down_uminus_eq) |
856 by transfer (simp add: round_down_uminus_eq) |
857 |
857 |
858 end |
858 end |
859 |
859 |
860 |
860 definition floorlog :: "nat \<Rightarrow> nat \<Rightarrow> nat" |
861 subsection \<open>Compute bitlen of integers\<close> |
861 where "floorlog b a = (if a > 0 \<and> b > 1 then nat \<lfloor>log b a\<rfloor> + 1 else 0)" |
862 |
862 |
863 definition bitlen :: "int \<Rightarrow> int" |
863 lemma floorlog_nonneg: "0 \<le> floorlog b x" |
864 where "bitlen a = (if a > 0 then \<lfloor>log 2 a\<rfloor> + 1 else 0)" |
864 proof - |
865 |
865 have "-1 < log b (-x)" if "0 > x" "b > 1" |
866 lemma bitlen_nonneg: "0 \<le> bitlen x" |
|
867 proof - |
|
868 have "-1 < log 2 (-x)" if "0 > x" |
|
869 proof - |
866 proof - |
870 have "-1 = log 2 (inverse 2)" |
867 have "-1 = log b (inverse b)" using that |
871 by (subst log_inverse) simp_all |
868 by (subst log_inverse) simp_all |
872 also have "\<dots> < log 2 (-x)" |
869 also have "\<dots> < log b (-x)" |
873 using \<open>0 > x\<close> by auto |
870 using \<open>0 > x\<close> by auto |
874 finally show ?thesis . |
871 finally show ?thesis . |
875 qed |
872 qed |
876 then show ?thesis |
873 then show ?thesis |
877 unfolding bitlen_def by (auto intro!: add_nonneg_nonneg) |
874 unfolding floorlog_def by (auto intro!: add_nonneg_nonneg) |
878 qed |
875 qed |
|
876 |
|
877 lemma floorlog_bounds: |
|
878 assumes "x > 0" "b > 1" |
|
879 shows "b ^ (floorlog b x - 1) \<le> x \<and> x < b ^ (floorlog b x)" |
|
880 proof |
|
881 show "b ^ (floorlog b x - 1) \<le> x" |
|
882 proof - |
|
883 have "(b::real) ^ nat \<lfloor>log b (real_of_int x)\<rfloor> = b powr real_of_int \<lfloor>log b (real_of_int x)\<rfloor>" |
|
884 using powr_realpow[symmetric, of b "nat \<lfloor>log b (real_of_int x)\<rfloor>"] \<open>x > 0\<close> \<open>b > 1\<close> |
|
885 by simp |
|
886 also have "\<dots> \<le> b powr log b (real_of_int x)" |
|
887 using \<open>b > 1\<close> |
|
888 by simp |
|
889 also have "\<dots> = real_of_int x" |
|
890 using \<open>0 < x\<close> \<open>b > 1\<close> by simp |
|
891 finally have "b ^ nat \<lfloor>log b (real_of_int x)\<rfloor> \<le> real_of_int x" |
|
892 by simp |
|
893 then show ?thesis |
|
894 using \<open>0 < x\<close> \<open>b > 1\<close> of_nat_le_iff |
|
895 by (fastforce simp add: floorlog_def) |
|
896 qed |
|
897 show "x < b ^ (floorlog b x)" |
|
898 proof - |
|
899 have "x \<le> b powr (log b x)" |
|
900 using \<open>x > 0\<close> \<open>b > 1\<close> by simp |
|
901 also have "\<dots> < b powr (\<lfloor>log b x\<rfloor> + 1)" |
|
902 using assms |
|
903 by (intro powr_less_mono) auto |
|
904 also have "\<dots> = b ^ nat (\<lfloor>log b (real_of_int x)\<rfloor> + 1)" |
|
905 using assms |
|
906 by (simp add: powr_realpow[symmetric]) |
|
907 finally |
|
908 have "x < b ^ nat (\<lfloor>log (real b) (real_of_int (int x))\<rfloor> + 1)" |
|
909 by (rule of_nat_less_imp_less) |
|
910 then show ?thesis |
|
911 using \<open>x > 0\<close> \<open>b > 1\<close> |
|
912 by (simp add: floorlog_def nat_add_distrib) |
|
913 qed |
|
914 qed |
|
915 |
|
916 lemma floorlog_power[simp]: |
|
917 assumes "a > 0" "b > 1" |
|
918 shows "floorlog b (a * b ^ c) = floorlog b a + c" |
|
919 proof - |
|
920 have "\<lfloor>log (real b) (real a) + real c\<rfloor> = \<lfloor>log (real b) (real a)\<rfloor> + c" |
|
921 by arith |
|
922 then show ?thesis using assms |
|
923 by (auto simp: floorlog_def log_mult powr_realpow[symmetric] nat_add_distrib) |
|
924 qed |
|
925 |
|
926 lemma |
|
927 floor_log_add_eqI: |
|
928 fixes a::nat and b::nat and r::real |
|
929 assumes "b > 1" |
|
930 assumes "a \<ge> 1" "0 \<le> r" "r < 1" |
|
931 shows "\<lfloor>log b (a + r)\<rfloor> = \<lfloor>log b a\<rfloor>" |
|
932 proof (rule floor_eq2) |
|
933 have "log (real b) (real a) \<le> log (real b) (real a + r)" |
|
934 using assms by force |
|
935 then show "\<lfloor>log (real b) (real a)\<rfloor> \<le> log (real b) (real a + r)" |
|
936 by arith |
|
937 next |
|
938 define l::int where "l = int b ^ (nat \<lfloor>log b a\<rfloor> + 1)" |
|
939 have l_def_real: "l = b powr (\<lfloor>log b a\<rfloor> + 1)" |
|
940 using assms by (simp add: l_def powr_add powr_real_of_int) |
|
941 have "a < l" |
|
942 proof - |
|
943 have "a = b powr (log b a)" using assms by simp |
|
944 also have "\<dots> < b powr floor ((log b a) + 1)" |
|
945 using assms(1) by auto |
|
946 also have "\<dots> = l" |
|
947 using assms |
|
948 by (simp add: l_def powr_real_of_int powr_add) |
|
949 finally show ?thesis by simp |
|
950 qed |
|
951 then have "a + r < l" using assms by simp |
|
952 then have "log b (a + r) < log b l" |
|
953 using assms by simp |
|
954 also have "\<dots> = real_of_int \<lfloor>log b a\<rfloor> + 1" |
|
955 using assms by (simp add: l_def_real) |
|
956 finally show "log b (a + r) < real_of_int \<lfloor>log b a\<rfloor> + 1" . |
|
957 qed |
|
958 |
|
959 lemma |
|
960 divide_nat_diff_div_nat_less_one: |
|
961 fixes x b::nat shows "x / b - x div b < 1" |
|
962 by (metis One_nat_def add_diff_cancel_left' divide_1 divide_self_if floor_divide_of_nat_eq |
|
963 less_eq_real_def mod_div_trivial nat.simps(3) of_nat_eq_0_iff real_of_nat_div3 real_of_nat_div_aux) |
|
964 |
|
965 context |
|
966 begin |
|
967 |
|
968 qualified lemma compute_floorlog[code]: "floorlog b x = (if x > 0 \<and> b > 1 then floorlog b (x div b) + 1 else 0)" |
|
969 proof - |
|
970 { |
|
971 assume prems: "x > 0" "b > 1" "0 < x div b" |
|
972 have "\<lfloor>log (real b) (real x)\<rfloor> = \<lfloor>log (real b) (x / b * b)\<rfloor>" |
|
973 using prems by simp |
|
974 also have "\<dots> = \<lfloor>log b (x / b) + log b b\<rfloor>" |
|
975 using prems |
|
976 by (subst log_mult) auto |
|
977 also have "\<dots> = \<lfloor>log b (x / b)\<rfloor> + 1" using prems by simp |
|
978 also have "\<lfloor>log b (x / b)\<rfloor> = \<lfloor>log b (x div b + (x / b - x div b))\<rfloor>" |
|
979 by simp |
|
980 also have "\<dots> = \<lfloor>log b (x div b)\<rfloor>" |
|
981 using prems real_of_nat_div4 divide_nat_diff_div_nat_less_one |
|
982 by (intro floor_log_add_eqI) auto |
|
983 finally have ?thesis using prems by (simp add: floorlog_def nat_add_distrib) |
|
984 } then show ?thesis |
|
985 by (auto simp: floorlog_def div_eq_0_iff intro!: floor_eq2) |
|
986 qed |
|
987 |
|
988 end |
|
989 |
|
990 definition bitlen :: "int \<Rightarrow> int" where "bitlen a = floorlog 2 (nat a)" |
|
991 |
|
992 lemma bitlen_alt_def: "bitlen a = (if a > 0 then \<lfloor>log 2 a\<rfloor> + 1 else 0)" |
|
993 by (simp add: bitlen_def floorlog_def) |
|
994 |
|
995 lemma bitlen_nonneg: "0 \<le> bitlen x" |
|
996 using floorlog_nonneg by (simp add: bitlen_def) |
879 |
997 |
880 lemma bitlen_bounds: |
998 lemma bitlen_bounds: |
881 assumes "x > 0" |
999 assumes "x > 0" |
882 shows "2 ^ nat (bitlen x - 1) \<le> x \<and> x < 2 ^ nat (bitlen x)" |
1000 shows "2 ^ nat (bitlen x - 1) \<le> x \<and> x < 2 ^ nat (bitlen x)" |
883 proof |
1001 proof - |
884 show "2 ^ nat (bitlen x - 1) \<le> x" |
1002 from assms have "bitlen x \<ge> 1" by (auto simp: bitlen_alt_def) |
885 proof - |
1003 with assms floorlog_bounds[of "nat x" 2] show ?thesis |
886 have "(2::real) ^ nat \<lfloor>log 2 (real_of_int x)\<rfloor> = 2 powr real_of_int \<lfloor>log 2 (real_of_int x)\<rfloor>" |
1004 by (auto simp add: bitlen_def le_nat_iff nat_less_iff nat_diff_distrib) |
887 using powr_realpow[symmetric, of 2 "nat \<lfloor>log 2 (real_of_int x)\<rfloor>"] \<open>x > 0\<close> |
|
888 by simp |
|
889 also have "\<dots> \<le> 2 powr log 2 (real_of_int x)" |
|
890 by simp |
|
891 also have "\<dots> = real_of_int x" |
|
892 using \<open>0 < x\<close> by simp |
|
893 finally have "2 ^ nat \<lfloor>log 2 (real_of_int x)\<rfloor> \<le> real_of_int x" |
|
894 by simp |
|
895 then show ?thesis |
|
896 using \<open>0 < x\<close> by (simp add: bitlen_def) |
|
897 qed |
|
898 show "x < 2 ^ nat (bitlen x)" |
|
899 proof - |
|
900 have "x \<le> 2 powr (log 2 x)" |
|
901 using \<open>x > 0\<close> by simp |
|
902 also have "\<dots> < 2 ^ nat (\<lfloor>log 2 (real_of_int x)\<rfloor> + 1)" |
|
903 apply (simp add: powr_realpow[symmetric]) |
|
904 using \<open>x > 0\<close> apply simp |
|
905 done |
|
906 finally show ?thesis |
|
907 using \<open>x > 0\<close> by (simp add: bitlen_def ac_simps) |
|
908 qed |
|
909 qed |
1005 qed |
910 |
1006 |
911 lemma bitlen_pow2[simp]: |
1007 lemma bitlen_pow2[simp]: |
912 assumes "b > 0" |
1008 assumes "b > 0" |
913 shows "bitlen (b * 2 ^ c) = bitlen b + c" |
1009 shows "bitlen (b * 2 ^ c) = bitlen b + c" |
914 proof - |
1010 using assms |
915 from assms have "b * 2 ^ c > 0" |
1011 by (simp add: bitlen_def nat_mult_distrib nat_power_eq) |
916 by auto |
|
917 then show ?thesis |
|
918 using floor_add[of "log 2 b" c] assms |
|
919 apply (auto simp add: log_mult log_nat_power bitlen_def) |
|
920 by (metis add.right_neutral frac_lt_1 frac_of_int of_int_of_nat_eq) |
|
921 qed |
|
922 |
1012 |
923 lemma bitlen_Float: |
1013 lemma bitlen_Float: |
924 fixes m e |
1014 fixes m e |
925 defines "f \<equiv> Float m e" |
1015 defines "f \<equiv> Float m e" |
926 shows "bitlen (\<bar>mantissa f\<bar>) + exponent f = (if m = 0 then 0 else bitlen \<bar>m\<bar> + e)" |
1016 shows "bitlen (\<bar>mantissa f\<bar>) + exponent f = (if m = 0 then 0 else bitlen \<bar>m\<bar> + e)" |
927 proof (cases "m = 0") |
1017 proof (cases "m = 0") |
928 case True |
1018 case True |
929 then show ?thesis by (simp add: f_def bitlen_def Float_def) |
1019 then show ?thesis by (simp add: f_def bitlen_alt_def Float_def) |
930 next |
1020 next |
931 case False |
1021 case False |
932 then have "f \<noteq> float_of 0" |
1022 then have "f \<noteq> float_of 0" |
933 unfolding real_of_float_eq by (simp add: f_def) |
1023 unfolding real_of_float_eq by (simp add: f_def) |
934 then have "mantissa f \<noteq> 0" |
1024 then have "mantissa f \<noteq> 0" |
941 |
1031 |
942 context |
1032 context |
943 begin |
1033 begin |
944 |
1034 |
945 qualified lemma compute_bitlen[code]: "bitlen x = (if x > 0 then bitlen (x div 2) + 1 else 0)" |
1035 qualified lemma compute_bitlen[code]: "bitlen x = (if x > 0 then bitlen (x div 2) + 1 else 0)" |
946 proof - |
1036 unfolding bitlen_def |
947 { assume "2 \<le> x" |
1037 by (subst Float.compute_floorlog) (simp add: nat_div_distrib) |
948 then have "\<lfloor>log 2 (x div 2)\<rfloor> + 1 = \<lfloor>log 2 (x - x mod 2)\<rfloor>" |
|
949 by (simp add: log_mult zmod_zdiv_equality') |
|
950 also have "\<dots> = \<lfloor>log 2 (real_of_int x)\<rfloor>" |
|
951 proof (cases "x mod 2 = 0") |
|
952 case True |
|
953 then show ?thesis by simp |
|
954 next |
|
955 case False |
|
956 define n where "n = \<lfloor>log 2 (real_of_int x)\<rfloor>" |
|
957 then have "0 \<le> n" |
|
958 using \<open>2 \<le> x\<close> by simp |
|
959 from \<open>2 \<le> x\<close> False have "x mod 2 = 1" "\<not> 2 dvd x" |
|
960 by (auto simp add: dvd_eq_mod_eq_0) |
|
961 with \<open>2 \<le> x\<close> have "x \<noteq> 2 ^ nat n" |
|
962 by (cases "nat n") auto |
|
963 moreover |
|
964 { have "real_of_int (2^nat n :: int) = 2 powr (nat n)" |
|
965 by (simp add: powr_realpow) |
|
966 also have "\<dots> \<le> 2 powr (log 2 x)" |
|
967 using \<open>2 \<le> x\<close> by (simp add: n_def del: powr_log_cancel) |
|
968 finally have "2^nat n \<le> x" using \<open>2 \<le> x\<close> by simp } |
|
969 ultimately have "2^nat n \<le> x - 1" by simp |
|
970 then have "2^nat n \<le> real_of_int (x - 1)" |
|
971 using numeral_power_le_real_of_int_cancel_iff by blast |
|
972 { have "n = \<lfloor>log 2 (2^nat n)\<rfloor>" |
|
973 using \<open>0 \<le> n\<close> by (simp add: log_nat_power) |
|
974 also have "\<dots> \<le> \<lfloor>log 2 (x - 1)\<rfloor>" |
|
975 using \<open>2^nat n \<le> real_of_int (x - 1)\<close> \<open>0 \<le> n\<close> \<open>2 \<le> x\<close> by (auto intro: floor_mono) |
|
976 finally have "n \<le> \<lfloor>log 2 (x - 1)\<rfloor>" . } |
|
977 moreover have "\<lfloor>log 2 (x - 1)\<rfloor> \<le> n" |
|
978 using \<open>2 \<le> x\<close> by (auto simp add: n_def intro!: floor_mono) |
|
979 ultimately show "\<lfloor>log 2 (x - x mod 2)\<rfloor> = \<lfloor>log 2 x\<rfloor>" |
|
980 unfolding n_def \<open>x mod 2 = 1\<close> by auto |
|
981 qed |
|
982 finally have "\<lfloor>log 2 (x div 2)\<rfloor> + 1 = \<lfloor>log 2 x\<rfloor>" . } |
|
983 moreover |
|
984 { assume "x < 2" "0 < x" |
|
985 then have "x = 1" by simp |
|
986 then have "\<lfloor>log 2 (real_of_int x)\<rfloor> = 0" by simp } |
|
987 ultimately show ?thesis |
|
988 unfolding bitlen_def |
|
989 by (auto simp: pos_imp_zdiv_pos_iff not_le) |
|
990 qed |
|
991 |
1038 |
992 end |
1039 end |
993 |
1040 |
994 lemma float_gt1_scale: assumes "1 \<le> Float m e" |
1041 lemma float_gt1_scale: assumes "1 \<le> Float m e" |
995 shows "0 \<le> e + (bitlen m - 1)" |
1042 shows "0 \<le> e + (bitlen m - 1)" |