--- a/src/HOL/Data_Structures/RBT.thy Thu Mar 22 17:05:06 2018 +0100
+++ b/src/HOL/Data_Structures/RBT.thy Thu Mar 22 17:06:15 2018 +0100
@@ -19,8 +19,8 @@
"baliL t1 a t2 = B t1 a t2"
fun baliR :: "'a rbt \<Rightarrow> 'a \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
+"baliR t1 a1 (R t2 a2 (R t3 a3 t4)) = R (B t1 a1 t2) a2 (B t3 a3 t4)" |
"baliR t1 a1 (R (R t2 a2 t3) a3 t4) = R (B t1 a1 t2) a2 (B t3 a3 t4)" |
-"baliR t1 a1 (R t2 a2 (R t3 a3 t4)) = R (B t1 a1 t2) a2 (B t3 a3 t4)" |
"baliR t1 a t2 = B t1 a t2"
fun paint :: "color \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
--- a/src/HOL/Parity.thy Thu Mar 22 17:05:06 2018 +0100
+++ b/src/HOL/Parity.thy Thu Mar 22 17:06:15 2018 +0100
@@ -371,19 +371,23 @@
with division_segment_euclidean_size [of r]
have "of_nat (euclidean_size r) = r"
by simp
- then have "r div of_nat m = of_nat (euclidean_size r) div of_nat m"
+ have "a mod (of_nat m * of_nat n) div (of_nat m * of_nat n) = 0"
+ by simp
+ with remainder(6) have "r div (of_nat m * of_nat n) = 0"
by simp
- also have "\<dots> = of_nat (euclidean_size r div m)"
+ with \<open>of_nat (euclidean_size r) = r\<close>
+ have "of_nat (euclidean_size r) div (of_nat m * of_nat n) = 0"
+ by simp
+ then have "of_nat (euclidean_size r div (m * n)) = 0"
by (simp add: of_nat_div)
- finally have "r div of_nat m = of_nat (euclidean_size r div m)"
- .
- with remainder(1-3) have "r div of_nat m div of_nat n = 0"
- by (auto intro!: div_eqI [of _ "of_nat (euclidean_size r div m)"])
- (simp add: division_segment_mult euclidean_size_mult ac_simps less_mult_imp_div_less )
+ then have "of_nat (euclidean_size r div m div n) = 0"
+ by (simp add: div_mult2_eq)
+ with \<open>of_nat (euclidean_size r) = r\<close> have "r div of_nat m div of_nat n = 0"
+ by (simp add: of_nat_div)
with remainder(1)
have "q = (r div of_nat m + q * of_nat n * of_nat m div of_nat m) div of_nat n"
by simp
- with remainder(5-7) show ?thesis
+ with remainder(5) remainder(7) show ?thesis
using div_plus_div_distrib_dvd_right [of "of_nat m" "q * (of_nat m * of_nat n)" r]
by (simp add: ac_simps)
next
@@ -681,29 +685,29 @@
text \<open>The primary purpose of the following operations is
to avoid ad-hoc simplification of concrete expressions @{term "2 ^ n"}\<close>
-definition bit_push :: "nat \<Rightarrow> 'a \<Rightarrow> 'a"
- where bit_push_eq_mult: "bit_push n a = a * 2 ^ n"
+definition push_bit :: "nat \<Rightarrow> 'a \<Rightarrow> 'a"
+ where push_bit_eq_mult: "push_bit n a = a * 2 ^ n"
-definition bit_take :: "nat \<Rightarrow> 'a \<Rightarrow> 'a"
- where bit_take_eq_mod: "bit_take n a = a mod of_nat (2 ^ n)"
+definition take_bit :: "nat \<Rightarrow> 'a \<Rightarrow> 'a"
+ where take_bit_eq_mod: "take_bit n a = a mod of_nat (2 ^ n)"
-definition bit_drop :: "nat \<Rightarrow> 'a \<Rightarrow> 'a"
- where bit_drop_eq_div: "bit_drop n a = a div of_nat (2 ^ n)"
+definition drop_bit :: "nat \<Rightarrow> 'a \<Rightarrow> 'a"
+ where drop_bit_eq_div: "drop_bit n a = a div of_nat (2 ^ n)"
lemma bit_ident:
- "bit_push n (bit_drop n a) + bit_take n a = a"
- using div_mult_mod_eq by (simp add: bit_push_eq_mult bit_take_eq_mod bit_drop_eq_div)
+ "push_bit n (drop_bit n a) + take_bit n a = a"
+ using div_mult_mod_eq by (simp add: push_bit_eq_mult take_bit_eq_mod drop_bit_eq_div)
-lemma bit_take_bit_take [simp]:
- "bit_take n (bit_take n a) = bit_take n a"
- by (simp add: bit_take_eq_mod)
+lemma take_bit_take_bit [simp]:
+ "take_bit n (take_bit n a) = take_bit n a"
+ by (simp add: take_bit_eq_mod)
-lemma bit_take_0 [simp]:
- "bit_take 0 a = 0"
- by (simp add: bit_take_eq_mod)
+lemma take_bit_0 [simp]:
+ "take_bit 0 a = 0"
+ by (simp add: take_bit_eq_mod)
-lemma bit_take_Suc [simp]:
- "bit_take (Suc n) a = bit_take n (a div 2) * 2 + of_bool (odd a)"
+lemma take_bit_Suc [simp]:
+ "take_bit (Suc n) a = take_bit n (a div 2) * 2 + of_bool (odd a)"
proof -
have "1 + 2 * (a div 2) mod (2 * 2 ^ n) = (a div 2 * 2 + a mod 2) mod (2 * 2 ^ n)"
if "odd a"
@@ -712,99 +716,99 @@
also have "\<dots> = a mod (2 * 2 ^ n)"
by (simp only: div_mult_mod_eq)
finally show ?thesis
- by (simp add: bit_take_eq_mod algebra_simps mult_mod_right)
+ by (simp add: take_bit_eq_mod algebra_simps mult_mod_right)
qed
-lemma bit_take_of_0 [simp]:
- "bit_take n 0 = 0"
- by (simp add: bit_take_eq_mod)
+lemma take_bit_of_0 [simp]:
+ "take_bit n 0 = 0"
+ by (simp add: take_bit_eq_mod)
-lemma bit_take_plus:
- "bit_take n (bit_take n a + bit_take n b) = bit_take n (a + b)"
- by (simp add: bit_take_eq_mod mod_simps)
+lemma take_bit_plus:
+ "take_bit n (take_bit n a + take_bit n b) = take_bit n (a + b)"
+ by (simp add: take_bit_eq_mod mod_simps)
-lemma bit_take_of_1_eq_0_iff [simp]:
- "bit_take n 1 = 0 \<longleftrightarrow> n = 0"
- by (simp add: bit_take_eq_mod)
+lemma take_bit_of_1_eq_0_iff [simp]:
+ "take_bit n 1 = 0 \<longleftrightarrow> n = 0"
+ by (simp add: take_bit_eq_mod)
-lemma bit_push_eq_0_iff [simp]:
- "bit_push n a = 0 \<longleftrightarrow> a = 0"
- by (simp add: bit_push_eq_mult)
+lemma push_bit_eq_0_iff [simp]:
+ "push_bit n a = 0 \<longleftrightarrow> a = 0"
+ by (simp add: push_bit_eq_mult)
-lemma bit_drop_0 [simp]:
- "bit_drop 0 = id"
- by (simp add: fun_eq_iff bit_drop_eq_div)
+lemma drop_bit_0 [simp]:
+ "drop_bit 0 = id"
+ by (simp add: fun_eq_iff drop_bit_eq_div)
-lemma bit_drop_of_0 [simp]:
- "bit_drop n 0 = 0"
- by (simp add: bit_drop_eq_div)
+lemma drop_bit_of_0 [simp]:
+ "drop_bit n 0 = 0"
+ by (simp add: drop_bit_eq_div)
-lemma bit_drop_Suc [simp]:
- "bit_drop (Suc n) a = bit_drop n (a div 2)"
+lemma drop_bit_Suc [simp]:
+ "drop_bit (Suc n) a = drop_bit n (a div 2)"
proof (cases "even a")
case True
then obtain b where "a = 2 * b" ..
- moreover have "bit_drop (Suc n) (2 * b) = bit_drop n b"
- by (simp add: bit_drop_eq_div)
+ moreover have "drop_bit (Suc n) (2 * b) = drop_bit n b"
+ by (simp add: drop_bit_eq_div)
ultimately show ?thesis
by simp
next
case False
then obtain b where "a = 2 * b + 1" ..
- moreover have "bit_drop (Suc n) (2 * b + 1) = bit_drop n b"
+ moreover have "drop_bit (Suc n) (2 * b + 1) = drop_bit n b"
using div_mult2_eq' [of "1 + b * 2" 2 "2 ^ n"]
- by (auto simp add: bit_drop_eq_div ac_simps)
+ by (auto simp add: drop_bit_eq_div ac_simps)
ultimately show ?thesis
by simp
qed
-lemma bit_drop_half:
- "bit_drop n (a div 2) = bit_drop n a div 2"
+lemma drop_bit_half:
+ "drop_bit n (a div 2) = drop_bit n a div 2"
by (induction n arbitrary: a) simp_all
-lemma bit_drop_of_bool [simp]:
- "bit_drop n (of_bool d) = of_bool (n = 0 \<and> d)"
+lemma drop_bit_of_bool [simp]:
+ "drop_bit n (of_bool d) = of_bool (n = 0 \<and> d)"
by (cases n) simp_all
-lemma even_bit_take_eq [simp]:
- "even (bit_take n a) \<longleftrightarrow> n = 0 \<or> even a"
- by (cases n) (simp_all add: bit_take_eq_mod dvd_mod_iff)
+lemma even_take_bit_eq [simp]:
+ "even (take_bit n a) \<longleftrightarrow> n = 0 \<or> even a"
+ by (cases n) (simp_all add: take_bit_eq_mod dvd_mod_iff)
-lemma bit_push_0_id [simp]:
- "bit_push 0 = id"
- by (simp add: fun_eq_iff bit_push_eq_mult)
+lemma push_bit_0_id [simp]:
+ "push_bit 0 = id"
+ by (simp add: fun_eq_iff push_bit_eq_mult)
-lemma bit_push_of_0 [simp]:
- "bit_push n 0 = 0"
- by (simp add: bit_push_eq_mult)
+lemma push_bit_of_0 [simp]:
+ "push_bit n 0 = 0"
+ by (simp add: push_bit_eq_mult)
-lemma bit_push_of_1:
- "bit_push n 1 = 2 ^ n"
- by (simp add: bit_push_eq_mult)
+lemma push_bit_of_1:
+ "push_bit n 1 = 2 ^ n"
+ by (simp add: push_bit_eq_mult)
-lemma bit_push_Suc [simp]:
- "bit_push (Suc n) a = bit_push n (a * 2)"
- by (simp add: bit_push_eq_mult ac_simps)
+lemma push_bit_Suc [simp]:
+ "push_bit (Suc n) a = push_bit n (a * 2)"
+ by (simp add: push_bit_eq_mult ac_simps)
-lemma bit_push_double:
- "bit_push n (a * 2) = bit_push n a * 2"
- by (simp add: bit_push_eq_mult ac_simps)
+lemma push_bit_double:
+ "push_bit n (a * 2) = push_bit n a * 2"
+ by (simp add: push_bit_eq_mult ac_simps)
-lemma bit_drop_bit_take [simp]:
- "bit_drop n (bit_take n a) = 0"
- by (simp add: bit_drop_eq_div bit_take_eq_mod)
+lemma drop_bit_take_bit [simp]:
+ "drop_bit n (take_bit n a) = 0"
+ by (simp add: drop_bit_eq_div take_bit_eq_mod)
-lemma bit_take_bit_drop_commute:
- "bit_drop m (bit_take n a) = bit_take (n - m) (bit_drop m a)"
+lemma take_bit_drop_bit_commute:
+ "drop_bit m (take_bit n a) = take_bit (n - m) (drop_bit m a)"
for m n :: nat
proof (cases "n \<ge> m")
case True
moreover define q where "q = n - m"
ultimately have "n - m = q" and "n = m + q"
by simp_all
- moreover have "bit_drop m (bit_take (m + q) a) = bit_take q (bit_drop m a)"
+ moreover have "drop_bit m (take_bit (m + q) a) = take_bit q (drop_bit m a)"
using mod_mult2_eq' [of a "2 ^ m" "2 ^ q"]
- by (simp add: bit_drop_eq_div bit_take_eq_mod power_add)
+ by (simp add: drop_bit_eq_div take_bit_eq_mod power_add)
ultimately show ?thesis
by simp
next
@@ -812,9 +816,9 @@
moreover define q where "q = m - n"
ultimately have "m - n = q" and "m = n + q"
by simp_all
- moreover have "bit_drop (n + q) (bit_take n a) = 0"
+ moreover have "drop_bit (n + q) (take_bit n a) = 0"
using div_mult2_eq' [of "a mod 2 ^ n" "2 ^ n" "2 ^ q"]
- by (simp add: bit_drop_eq_div bit_take_eq_mod power_add div_mult2_eq)
+ by (simp add: drop_bit_eq_div take_bit_eq_mod power_add div_mult2_eq)
ultimately show ?thesis
by simp
qed
--- a/src/HOL/ROOT Thu Mar 22 17:05:06 2018 +0100
+++ b/src/HOL/ROOT Thu Mar 22 17:06:15 2018 +0100
@@ -527,6 +527,7 @@
Ballot
BinEx
Birthday_Paradox
+ Bit_Lists
Bubblesort
CTL
Cartouche_Examples
--- a/src/HOL/Set_Interval.thy Thu Mar 22 17:05:06 2018 +0100
+++ b/src/HOL/Set_Interval.thy Thu Mar 22 17:06:15 2018 +0100
@@ -1929,8 +1929,8 @@
lemma sum_diff_distrib: "\<forall>x. Q x \<le> P x \<Longrightarrow> (\<Sum>x<n. P x) - (\<Sum>x<n. Q x) = (\<Sum>x<n. P x - Q x :: nat)"
by (subst sum_subtractf_nat) auto
-lemma bit_take_sum_nat:
- "bit_take n m = (\<Sum>k = 0..<n. bit_push k (of_bool (odd (bit_drop k m))))"
+lemma take_bit_sum_nat:
+ "take_bit n m = (\<Sum>k = 0..<n. push_bit k (of_bool (odd (drop_bit k m))))"
for n m :: nat
proof (induction n arbitrary: m)
case 0
@@ -1938,12 +1938,12 @@
by simp
next
case (Suc n)
- have "(\<Sum>k = 0..<Suc n. bit_push k (of_bool (odd (bit_drop k m)))) =
- of_bool (odd m) + (\<Sum>k = Suc 0..<Suc n. bit_push k (of_bool (odd (bit_drop k m))))"
+ have "(\<Sum>k = 0..<Suc n. push_bit k (of_bool (odd (drop_bit k m)))) =
+ of_bool (odd m) + (\<Sum>k = Suc 0..<Suc n. push_bit k (of_bool (odd (drop_bit k m))))"
by (simp add: sum_head_upt_Suc ac_simps)
- also have "(\<Sum>k = Suc 0..<Suc n. bit_push k (of_bool (odd (bit_drop k m))))
- = (\<Sum>k = 0..<n. bit_push k (of_bool (odd (bit_drop k (m div 2))))) * (2::nat)"
- by (simp only: sum.atLeast_Suc_lessThan_Suc_shift) (simp add: sum_distrib_right bit_push_double)
+ also have "(\<Sum>k = Suc 0..<Suc n. push_bit k (of_bool (odd (drop_bit k m))))
+ = (\<Sum>k = 0..<n. push_bit k (of_bool (odd (drop_bit k (m div 2))))) * (2::nat)"
+ by (simp only: sum.atLeast_Suc_lessThan_Suc_shift) (simp add: sum_distrib_right push_bit_double)
finally show ?case
using Suc [of "m div 2"] by simp
qed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/HOL/ex/Bit_Lists.thy Thu Mar 22 17:06:15 2018 +0100
@@ -0,0 +1,169 @@
+(* Author: Florian Haftmann, TUM
+*)
+
+section \<open>Proof of concept for algebraically founded lists of bits\<close>
+
+theory Bit_Lists
+ imports Main
+begin
+
+context comm_semiring_1
+begin
+
+primrec of_unsigned :: "bool list \<Rightarrow> 'a"
+ where "of_unsigned [] = 0"
+ | "of_unsigned (b # bs) = of_bool b + 2 * of_unsigned bs"
+
+end
+
+context comm_ring_1
+begin
+
+definition of_signed :: "bool list \<Rightarrow> 'a"
+ where "of_signed bs = (if bs = [] then 0 else if last bs
+ then - (of_unsigned (map Not bs) + 1) else of_unsigned bs)"
+
+end
+
+class semiring_bits = semiring_parity +
+ assumes half_measure: "a div 2 \<noteq> a \<Longrightarrow> euclidean_size (a div 2) < euclidean_size a"
+ \<comment> \<open>It is not clear whether this could be derived from already existing assumptions.\<close>
+begin
+
+function bits_of :: "'a \<Rightarrow> bool list"
+ where "bits_of a = odd a # (let b = a div 2 in if a = b then [] else bits_of b)"
+ by auto
+
+termination
+ by (relation "measure euclidean_size") (auto intro: half_measure)
+
+lemma bits_of_not_empty [simp]:
+ "bits_of a \<noteq> []"
+ by (induction a rule: bits_of.induct) simp_all
+
+lemma bits_of_0 [simp]:
+ "bits_of 0 = [False]"
+ by simp
+
+lemma bits_of_1 [simp]:
+ "bits_of 1 = [True, False]"
+ by simp
+
+lemma bits_of_double [simp]:
+ "bits_of (a * 2) = False # (if a = 0 then [] else bits_of a)"
+ by simp (simp add: mult_2_right)
+
+lemma bits_of_add_1_double [simp]:
+ "bits_of (1 + a * 2) = True # (if a + 1 = 0 then [] else bits_of a)"
+ by simp (simp add: mult_2_right algebra_simps)
+
+declare bits_of.simps [simp del]
+
+lemma not_last_bits_of_nat [simp]:
+ "\<not> last (bits_of (of_nat n))"
+ by (induction n rule: parity_induct)
+ (use of_nat_neq_0 in \<open>simp_all add: algebra_simps\<close>)
+
+lemma of_unsigned_bits_of_nat:
+ "of_unsigned (bits_of (of_nat n)) = of_nat n"
+ by (induction n rule: parity_induct)
+ (use of_nat_neq_0 in \<open>simp_all add: algebra_simps\<close>)
+
+end
+
+instance nat :: semiring_bits
+ by standard simp
+
+lemma bits_of_Suc_double [simp]:
+ "bits_of (Suc (n * 2)) = True # bits_of n"
+ using bits_of_add_1_double [of n] by simp
+
+lemma of_unsigned_bits_of:
+ "of_unsigned (bits_of n) = n" for n :: nat
+ using of_unsigned_bits_of_nat [of n, where ?'a = nat] by simp
+
+class ring_bits = ring_parity + semiring_bits
+begin
+
+lemma bits_of_minus_1 [simp]:
+ "bits_of (- 1) = [True]"
+ using bits_of.simps [of "- 1"] by simp
+
+lemma bits_of_double [simp]:
+ "bits_of (- (a * 2)) = False # (if a = 0 then [] else bits_of (- a))"
+ using bits_of.simps [of "- (a * 2)"] nonzero_mult_div_cancel_right [of 2 "- a"]
+ by simp (simp add: mult_2_right)
+
+lemma bits_of_minus_1_diff_double [simp]:
+ "bits_of (- 1 - a * 2) = True # (if a = 0 then [] else bits_of (- 1 - a))"
+proof -
+ have [simp]: "- 1 - a = - a - 1"
+ by (simp add: algebra_simps)
+ show ?thesis
+ using bits_of.simps [of "- 1 - a * 2"] div_mult_self1 [of 2 "- 1" "- a"]
+ by simp (simp add: mult_2_right algebra_simps)
+qed
+
+lemma last_bits_of_neg_of_nat [simp]:
+ "last (bits_of (- 1 - of_nat n))"
+proof (induction n rule: parity_induct)
+ case zero
+ then show ?case
+ by simp
+next
+ case (even n)
+ then show ?case
+ by (simp add: algebra_simps)
+next
+ case (odd n)
+ then have "last (bits_of ((- 1 - of_nat n) * 2))"
+ by auto
+ also have "(- 1 - of_nat n) * 2 = - 1 - (1 + 2 * of_nat n)"
+ by (simp add: algebra_simps)
+ finally show ?case
+ by simp
+qed
+
+lemma of_signed_bits_of_nat:
+ "of_signed (bits_of (of_nat n)) = of_nat n"
+ by (simp add: of_signed_def of_unsigned_bits_of_nat)
+
+lemma of_signed_bits_neg_of_nat:
+ "of_signed (bits_of (- 1 - of_nat n)) = - 1 - of_nat n"
+proof -
+ have "of_unsigned (map Not (bits_of (- 1 - of_nat n))) = of_nat n"
+ proof (induction n rule: parity_induct)
+ case zero
+ then show ?case
+ by simp
+ next
+ case (even n)
+ then show ?case
+ by (simp add: algebra_simps)
+ next
+ case (odd n)
+ have *: "- 1 - (1 + of_nat n * 2) = - 2 - of_nat n * 2"
+ by (simp add: algebra_simps) (metis add_assoc one_add_one)
+ from odd show ?case
+ using bits_of_double [of "of_nat (Suc n)"] of_nat_neq_0
+ by (simp add: algebra_simps *)
+ qed
+ then show ?thesis
+ by (simp add: of_signed_def algebra_simps)
+qed
+
+lemma of_signed_bits_of_int:
+ "of_signed (bits_of (of_int k)) = of_int k"
+ by (cases k rule: int_cases)
+ (simp_all add: of_signed_bits_of_nat of_signed_bits_neg_of_nat)
+
+end
+
+instance int :: ring_bits
+ by standard auto
+
+lemma of_signed_bits_of:
+ "of_signed (bits_of k) = k" for k :: int
+ using of_signed_bits_of_int [of k, where ?'a = int] by simp
+
+end
--- a/src/HOL/ex/Word_Type.thy Thu Mar 22 17:05:06 2018 +0100
+++ b/src/HOL/ex/Word_Type.thy Thu Mar 22 17:06:15 2018 +0100
@@ -9,32 +9,32 @@
"HOL-Library.Type_Length"
begin
-lemma bit_take_uminus:
+lemma take_bit_uminus:
fixes k :: int
- shows "bit_take n (- (bit_take n k)) = bit_take n (- k)"
- by (simp add: bit_take_eq_mod mod_minus_eq)
+ shows "take_bit n (- (take_bit n k)) = take_bit n (- k)"
+ by (simp add: take_bit_eq_mod mod_minus_eq)
-lemma bit_take_minus:
+lemma take_bit_minus:
fixes k l :: int
- shows "bit_take n (bit_take n k - bit_take n l) = bit_take n (k - l)"
- by (simp add: bit_take_eq_mod mod_diff_eq)
+ shows "take_bit n (take_bit n k - take_bit n l) = take_bit n (k - l)"
+ by (simp add: take_bit_eq_mod mod_diff_eq)
-lemma bit_take_nonnegative [simp]:
+lemma take_bit_nonnegative [simp]:
fixes k :: int
- shows "bit_take n k \<ge> 0"
- by (simp add: bit_take_eq_mod)
+ shows "take_bit n k \<ge> 0"
+ by (simp add: take_bit_eq_mod)
-definition signed_bit_take :: "nat \<Rightarrow> int \<Rightarrow> int"
- where signed_bit_take_eq_bit_take:
- "signed_bit_take n k = bit_take (Suc n) (k + 2 ^ n) - 2 ^ n"
+definition signed_take_bit :: "nat \<Rightarrow> int \<Rightarrow> int"
+ where signed_take_bit_eq_take_bit:
+ "signed_take_bit n k = take_bit (Suc n) (k + 2 ^ n) - 2 ^ n"
-lemma signed_bit_take_eq_bit_take':
+lemma signed_take_bit_eq_take_bit':
assumes "n > 0"
- shows "signed_bit_take (n - Suc 0) k = bit_take n (k + 2 ^ (n - 1)) - 2 ^ (n - 1)"
- using assms by (simp add: signed_bit_take_eq_bit_take)
+ shows "signed_take_bit (n - Suc 0) k = take_bit n (k + 2 ^ (n - 1)) - 2 ^ (n - 1)"
+ using assms by (simp add: signed_take_bit_eq_take_bit)
-lemma signed_bit_take_0 [simp]:
- "signed_bit_take 0 k = - (k mod 2)"
+lemma signed_take_bit_0 [simp]:
+ "signed_take_bit 0 k = - (k mod 2)"
proof (cases "even k")
case True
then have "odd (k + 1)"
@@ -42,54 +42,54 @@
then have "(k + 1) mod 2 = 1"
by (simp add: even_iff_mod_2_eq_zero)
with True show ?thesis
- by (simp add: signed_bit_take_eq_bit_take)
+ by (simp add: signed_take_bit_eq_take_bit)
next
case False
then show ?thesis
- by (simp add: signed_bit_take_eq_bit_take odd_iff_mod_2_eq_one)
+ by (simp add: signed_take_bit_eq_take_bit odd_iff_mod_2_eq_one)
qed
-lemma signed_bit_take_Suc [simp]:
- "signed_bit_take (Suc n) k = signed_bit_take n (k div 2) * 2 + k mod 2"
- by (simp add: odd_iff_mod_2_eq_one signed_bit_take_eq_bit_take algebra_simps)
+lemma signed_take_bit_Suc [simp]:
+ "signed_take_bit (Suc n) k = signed_take_bit n (k div 2) * 2 + k mod 2"
+ by (simp add: odd_iff_mod_2_eq_one signed_take_bit_eq_take_bit algebra_simps)
-lemma signed_bit_take_of_0 [simp]:
- "signed_bit_take n 0 = 0"
- by (simp add: signed_bit_take_eq_bit_take bit_take_eq_mod)
+lemma signed_take_bit_of_0 [simp]:
+ "signed_take_bit n 0 = 0"
+ by (simp add: signed_take_bit_eq_take_bit take_bit_eq_mod)
-lemma signed_bit_take_of_minus_1 [simp]:
- "signed_bit_take n (- 1) = - 1"
+lemma signed_take_bit_of_minus_1 [simp]:
+ "signed_take_bit n (- 1) = - 1"
by (induct n) simp_all
-lemma signed_bit_take_eq_iff_bit_take_eq:
+lemma signed_take_bit_eq_iff_take_bit_eq:
assumes "n > 0"
- shows "signed_bit_take (n - Suc 0) k = signed_bit_take (n - Suc 0) l \<longleftrightarrow> bit_take n k = bit_take n l" (is "?P \<longleftrightarrow> ?Q")
+ shows "signed_take_bit (n - Suc 0) k = signed_take_bit (n - Suc 0) l \<longleftrightarrow> take_bit n k = take_bit n l" (is "?P \<longleftrightarrow> ?Q")
proof -
from assms obtain m where m: "n = Suc m"
by (cases n) auto
show ?thesis
proof
assume ?Q
- have "bit_take (Suc m) (k + 2 ^ m) =
- bit_take (Suc m) (bit_take (Suc m) k + bit_take (Suc m) (2 ^ m))"
- by (simp only: bit_take_plus)
+ have "take_bit (Suc m) (k + 2 ^ m) =
+ take_bit (Suc m) (take_bit (Suc m) k + take_bit (Suc m) (2 ^ m))"
+ by (simp only: take_bit_plus)
also have "\<dots> =
- bit_take (Suc m) (bit_take (Suc m) l + bit_take (Suc m) (2 ^ m))"
+ take_bit (Suc m) (take_bit (Suc m) l + take_bit (Suc m) (2 ^ m))"
by (simp only: \<open>?Q\<close> m [symmetric])
- also have "\<dots> = bit_take (Suc m) (l + 2 ^ m)"
- by (simp only: bit_take_plus)
+ also have "\<dots> = take_bit (Suc m) (l + 2 ^ m)"
+ by (simp only: take_bit_plus)
finally show ?P
- by (simp only: signed_bit_take_eq_bit_take m) simp
+ by (simp only: signed_take_bit_eq_take_bit m) simp
next
assume ?P
with assms have "(k + 2 ^ (n - Suc 0)) mod 2 ^ n = (l + 2 ^ (n - Suc 0)) mod 2 ^ n"
- by (simp add: signed_bit_take_eq_bit_take' bit_take_eq_mod)
+ by (simp add: signed_take_bit_eq_take_bit' take_bit_eq_mod)
then have "(i + (k + 2 ^ (n - Suc 0))) mod 2 ^ n = (i + (l + 2 ^ (n - Suc 0))) mod 2 ^ n" for i
by (metis mod_add_eq)
then have "k mod 2 ^ n = l mod 2 ^ n"
by (metis add_diff_cancel_right' uminus_add_conv_diff)
then show ?Q
- by (simp add: bit_take_eq_mod)
+ by (simp add: take_bit_eq_mod)
qed
qed
@@ -98,7 +98,7 @@
subsubsection \<open>Basic properties\<close>
-quotient_type (overloaded) 'a word = int / "\<lambda>k l. bit_take LENGTH('a) k = bit_take LENGTH('a::len0) l"
+quotient_type (overloaded) 'a word = int / "\<lambda>k l. take_bit LENGTH('a) k = take_bit LENGTH('a::len0) l"
by (auto intro!: equivpI reflpI sympI transpI)
instantiation word :: (len0) "{semiring_numeral, comm_semiring_0, comm_ring}"
@@ -114,19 +114,19 @@
lift_definition plus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
is plus
- by (subst bit_take_plus [symmetric]) (simp add: bit_take_plus)
+ by (subst take_bit_plus [symmetric]) (simp add: take_bit_plus)
lift_definition uminus_word :: "'a word \<Rightarrow> 'a word"
is uminus
- by (subst bit_take_uminus [symmetric]) (simp add: bit_take_uminus)
+ by (subst take_bit_uminus [symmetric]) (simp add: take_bit_uminus)
lift_definition minus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
is minus
- by (subst bit_take_minus [symmetric]) (simp add: bit_take_minus)
+ by (subst take_bit_minus [symmetric]) (simp add: take_bit_minus)
lift_definition times_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
is times
- by (auto simp add: bit_take_eq_mod intro: mod_mult_cong)
+ by (auto simp add: take_bit_eq_mod intro: mod_mult_cong)
instance
by standard (transfer; simp add: algebra_simps)+
@@ -159,7 +159,7 @@
begin
lift_definition unsigned :: "'b::len0 word \<Rightarrow> 'a"
- is "of_nat \<circ> nat \<circ> bit_take LENGTH('b)"
+ is "of_nat \<circ> nat \<circ> take_bit LENGTH('b)"
by simp
lemma unsigned_0 [simp]:
@@ -181,8 +181,8 @@
begin
lift_definition signed :: "'b::len word \<Rightarrow> 'a"
- is "of_int \<circ> signed_bit_take (LENGTH('b) - 1)"
- by (simp add: signed_bit_take_eq_iff_bit_take_eq [symmetric])
+ is "of_int \<circ> signed_take_bit (LENGTH('b) - 1)"
+ by (simp add: signed_take_bit_eq_iff_take_bit_eq [symmetric])
lemma signed_0 [simp]:
"signed 0 = 0"
@@ -191,8 +191,8 @@
end
lemma unsigned_of_nat [simp]:
- "unsigned (of_nat n :: 'a word) = bit_take LENGTH('a::len) n"
- by transfer (simp add: nat_eq_iff bit_take_eq_mod zmod_int)
+ "unsigned (of_nat n :: 'a word) = take_bit LENGTH('a::len) n"
+ by transfer (simp add: nat_eq_iff take_bit_eq_mod zmod_int)
lemma of_nat_unsigned [simp]:
"of_nat (unsigned a) = a"
@@ -207,17 +207,17 @@
lemma word_eq_iff_signed:
"a = b \<longleftrightarrow> signed a = signed b"
- by safe (transfer; auto simp add: signed_bit_take_eq_iff_bit_take_eq)
+ by safe (transfer; auto simp add: signed_take_bit_eq_iff_take_bit_eq)
end
lemma signed_of_int [simp]:
- "signed (of_int k :: 'a word) = signed_bit_take (LENGTH('a::len) - 1) k"
+ "signed (of_int k :: 'a word) = signed_take_bit (LENGTH('a::len) - 1) k"
by transfer simp
lemma of_int_signed [simp]:
"of_int (signed a) = a"
- by transfer (simp add: signed_bit_take_eq_bit_take bit_take_eq_mod mod_simps)
+ by transfer (simp add: signed_take_bit_eq_take_bit take_bit_eq_mod mod_simps)
subsubsection \<open>Properties\<close>
@@ -229,11 +229,11 @@
begin
lift_definition divide_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is "\<lambda>a b. bit_take LENGTH('a) a div bit_take LENGTH('a) b"
+ is "\<lambda>a b. take_bit LENGTH('a) a div take_bit LENGTH('a) b"
by simp
lift_definition modulo_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is "\<lambda>a b. bit_take LENGTH('a) a mod bit_take LENGTH('a) b"
+ is "\<lambda>a b. take_bit LENGTH('a) a mod take_bit LENGTH('a) b"
by simp
instance ..
@@ -247,11 +247,11 @@
begin
lift_definition less_eq_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
- is "\<lambda>a b. bit_take LENGTH('a) a \<le> bit_take LENGTH('a) b"
+ is "\<lambda>a b. take_bit LENGTH('a) a \<le> take_bit LENGTH('a) b"
by simp
lift_definition less_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
- is "\<lambda>a b. bit_take LENGTH('a) a < bit_take LENGTH('a) b"
+ is "\<lambda>a b. take_bit LENGTH('a) a < take_bit LENGTH('a) b"
by simp
instance
@@ -268,7 +268,7 @@
lemma word_less_iff_unsigned:
"a < b \<longleftrightarrow> unsigned a < unsigned b"
- by (transfer fixing: less) (auto dest: preorder_class.le_less_trans [OF bit_take_nonnegative])
+ by (transfer fixing: less) (auto dest: preorder_class.le_less_trans [OF take_bit_nonnegative])
end