src/HOL/Integ/IntDiv.ML
changeset 8765 1bc30ff5fc54
parent 8624 69619f870939
child 8785 00cff9d083df
equal deleted inserted replaced
8764:3f976a7e81d3 8765:1bc30ff5fc54
   555 
   555 
   556 Goal "[| quorem((b,c),(q,r));  c ~= #0 |] \
   556 Goal "[| quorem((b,c),(q,r));  c ~= #0 |] \
   557 \     ==> quorem ((a*b, c), (a*q + a*r div c, a*r mod c))";
   557 \     ==> quorem ((a*b, c), (a*q + a*r div c, a*r mod c))";
   558 by (auto_tac
   558 by (auto_tac
   559     (claset(),
   559     (claset(),
   560      simpset() delsimprocs [Int_CC.sum_conv, Int_CC.rel_conv]
   560      simpset() addsimps split_ifs@zmult_ac@
   561                addsimps split_ifs@zmult_ac@
       
   562                         [quorem_def, linorder_neq_iff, 
   561                         [quorem_def, linorder_neq_iff, 
   563 			 zadd_zmult_distrib2,
   562 			 zadd_zmult_distrib2,
   564 			 pos_mod_sign,pos_mod_bound,
   563 			 pos_mod_sign,pos_mod_bound,
   565 			 neg_mod_sign, neg_mod_bound]));
   564 			 neg_mod_sign, neg_mod_bound]));
   566 by (ALLGOALS(rtac zmod_zdiv_equality));
   565 by (ALLGOALS(rtac zmod_zdiv_equality));
   601 
   600 
   602 Goal "[| quorem((a,c),(aq,ar));  quorem((b,c),(bq,br));  c ~= #0 |] \
   601 Goal "[| quorem((a,c),(aq,ar));  quorem((b,c),(bq,br));  c ~= #0 |] \
   603 \     ==> quorem ((a+b, c), (aq + bq + (ar+br) div c, (ar+br) mod c))";
   602 \     ==> quorem ((a+b, c), (aq + bq + (ar+br) div c, (ar+br) mod c))";
   604 by (auto_tac
   603 by (auto_tac
   605     (claset(),
   604     (claset(),
   606      simpset() delsimprocs [Int_CC.sum_conv, Int_CC.rel_conv]
   605      simpset() addsimps split_ifs@zmult_ac@
   607                addsimps split_ifs@zmult_ac@
       
   608                         [quorem_def, linorder_neq_iff, 
   606                         [quorem_def, linorder_neq_iff, 
   609 			 zadd_zmult_distrib2,
   607 			 zadd_zmult_distrib2,
   610 			 pos_mod_sign,pos_mod_bound,
   608 			 pos_mod_sign,pos_mod_bound,
   611 			 neg_mod_sign, neg_mod_bound]));
   609 			 neg_mod_sign, neg_mod_bound]));
   612 by (ALLGOALS(rtac zmod_zdiv_equality));
   610 by (ALLGOALS(rtac zmod_zdiv_equality));
   714 
   712 
   715 Goal "[| quorem ((a,b), (q,r));  b ~= #0;  #0 < c |] \
   713 Goal "[| quorem ((a,b), (q,r));  b ~= #0;  #0 < c |] \
   716 \     ==> quorem ((a, b*c), (q div c, b*(q mod c) + r))";
   714 \     ==> quorem ((a, b*c), (q div c, b*(q mod c) + r))";
   717 by (auto_tac  (*SLOW*)
   715 by (auto_tac  (*SLOW*)
   718     (claset(),
   716     (claset(),
   719      simpset() delsimprocs [Int_CC.sum_conv, Int_CC.rel_conv]
   717      simpset() addsimps split_ifs@zmult_ac@
   720                addsimps split_ifs@zmult_ac@
       
   721                         [quorem_def, linorder_neq_iff,
   718                         [quorem_def, linorder_neq_iff,
   722 			 pos_imp_zmult_pos_iff,
   719 			 pos_imp_zmult_pos_iff,
   723 			 neg_imp_zmult_pos_iff,
   720 			 neg_imp_zmult_pos_iff,
   724 			 zadd_zmult_distrib2 RS sym,
   721 			 zadd_zmult_distrib2 RS sym,
   725 			 lemma1, lemma2, lemma3, lemma4]));
   722 			 lemma1, lemma2, lemma3, lemma4]));
   815 				  add1_zle_eq, pos_mod_bound]));
   812 				  add1_zle_eq, pos_mod_bound]));
   816 by (stac zdiv_zadd1_eq 1);
   813 by (stac zdiv_zadd1_eq 1);
   817 by (asm_simp_tac (simpset() addsimps [zdiv_zmult_zmult2, zmod_zmult_zmult2, 
   814 by (asm_simp_tac (simpset() addsimps [zdiv_zmult_zmult2, zmod_zmult_zmult2, 
   818 				      div_pos_pos_trivial]) 1);
   815 				      div_pos_pos_trivial]) 1);
   819 by (stac div_pos_pos_trivial 1);
   816 by (stac div_pos_pos_trivial 1);
   820 by (asm_simp_tac (simpset() delsimprocs [Int_CC.sum_conv, Int_CC.rel_conv]
   817 by (asm_simp_tac (simpset() 
   821            addsimps zadd_ac@ [zmult_2_right, mod_pos_pos_trivial,
   818            addsimps zadd_ac@ [zmult_2_right, mod_pos_pos_trivial,
   822                     pos_mod_sign RS zadd_zle_mono1 RSN (2,order_trans)]) 1);
   819                     pos_mod_sign RS zadd_zle_mono1 RSN (2,order_trans)]) 1);
   823 by (auto_tac (claset(),
   820 by (auto_tac (claset(),
   824 	      simpset() addsimps [mod_pos_pos_trivial]));
   821 	      simpset() addsimps [mod_pos_pos_trivial]));
   825 qed "pos_zdiv_times_2";
   822 qed "pos_zdiv_times_2";
   849 \          then number_of v div (number_of w)    \
   846 \          then number_of v div (number_of w)    \
   850 \          else (number_of v + (#1::int)) div (number_of w))";
   847 \          else (number_of v + (#1::int)) div (number_of w))";
   851 by (simp_tac (simpset_of Int.thy
   848 by (simp_tac (simpset_of Int.thy
   852 			 addsimps [zadd_assoc, number_of_BIT]) 1);
   849 			 addsimps [zadd_assoc, number_of_BIT]) 1);
   853 by (asm_simp_tac (simpset()
   850 by (asm_simp_tac (simpset()
   854 		  delsimprocs [Int_CC.sum_conv, Int_CC.rel_conv]
       
   855                   delsimps bin_arith_extra_simps@bin_rel_simps
   851                   delsimps bin_arith_extra_simps@bin_rel_simps
   856 		  addsimps [zmult_2 RS sym, zdiv_zmult_zmult1,
   852 		  addsimps [zmult_2 RS sym, zdiv_zmult_zmult1,
   857 			    pos_zdiv_times_2, lemma, neg_zdiv_times_2]) 1);
   853 			    pos_zdiv_times_2, lemma, neg_zdiv_times_2]) 1);
   858 qed "zdiv_number_of_BIT";
   854 qed "zdiv_number_of_BIT";
   859 
   855 
   875 				  add1_zle_eq, pos_mod_bound]));
   871 				  add1_zle_eq, pos_mod_bound]));
   876 by (stac zmod_zadd1_eq 1);
   872 by (stac zmod_zadd1_eq 1);
   877 by (asm_simp_tac (simpset() addsimps [zmod_zmult_zmult2, 
   873 by (asm_simp_tac (simpset() addsimps [zmod_zmult_zmult2, 
   878 				      mod_pos_pos_trivial]) 1);
   874 				      mod_pos_pos_trivial]) 1);
   879 by (rtac mod_pos_pos_trivial 1);
   875 by (rtac mod_pos_pos_trivial 1);
   880 by (asm_simp_tac (simpset() delsimprocs [Int_CC.sum_conv, Int_CC.rel_conv]
   876 by (asm_simp_tac (simpset() 
   881                   addsimps zadd_ac@ [zmult_2_right, mod_pos_pos_trivial,
   877                   addsimps zadd_ac@ [zmult_2_right, mod_pos_pos_trivial,
   882                     pos_mod_sign RS zadd_zle_mono1 RSN (2,order_trans)]) 1);
   878                     pos_mod_sign RS zadd_zle_mono1 RSN (2,order_trans)]) 1);
   883 by (auto_tac (claset(),
   879 by (auto_tac (claset(),
   884 	      simpset() addsimps [mod_pos_pos_trivial]));
   880 	      simpset() addsimps [mod_pos_pos_trivial]));
   885 qed "pos_zmod_times_2";
   881 qed "pos_zmod_times_2";
   908 \               else #2 * ((number_of v + (#1::int)) mod number_of w) - #1  \
   904 \               else #2 * ((number_of v + (#1::int)) mod number_of w) - #1  \
   909 \          else #2 * (number_of v mod number_of w))";
   905 \          else #2 * (number_of v mod number_of w))";
   910 by (simp_tac (simpset_of Int.thy
   906 by (simp_tac (simpset_of Int.thy
   911 			 addsimps [zadd_assoc, number_of_BIT]) 1);
   907 			 addsimps [zadd_assoc, number_of_BIT]) 1);
   912 by (asm_simp_tac (simpset()
   908 by (asm_simp_tac (simpset()
   913 		  delsimprocs [Int_CC.sum_conv, Int_CC.rel_conv]
       
   914 		  delsimps bin_arith_extra_simps@bin_rel_simps
   909 		  delsimps bin_arith_extra_simps@bin_rel_simps
   915 		  addsimps [zmult_2 RS sym, zmod_zmult_zmult1,
   910 		  addsimps [zmult_2 RS sym, zmod_zmult_zmult1,
   916 			    pos_zmod_times_2, lemma, neg_zmod_times_2]) 1);
   911 			    pos_zmod_times_2, lemma, neg_zmod_times_2]) 1);
   917 qed "zmod_number_of_BIT";
   912 qed "zmod_number_of_BIT";
   918 
   913