1140 by (simp add: Suc3_eq_add_3) |
1140 by (simp add: Suc3_eq_add_3) |
1141 |
1141 |
1142 lemma Suc_mod_eq_add3_mod: "(Suc (Suc (Suc m))) mod n = (3+m) mod n" |
1142 lemma Suc_mod_eq_add3_mod: "(Suc (Suc (Suc m))) mod n = (3+m) mod n" |
1143 by (simp add: Suc3_eq_add_3) |
1143 by (simp add: Suc3_eq_add_3) |
1144 |
1144 |
1145 lemmas Suc_div_eq_add3_div_number_of = |
1145 lemmas Suc_div_eq_add3_div_number_of [simp] = Suc_div_eq_add3_div [of _ "number_of v"] for v |
1146 Suc_div_eq_add3_div [of _ "number_of v", standard] |
1146 lemmas Suc_mod_eq_add3_mod_number_of [simp] = Suc_mod_eq_add3_mod [of _ "number_of v"] for v |
1147 declare Suc_div_eq_add3_div_number_of [simp] |
|
1148 |
|
1149 lemmas Suc_mod_eq_add3_mod_number_of = |
|
1150 Suc_mod_eq_add3_mod [of _ "number_of v", standard] |
|
1151 declare Suc_mod_eq_add3_mod_number_of [simp] |
|
1152 |
1147 |
1153 |
1148 |
1154 lemma Suc_times_mod_eq: "1<k ==> Suc (k * m) mod k = 1" |
1149 lemma Suc_times_mod_eq: "1<k ==> Suc (k * m) mod k = 1" |
1155 apply (induct "m") |
1150 apply (induct "m") |
1156 apply (simp_all add: mod_Suc) |
1151 apply (simp_all add: mod_Suc) |
1157 done |
1152 done |
1158 |
1153 |
1159 declare Suc_times_mod_eq [of "number_of w", standard, simp] |
1154 declare Suc_times_mod_eq [of "number_of w", simp] for w |
1160 |
1155 |
1161 lemma [simp]: "n div k \<le> (Suc n) div k" |
1156 lemma [simp]: "n div k \<le> (Suc n) div k" |
1162 by (simp add: div_le_mono) |
1157 by (simp add: div_le_mono) |
1163 |
1158 |
1164 lemma Suc_n_div_2_gt_zero [simp]: "(0::nat) < n ==> 0 < (n + 1) div 2" |
1159 lemma Suc_n_div_2_gt_zero [simp]: "(0::nat) < n ==> 0 < (n + 1) div 2" |
1448 lemma pos_mod_conj : "(0::int) < b ==> 0 \<le> a mod b & a mod b < b" |
1443 lemma pos_mod_conj : "(0::int) < b ==> 0 \<le> a mod b & a mod b < b" |
1449 apply (cut_tac a = a and b = b in divmod_int_correct) |
1444 apply (cut_tac a = a and b = b in divmod_int_correct) |
1450 apply (auto simp add: divmod_int_rel_def mod_int_def) |
1445 apply (auto simp add: divmod_int_rel_def mod_int_def) |
1451 done |
1446 done |
1452 |
1447 |
1453 lemmas pos_mod_sign [simp] = pos_mod_conj [THEN conjunct1, standard] |
1448 lemmas pos_mod_sign [simp] = pos_mod_conj [THEN conjunct1] |
1454 and pos_mod_bound [simp] = pos_mod_conj [THEN conjunct2, standard] |
1449 and pos_mod_bound [simp] = pos_mod_conj [THEN conjunct2] |
1455 |
1450 |
1456 lemma neg_mod_conj : "b < (0::int) ==> a mod b \<le> 0 & b < a mod b" |
1451 lemma neg_mod_conj : "b < (0::int) ==> a mod b \<le> 0 & b < a mod b" |
1457 apply (cut_tac a = a and b = b in divmod_int_correct) |
1452 apply (cut_tac a = a and b = b in divmod_int_correct) |
1458 apply (auto simp add: divmod_int_rel_def div_int_def mod_int_def) |
1453 apply (auto simp add: divmod_int_rel_def div_int_def mod_int_def) |
1459 done |
1454 done |
1460 |
1455 |
1461 lemmas neg_mod_sign [simp] = neg_mod_conj [THEN conjunct1, standard] |
1456 lemmas neg_mod_sign [simp] = neg_mod_conj [THEN conjunct1] |
1462 and neg_mod_bound [simp] = neg_mod_conj [THEN conjunct2, standard] |
1457 and neg_mod_bound [simp] = neg_mod_conj [THEN conjunct2] |
1463 |
|
1464 |
1458 |
1465 |
1459 |
1466 subsubsection{*General Properties of div and mod*} |
1460 subsubsection{*General Properties of div and mod*} |
1467 |
1461 |
1468 lemma divmod_int_rel_div_mod: "b \<noteq> 0 ==> divmod_int_rel a b (a div b, a mod b)" |
1462 lemma divmod_int_rel_div_mod: "b \<noteq> 0 ==> divmod_int_rel a b (a div b, a mod b)" |
1726 {* K (divmod_proc @{thm int_div_pos_eq} @{thm int_div_neg_eq}) *} |
1720 {* K (divmod_proc @{thm int_div_pos_eq} @{thm int_div_neg_eq}) *} |
1727 |
1721 |
1728 simproc_setup binary_int_mod ("number_of m mod number_of n :: int") = |
1722 simproc_setup binary_int_mod ("number_of m mod number_of n :: int") = |
1729 {* K (divmod_proc @{thm int_mod_pos_eq} @{thm int_mod_neg_eq}) *} |
1723 {* K (divmod_proc @{thm int_mod_pos_eq} @{thm int_mod_neg_eq}) *} |
1730 |
1724 |
1731 lemmas posDivAlg_eqn_number_of [simp] = |
1725 lemmas posDivAlg_eqn_number_of [simp] = posDivAlg_eqn [of "number_of v" "number_of w"] for v w |
1732 posDivAlg_eqn [of "number_of v" "number_of w", standard] |
1726 lemmas negDivAlg_eqn_number_of [simp] = negDivAlg_eqn [of "number_of v" "number_of w"] for v w |
1733 |
|
1734 lemmas negDivAlg_eqn_number_of [simp] = |
|
1735 negDivAlg_eqn [of "number_of v" "number_of w", standard] |
|
1736 |
1727 |
1737 |
1728 |
1738 text{*Special-case simplification *} |
1729 text{*Special-case simplification *} |
1739 |
1730 |
1740 lemma zmod_minus1_right [simp]: "a mod (-1::int) = 0" |
1731 lemma zmod_minus1_right [simp]: "a mod (-1::int) = 0" |
1747 by (cut_tac a = a and b = "-1" in zmod_zdiv_equality, auto) |
1738 by (cut_tac a = a and b = "-1" in zmod_zdiv_equality, auto) |
1748 |
1739 |
1749 (** The last remaining special cases for constant arithmetic: |
1740 (** The last remaining special cases for constant arithmetic: |
1750 1 div z and 1 mod z **) |
1741 1 div z and 1 mod z **) |
1751 |
1742 |
1752 lemmas div_pos_pos_1_number_of [simp] = |
1743 lemmas div_pos_pos_1_number_of [simp] = div_pos_pos [OF zero_less_one, of "number_of w"] for w |
1753 div_pos_pos [OF zero_less_one, of "number_of w", standard] |
1744 lemmas div_pos_neg_1_number_of [simp] = div_pos_neg [OF zero_less_one, of "number_of w"] for w |
1754 |
1745 lemmas mod_pos_pos_1_number_of [simp] = mod_pos_pos [OF zero_less_one, of "number_of w"] for w |
1755 lemmas div_pos_neg_1_number_of [simp] = |
1746 lemmas mod_pos_neg_1_number_of [simp] = mod_pos_neg [OF zero_less_one, of "number_of w"] for w |
1756 div_pos_neg [OF zero_less_one, of "number_of w", standard] |
1747 lemmas posDivAlg_eqn_1_number_of [simp] = posDivAlg_eqn [of concl: 1 "number_of w"] for w |
1757 |
1748 lemmas negDivAlg_eqn_1_number_of [simp] = negDivAlg_eqn [of concl: 1 "number_of w"] for w |
1758 lemmas mod_pos_pos_1_number_of [simp] = |
|
1759 mod_pos_pos [OF zero_less_one, of "number_of w", standard] |
|
1760 |
|
1761 lemmas mod_pos_neg_1_number_of [simp] = |
|
1762 mod_pos_neg [OF zero_less_one, of "number_of w", standard] |
|
1763 |
|
1764 |
|
1765 lemmas posDivAlg_eqn_1_number_of [simp] = |
|
1766 posDivAlg_eqn [of concl: 1 "number_of w", standard] |
|
1767 |
|
1768 lemmas negDivAlg_eqn_1_number_of [simp] = |
|
1769 negDivAlg_eqn [of concl: 1 "number_of w", standard] |
|
1770 |
|
1771 |
1749 |
1772 |
1750 |
1773 subsubsection{*Monotonicity in the First Argument (Dividend)*} |
1751 subsubsection{*Monotonicity in the First Argument (Dividend)*} |
1774 |
1752 |
1775 lemma zdiv_mono1: "[| a \<le> a'; 0 < (b::int) |] ==> a div b \<le> a' div b" |
1753 lemma zdiv_mono1: "[| a \<le> a'; 0 < (b::int) |] ==> a div b \<le> a' div b" |
2067 done |
2045 done |
2068 |
2046 |
2069 text {* Enable (lin)arith to deal with @{const div} and @{const mod} |
2047 text {* Enable (lin)arith to deal with @{const div} and @{const mod} |
2070 when these are applied to some constant that is of the form |
2048 when these are applied to some constant that is of the form |
2071 @{term "number_of k"}: *} |
2049 @{term "number_of k"}: *} |
2072 declare split_zdiv [of _ _ "number_of k", standard, arith_split] |
2050 declare split_zdiv [of _ _ "number_of k", arith_split] for k |
2073 declare split_zmod [of _ _ "number_of k", standard, arith_split] |
2051 declare split_zmod [of _ _ "number_of k", arith_split] for k |
2074 |
2052 |
2075 |
2053 |
2076 subsubsection{*Speeding up the Division Algorithm with Shifting*} |
2054 subsubsection{*Speeding up the Division Algorithm with Shifting*} |
2077 |
2055 |
2078 text{*computing div by shifting *} |
2056 text{*computing div by shifting *} |
2255 |
2233 |
2256 |
2234 |
2257 subsubsection {* The Divides Relation *} |
2235 subsubsection {* The Divides Relation *} |
2258 |
2236 |
2259 lemmas zdvd_iff_zmod_eq_0_number_of [simp] = |
2237 lemmas zdvd_iff_zmod_eq_0_number_of [simp] = |
2260 dvd_eq_mod_eq_0 [of "number_of x::int" "number_of y::int", standard] |
2238 dvd_eq_mod_eq_0 [of "number_of x" "number_of y"] for x y :: int |
2261 |
2239 |
2262 lemma zdvd_zmod: "f dvd m ==> f dvd (n::int) ==> f dvd m mod n" |
2240 lemma zdvd_zmod: "f dvd m ==> f dvd (n::int) ==> f dvd m mod n" |
2263 by (rule dvd_mod) (* TODO: remove *) |
2241 by (rule dvd_mod) (* TODO: remove *) |
2264 |
2242 |
2265 lemma zdvd_zmod_imp_zdvd: "k dvd m mod n ==> k dvd n ==> k dvd (m::int)" |
2243 lemma zdvd_zmod_imp_zdvd: "k dvd m mod n ==> k dvd n ==> k dvd (m::int)" |
2454 "Suc 0 mod number_of v' = |
2432 "Suc 0 mod number_of v' = |
2455 (if neg (number_of v' :: int) then Suc 0 |
2433 (if neg (number_of v' :: int) then Suc 0 |
2456 else nat (1 mod number_of v'))" |
2434 else nat (1 mod number_of v'))" |
2457 by (simp del: nat_numeral_1_eq_1 add: numeral_1_eq_Suc_0 [symmetric]) |
2435 by (simp del: nat_numeral_1_eq_1 add: numeral_1_eq_Suc_0 [symmetric]) |
2458 |
2436 |
2459 lemmas dvd_eq_mod_eq_0_number_of = |
2437 lemmas dvd_eq_mod_eq_0_number_of [simp] = |
2460 dvd_eq_mod_eq_0 [of "number_of x" "number_of y", standard] |
2438 dvd_eq_mod_eq_0 [of "number_of x" "number_of y"] for x y |
2461 |
|
2462 declare dvd_eq_mod_eq_0_number_of [simp] |
|
2463 |
2439 |
2464 |
2440 |
2465 subsubsection {* Nitpick *} |
2441 subsubsection {* Nitpick *} |
2466 |
2442 |
2467 lemma zmod_zdiv_equality': |
2443 lemma zmod_zdiv_equality': |