equal
deleted
inserted
replaced
99 apply (subgoal_tac "0 < b * (1 + q - q') ") |
99 apply (subgoal_tac "0 < b * (1 + q - q') ") |
100 apply (erule_tac [2] order_le_less_trans) |
100 apply (erule_tac [2] order_le_less_trans) |
101 prefer 2 apply (simp add: zdiff_zmult_distrib2 zadd_zmult_distrib2) |
101 prefer 2 apply (simp add: zdiff_zmult_distrib2 zadd_zmult_distrib2) |
102 apply (subgoal_tac "b * q' < b * (1 + q) ") |
102 apply (subgoal_tac "b * q' < b * (1 + q) ") |
103 prefer 2 apply (simp add: zdiff_zmult_distrib2 zadd_zmult_distrib2) |
103 prefer 2 apply (simp add: zdiff_zmult_distrib2 zadd_zmult_distrib2) |
104 apply (simp add: zmult_zless_cancel1) |
104 apply (simp add: mult_less_cancel_left) |
105 done |
105 done |
106 |
106 |
107 lemma unique_quotient_lemma_neg: |
107 lemma unique_quotient_lemma_neg: |
108 "[| b*q' + r' \<le> b*q + r; r \<le> 0; b < 0; b < r' |] |
108 "[| b*q' + r' \<le> b*q + r; r \<le> 0; b < 0; b < r' |] |
109 ==> q \<le> (q'::int)" |
109 ==> q \<le> (q'::int)" |
524 "[| b*q + r = b'*q' + r'; 0 \<le> b'*q' + r'; |
524 "[| b*q + r = b'*q' + r'; 0 \<le> b'*q' + r'; |
525 r' < b'; 0 \<le> r; 0 < b'; b' \<le> b |] |
525 r' < b'; 0 \<le> r; 0 < b'; b' \<le> b |] |
526 ==> q \<le> (q'::int)" |
526 ==> q \<le> (q'::int)" |
527 apply (frule q_pos_lemma, assumption+) |
527 apply (frule q_pos_lemma, assumption+) |
528 apply (subgoal_tac "b*q < b* (q' + 1) ") |
528 apply (subgoal_tac "b*q < b* (q' + 1) ") |
529 apply (simp add: zmult_zless_cancel1) |
529 apply (simp add: mult_less_cancel_left) |
530 apply (subgoal_tac "b*q = r' - r + b'*q'") |
530 apply (subgoal_tac "b*q = r' - r + b'*q'") |
531 prefer 2 apply simp |
531 prefer 2 apply simp |
532 apply (simp (no_asm_simp) add: zadd_zmult_distrib2) |
532 apply (simp (no_asm_simp) add: zadd_zmult_distrib2) |
533 apply (subst zadd_commute, rule zadd_zless_mono, arith) |
533 apply (subst zadd_commute, rule zadd_zless_mono, arith) |
534 apply (rule mult_right_mono, auto) |
534 apply (rule mult_right_mono, auto) |
556 "[| b*q + r = b'*q' + r'; b'*q' + r' < 0; |
556 "[| b*q + r = b'*q' + r'; b'*q' + r' < 0; |
557 r < b; 0 \<le> r'; 0 < b'; b' \<le> b |] |
557 r < b; 0 \<le> r'; 0 < b'; b' \<le> b |] |
558 ==> q' \<le> (q::int)" |
558 ==> q' \<le> (q::int)" |
559 apply (frule q_neg_lemma, assumption+) |
559 apply (frule q_neg_lemma, assumption+) |
560 apply (subgoal_tac "b*q' < b* (q + 1) ") |
560 apply (subgoal_tac "b*q' < b* (q + 1) ") |
561 apply (simp add: zmult_zless_cancel1) |
561 apply (simp add: mult_less_cancel_left) |
562 apply (simp add: zadd_zmult_distrib2) |
562 apply (simp add: zadd_zmult_distrib2) |
563 apply (subgoal_tac "b*q' \<le> b'*q'") |
563 apply (subgoal_tac "b*q' \<le> b'*q'") |
564 prefer 2 apply (simp add: mult_right_mono_neg) |
564 prefer 2 apply (simp add: mult_right_mono_neg) |
565 apply (subgoal_tac "b'*q' < b + b*q") |
565 apply (subgoal_tac "b'*q' < b + b*q") |
566 apply arith |
566 apply arith |
723 lemma zmult2_lemma_aux4: "[| (0::int) < c; 0 \<le> r; r < b |] ==> b * (q mod c) + r < b * c" |
723 lemma zmult2_lemma_aux4: "[| (0::int) < c; 0 \<le> r; r < b |] ==> b * (q mod c) + r < b * c" |
724 apply (subgoal_tac "r * 1 < b * (c - q mod c) ") |
724 apply (subgoal_tac "r * 1 < b * (c - q mod c) ") |
725 apply (simp add: zdiff_zmult_distrib2) |
725 apply (simp add: zdiff_zmult_distrib2) |
726 apply (rule order_less_le_trans) |
726 apply (rule order_less_le_trans) |
727 apply (erule mult_strict_right_mono) |
727 apply (erule mult_strict_right_mono) |
728 apply (rule_tac [2] zmult_zle_mono2) |
728 apply (rule_tac [2] mult_left_mono) |
729 apply (auto simp add: compare_rls zadd_commute [of 1] |
729 apply (auto simp add: compare_rls zadd_commute [of 1] |
730 add1_zle_eq pos_mod_bound) |
730 add1_zle_eq pos_mod_bound) |
731 done |
731 done |
732 |
732 |
733 lemma zmult2_lemma: "[| quorem ((a,b), (q,r)); b ~= 0; 0 < c |] |
733 lemma zmult2_lemma: "[| quorem ((a,b), (q,r)); b ~= 0; 0 < c |] |
902 lemma zdiv_number_of_BIT[simp]: |
902 lemma zdiv_number_of_BIT[simp]: |
903 "number_of (v BIT b) div number_of (w BIT False) = |
903 "number_of (v BIT b) div number_of (w BIT False) = |
904 (if ~b | (0::int) \<le> number_of w |
904 (if ~b | (0::int) \<le> number_of w |
905 then number_of v div (number_of w) |
905 then number_of v div (number_of w) |
906 else (number_of v + (1::int)) div (number_of w))" |
906 else (number_of v + (1::int)) div (number_of w))" |
907 apply (simp only: zadd_assoc number_of_BIT) |
907 apply (simp only: add_assoc number_of_BIT) |
908 (*create subgoal because the next step can't simplify numerals*) |
908 (*create subgoal because the next step can't simplify numerals*) |
909 apply (subgoal_tac "2 ~= (0::int) ") |
909 apply (subgoal_tac "2 ~= (0::int) ") |
910 apply (simp del: bin_arith_extra_simps |
910 apply (simp del: bin_arith_extra_simps arith_special |
911 add: zdiv_zmult_zmult1 pos_zdiv_mult_2 not_0_le_lemma neg_zdiv_mult_2, simp) |
911 add: zdiv_zmult_zmult1 pos_zdiv_mult_2 not_0_le_lemma neg_zdiv_mult_2) |
|
912 apply simp |
912 done |
913 done |
913 |
914 |
914 |
915 |
915 (** computing mod by shifting (proofs resemble those for div) **) |
916 (** computing mod by shifting (proofs resemble those for div) **) |
916 |
917 |
920 apply (subgoal_tac "1 \<le> a") |
921 apply (subgoal_tac "1 \<le> a") |
921 prefer 2 apply arith |
922 prefer 2 apply arith |
922 apply (subgoal_tac "1 < a * 2") |
923 apply (subgoal_tac "1 < a * 2") |
923 prefer 2 apply arith |
924 prefer 2 apply arith |
924 apply (subgoal_tac "2* (1 + b mod a) \<le> 2*a") |
925 apply (subgoal_tac "2* (1 + b mod a) \<le> 2*a") |
925 apply (rule_tac [2] zmult_zle_mono2) |
926 apply (rule_tac [2] mult_left_mono) |
926 apply (auto simp add: zadd_commute [of 1] zmult_commute add1_zle_eq |
927 apply (auto simp add: zadd_commute [of 1] zmult_commute add1_zle_eq |
927 pos_mod_bound) |
928 pos_mod_bound) |
928 apply (subst zmod_zadd1_eq) |
929 apply (subst zmod_zadd1_eq) |
929 apply (simp add: zmod_zmult_zmult2 mod_pos_pos_trivial) |
930 apply (simp add: zmod_zmult_zmult2 mod_pos_pos_trivial) |
930 apply (rule mod_pos_pos_trivial) |
931 apply (rule mod_pos_pos_trivial) |
951 if (0::int) \<le> number_of w |
952 if (0::int) \<le> number_of w |
952 then 2 * (number_of v mod number_of w) + 1 |
953 then 2 * (number_of v mod number_of w) + 1 |
953 else 2 * ((number_of v + (1::int)) mod number_of w) - 1 |
954 else 2 * ((number_of v + (1::int)) mod number_of w) - 1 |
954 else 2 * (number_of v mod number_of w))" |
955 else 2 * (number_of v mod number_of w))" |
955 apply (simp only: zadd_assoc number_of_BIT) |
956 apply (simp only: zadd_assoc number_of_BIT) |
956 apply (simp del: bin_arith_extra_simps bin_rel_simps |
957 apply (simp del: bin_arith_extra_simps bin_rel_simps arith_special |
957 add: zmod_zmult_zmult1 pos_zmod_mult_2 not_0_le_lemma neg_zmod_mult_2, simp) |
958 add: zmod_zmult_zmult1 pos_zmod_mult_2 not_0_le_lemma neg_zmod_mult_2 |
|
959 neg_def) |
958 done |
960 done |
959 |
961 |
960 |
962 |
961 |
963 |
962 (** Quotients of signs **) |
964 (** Quotients of signs **) |
1112 apply (subgoal_tac "0 < n") |
1114 apply (subgoal_tac "0 < n") |
1113 prefer 2 |
1115 prefer 2 |
1114 apply (blast intro: order_less_trans) |
1116 apply (blast intro: order_less_trans) |
1115 apply (simp add: zero_less_mult_iff) |
1117 apply (simp add: zero_less_mult_iff) |
1116 apply (subgoal_tac "n * k < n * 1") |
1118 apply (subgoal_tac "n * k < n * 1") |
1117 apply (drule zmult_zless_cancel1 [THEN iffD1], auto) |
1119 apply (drule mult_less_cancel_left [THEN iffD1], auto) |
1118 done |
1120 done |
1119 |
1121 |
1120 lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))" |
1122 lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))" |
1121 apply (auto simp add: dvd_def nat_abs_mult_distrib) |
1123 apply (auto simp add: dvd_def nat_abs_mult_distrib) |
1122 apply (auto simp add: nat_eq_iff abs_if split add: split_if_asm) |
1124 apply (auto simp add: nat_eq_iff abs_if split add: split_if_asm) |