src/Tools/isac/Knowledge/Rational.thy
branchisac-update-Isa09-2
changeset 38031 460c24a6a6ba
parent 38015 67ba02dffacc
child 38034 928cebc9c4aa
equal deleted inserted replaced
38030:95d956108461 38031:460c24a6a6ba
   255 (*. uv polynomial division, result is (quotient, remainder) .*)
   255 (*. uv polynomial division, result is (quotient, remainder) .*)
   256 (*. only for uv_mod_divides .*)
   256 (*. only for uv_mod_divides .*)
   257 (* FIXME: Division von x^9+x^5+1 durch x-1000 funktioniert nicht,
   257 (* FIXME: Division von x^9+x^5+1 durch x-1000 funktioniert nicht,
   258    integer zu klein  *)
   258    integer zu klein  *)
   259 fun uv_mod_pdiv (p1:uv_poly) ([]:uv_poly) = 
   259 fun uv_mod_pdiv (p1:uv_poly) ([]:uv_poly) = 
   260     raise error ("RATIONALS_UV_MOD_PDIV_EXCEPTION: division by zero")
   260     error ("RATIONALS_UV_MOD_PDIV_EXCEPTION: division by zero")
   261   | uv_mod_pdiv p1 [x] = 
   261   | uv_mod_pdiv p1 [x] = 
   262     let
   262     let
   263 	val xs= Unsynchronized.ref  [];
   263 	val xs= Unsynchronized.ref  [];
   264     in
   264     in
   265 	if x<>0 then 
   265 	if x<>0 then 
   266 	    (
   266 	    (
   267 	     xs:=(uv_mod_rem_poly(p1,x));
   267 	     xs:=(uv_mod_rem_poly(p1,x));
   268 	     while length(!xs)>0 andalso hd(!xs)=0 do xs:=tl(!xs)
   268 	     while length(!xs)>0 andalso hd(!xs)=0 do xs:=tl(!xs)
   269 	     )
   269 	     )
   270 	else raise error ("RATIONALS_UV_MOD_PDIV_EXCEPTION: division by zero");
   270 	else error ("RATIONALS_UV_MOD_PDIV_EXCEPTION: division by zero");
   271 	([]:uv_poly,!xs:uv_poly)
   271 	([]:uv_poly,!xs:uv_poly)
   272     end
   272     end
   273   | uv_mod_pdiv p1 p2 =  
   273   | uv_mod_pdiv p1 p2 =  
   274     let
   274     let
   275 	val n= uv_mod_deg(p2);
   275 	val n= uv_mod_deg(p2);
   281 	val c= Unsynchronized.ref  0;
   281 	val c= Unsynchronized.ref  0;
   282 	val output= Unsynchronized.ref  ([],[]);
   282 	val output= Unsynchronized.ref  ([],[]);
   283     in
   283     in
   284 	(
   284 	(
   285 	 if (!m)=0 orelse p2=[0] 
   285 	 if (!m)=0 orelse p2=[0] 
   286          then raise error ("RATIONALS_UV_MOD_PDIV_EXCEPTION: Division by zero") 
   286          then error ("RATIONALS_UV_MOD_PDIV_EXCEPTION: Division by zero") 
   287 	 else
   287 	 else
   288 	     (
   288 	     (
   289 	      if (!m)<n then 
   289 	      if (!m)<n then 
   290 		  (
   290 		  (
   291 		   output:=([0],p1) 
   291 		   output:=([0],p1) 
   321 	val q= Unsynchronized.ref  [];
   321 	val q= Unsynchronized.ref  [];
   322 	val c= Unsynchronized.ref  0;
   322 	val c= Unsynchronized.ref  0;
   323 	val output= Unsynchronized.ref  ([],[]);
   323 	val output= Unsynchronized.ref  ([],[]);
   324     in
   324     in
   325 	(
   325 	(
   326 	 if (!m)=0 orelse p2=[0] then raise error ("RATIONALS_UV_MOD_PDIVP_EXCEPTION: Division by zero") 
   326 	 if (!m)=0 orelse p2=[0] then error ("RATIONALS_UV_MOD_PDIVP_EXCEPTION: Division by zero") 
   327 	 else
   327 	 else
   328 	     (
   328 	     (
   329 	      if (!m)<n then 
   329 	      if (!m)<n then 
   330 		  (
   330 		  (
   331 		   output:=([0],p1) 
   331 		   output:=([0],p1) 
   352 	     !output:uv_poly * uv_poly
   352 	     !output:uv_poly * uv_poly
   353 	 )
   353 	 )
   354     end;
   354     end;
   355 
   355 
   356 (*. calculates the remainder of p1/p2 .*)
   356 (*. calculates the remainder of p1/p2 .*)
   357 fun uv_mod_prest (p1:uv_poly) ([]:uv_poly) = raise error("UV_MOD_PREST_EXCEPTION: Division by zero") 
   357 fun uv_mod_prest (p1:uv_poly) ([]:uv_poly) = error("UV_MOD_PREST_EXCEPTION: Division by zero") 
   358   | uv_mod_prest [] p2 = []:uv_poly
   358   | uv_mod_prest [] p2 = []:uv_poly
   359   | uv_mod_prest p1 p2 = (#2(uv_mod_pdiv p1 p2));
   359   | uv_mod_prest p1 p2 = (#2(uv_mod_pdiv p1 p2));
   360 
   360 
   361 (*. calculates the remainder of p1/p2 in Zp .*)
   361 (*. calculates the remainder of p1/p2 in Zp .*)
   362 fun uv_mod_prestp (p1:uv_poly) ([]:uv_poly) p= raise error("UV_MOD_PRESTP_EXCEPTION: Division by zero") 
   362 fun uv_mod_prestp (p1:uv_poly) ([]:uv_poly) p= error("UV_MOD_PRESTP_EXCEPTION: Division by zero") 
   363   | uv_mod_prestp [] p2 p= []:uv_poly 
   363   | uv_mod_prestp [] p2 p= []:uv_poly 
   364   | uv_mod_prestp p1 p2 p = #2(uv_mod_pdivp p1 p2 p); 
   364   | uv_mod_prestp p1 p2 p = #2(uv_mod_pdivp p1 p2 p); 
   365 
   365 
   366 (*. calculates the content of a uv polynomial .*)
   366 (*. calculates the content of a uv polynomial .*)
   367 fun uv_mod_cont ([]:uv_poly) = 0  
   367 fun uv_mod_cont ([]:uv_poly) = 0  
   368   | uv_mod_cont (x::p)= gcd_int x (uv_mod_cont(p));
   368   | uv_mod_cont (x::p)= gcd_int x (uv_mod_cont(p));
   369 
   369 
   370 (*. divides each coefficient of a uv polynomial by y .*)
   370 (*. divides each coefficient of a uv polynomial by y .*)
   371 fun uv_mod_div_list (p:uv_poly,0) = raise error("UV_MOD_DIV_LIST_EXCEPTION: Division by zero") 
   371 fun uv_mod_div_list (p:uv_poly,0) = error("UV_MOD_DIV_LIST_EXCEPTION: Division by zero") 
   372   | uv_mod_div_list ([],y)   = []:uv_poly
   372   | uv_mod_div_list ([],y)   = []:uv_poly
   373   | uv_mod_div_list (x::p,y) = (x div y)::uv_mod_div_list(p,y); 
   373   | uv_mod_div_list (x::p,y) = (x div y)::uv_mod_div_list(p,y); 
   374 
   374 
   375 (*. calculates the primitiv part of a uv polynomial .*)
   375 (*. calculates the primitiv part of a uv polynomial .*)
   376 fun uv_mod_pp ([]:uv_poly) = []:uv_poly
   376 fun uv_mod_pp ([]:uv_poly) = []:uv_poly
   379 	val c= Unsynchronized.ref  0;
   379 	val c= Unsynchronized.ref  0;
   380     in
   380     in
   381 	(
   381 	(
   382 	 c:=uv_mod_cont(p);
   382 	 c:=uv_mod_cont(p);
   383 	 
   383 	 
   384 	 if !c=0 then raise error ("RATIONALS_UV_MOD_PP_EXCEPTION: content is 0")
   384 	 if !c=0 then error ("RATIONALS_UV_MOD_PP_EXCEPTION: content is 0")
   385 	 else uv_mod_div_list(p,!c)
   385 	 else uv_mod_div_list(p,!c)
   386 	)
   386 	)
   387     end;
   387     end;
   388 
   388 
   389 (*. gets the leading coefficient of a uv polynomial .*)
   389 (*. gets the leading coefficient of a uv polynomial .*)
   515 		 ); 
   515 		 ); 
   516 	    !exit
   516 	    !exit
   517     end;
   517     end;
   518 
   518 
   519 (*. decides if p1 is a factor of p2 in Zp .*)
   519 (*. decides if p1 is a factor of p2 in Zp .*)
   520 fun uv_mod_dividesp ([]:uv_poly) (p2:uv_poly) p= raise error("UV_MOD_DIVIDESP: Division by zero") 
   520 fun uv_mod_dividesp ([]:uv_poly) (p2:uv_poly) p= error("UV_MOD_DIVIDESP: Division by zero") 
   521   | uv_mod_dividesp p1 p2 p= if uv_mod_prestp p2 p1 p = [] then true else false;
   521   | uv_mod_dividesp p1 p2 p= if uv_mod_prestp p2 p1 p = [] then true else false;
   522 
   522 
   523 (*. decides if p1 is a factor of p2 .*)
   523 (*. decides if p1 is a factor of p2 .*)
   524 fun uv_mod_divides ([]:uv_poly) (p2:uv_poly) = raise error("UV_MOD_DIVIDES: Division by zero")
   524 fun uv_mod_divides ([]:uv_poly) (p2:uv_poly) = error("UV_MOD_DIVIDES: Division by zero")
   525   | uv_mod_divides p1 p2 = if uv_mod_prest p2 p1  = [] then true else false;
   525   | uv_mod_divides p1 p2 = if uv_mod_prest p2 p1  = [] then true else false;
   526 
   526 
   527 (*. chinese remainder algorithm .*)
   527 (*. chinese remainder algorithm .*)
   528 fun uv_mod_cra2(r1,r2,m1,m2)=     
   528 fun uv_mod_cra2(r1,r2,m1,m2)=     
   529     let 
   529     let 
   543 	 )
   543 	 )
   544     end;
   544     end;
   545 
   545 
   546 (*. applies the chinese remainder algorithmen to the coefficients of x1 and x2 .*)
   546 (*. applies the chinese remainder algorithmen to the coefficients of x1 and x2 .*)
   547 fun uv_mod_cra_2 ([],[],m1,m2) = [] 
   547 fun uv_mod_cra_2 ([],[],m1,m2) = [] 
   548   | uv_mod_cra_2 ([],x2,m1,m2) = raise error("UV_MOD_CRA_2_EXCEPTION: invalid call x1")
   548   | uv_mod_cra_2 ([],x2,m1,m2) = error("UV_MOD_CRA_2_EXCEPTION: invalid call x1")
   549   | uv_mod_cra_2 (x1,[],m1,m2) = raise error("UV_MOD_CRA_2_EXCEPTION: invalid call x2")
   549   | uv_mod_cra_2 (x1,[],m1,m2) = error("UV_MOD_CRA_2_EXCEPTION: invalid call x2")
   550   | uv_mod_cra_2 (x1::x1s,x2::x2s,m1,m2) = (uv_mod_cra2(x1,x2,m1,m2))::(uv_mod_cra_2(x1s,x2s,m1,m2));
   550   | uv_mod_cra_2 (x1::x1s,x2::x2s,m1,m2) = (uv_mod_cra2(x1,x2,m1,m2))::(uv_mod_cra_2(x1s,x2s,m1,m2));
   551 
   551 
   552 (*. calculates the gcd of two uv polynomials p1' and p2' with the modular algorithm .*)
   552 (*. calculates the gcd of two uv polynomials p1' and p2' with the modular algorithm .*)
   553 fun uv_mod_gcd (p1':uv_poly) (p2':uv_poly) =
   553 fun uv_mod_gcd (p1':uv_poly) (p2':uv_poly) =
   554     let 
   554     let 
   686 (*. tests if the monomial M1 is greater as the monomial M2 and returns a boolean value .*)
   686 (*. tests if the monomial M1 is greater as the monomial M2 and returns a boolean value .*)
   687 (*. 2 orders are implemented LEX_/GGO_ (lexigraphical/greatest degree order) .*)
   687 (*. 2 orders are implemented LEX_/GGO_ (lexigraphical/greatest degree order) .*)
   688 fun mv_monom_greater((M1x,M1l):mv_monom,(M2x,M2l):mv_monom,order)=
   688 fun mv_monom_greater((M1x,M1l):mv_monom,(M2x,M2l):mv_monom,order)=
   689     if order=LEX_ then
   689     if order=LEX_ then
   690 	( 
   690 	( 
   691 	 if length(M1l)<>length(M2l) then raise error ("RATIONALS_MV_MONOM_GREATER_EXCEPTION: Order error")
   691 	 if length(M1l)<>length(M2l) then error ("RATIONALS_MV_MONOM_GREATER_EXCEPTION: Order error")
   692 	 else if (mv_mg_hlp((map op- (M1l~~M2l)))<>GREATER) then false else true
   692 	 else if (mv_mg_hlp((map op- (M1l~~M2l)))<>GREATER) then false else true
   693 	     )
   693 	     )
   694     else
   694     else
   695 	if order=GGO_ then
   695 	if order=GGO_ then
   696 	    ( 
   696 	    ( 
   697 	     if length(M1l)<>length(M2l) then raise error ("RATIONALS_MV_MONOM_GREATER_EXCEPTION: Order error")
   697 	     if length(M1l)<>length(M2l) then error ("RATIONALS_MV_MONOM_GREATER_EXCEPTION: Order error")
   698 	     else 
   698 	     else 
   699 		 if mv_addlist(M1l)=mv_addlist(M2l)  then if (mv_mg_hlp((map op- (M1l~~M2l)))<>GREATER) then false else true
   699 		 if mv_addlist(M1l)=mv_addlist(M2l)  then if (mv_mg_hlp((map op- (M1l~~M2l)))<>GREATER) then false else true
   700 		 else if mv_addlist(M1l)>mv_addlist(M2l) then true else false
   700 		 else if mv_addlist(M1l)>mv_addlist(M2l) then true else false
   701 	     )
   701 	     )
   702 	else raise error ("RATIONALS_MV_MONOM_GREATER_EXCEPTION: Wrong Order");
   702 	else error ("RATIONALS_MV_MONOM_GREATER_EXCEPTION: Wrong Order");
   703 		   
   703 		   
   704 (*. tests if the monomial X is greater as the monomial Y and returns a order value (GREATER,EQUAL,LESS) .*)
   704 (*. tests if the monomial X is greater as the monomial Y and returns a order value (GREATER,EQUAL,LESS) .*)
   705 (*. 2 orders are implemented LEX_/GGO_ (lexigraphical/greatest degree order) .*)
   705 (*. 2 orders are implemented LEX_/GGO_ (lexigraphical/greatest degree order) .*)
   706 fun mv_geq order ((x1,x):mv_monom,(x2,y):mv_monom) =
   706 fun mv_geq order ((x1,x):mv_monom,(x2,y):mv_monom) =
   707 let 
   707 let 
   708     val temp= Unsynchronized.ref  EQUAL;
   708     val temp= Unsynchronized.ref  EQUAL;
   709 in
   709 in
   710     if order=LEX_ then
   710     if order=LEX_ then
   711 	(
   711 	(
   712 	 if length(x)<>length(y) then 
   712 	 if length(x)<>length(y) then 
   713 	     raise error ("RATIONALS_MV_GEQ_EXCEPTION: Order error")
   713 	     error ("RATIONALS_MV_GEQ_EXCEPTION: Order error")
   714 	 else 
   714 	 else 
   715 	     (
   715 	     (
   716 	      temp:=mv_mg_hlp((map op- (x~~y)));
   716 	      temp:=mv_mg_hlp((map op- (x~~y)));
   717 	      if !temp=EQUAL then 
   717 	      if !temp=EQUAL then 
   718 		  ( if x1=x2 then EQUAL 
   718 		  ( if x1=x2 then EQUAL 
   724 	     )
   724 	     )
   725     else 
   725     else 
   726 	if order=GGO_ then 
   726 	if order=GGO_ then 
   727 	    (
   727 	    (
   728 	     if length(x)<>length(y) then 
   728 	     if length(x)<>length(y) then 
   729 	      raise error ("RATIONALS_MV_GEQ_EXCEPTION: Order error")
   729 	      error ("RATIONALS_MV_GEQ_EXCEPTION: Order error")
   730 	     else 
   730 	     else 
   731 		 if mv_addlist(x)=mv_addlist(y) then 
   731 		 if mv_addlist(x)=mv_addlist(y) then 
   732 		     (mv_mg_hlp((map op- (x~~y))))
   732 		     (mv_mg_hlp((map op- (x~~y))))
   733 		 else if mv_addlist(x)>mv_addlist(y) then GREATER else LESS
   733 		 else if mv_addlist(x)>mv_addlist(y) then GREATER else LESS
   734 		     )
   734 		     )
   735 	else raise error ("RATIONALS_MV_GEQ_EXCEPTION: Wrong Order")
   735 	else error ("RATIONALS_MV_GEQ_EXCEPTION: Wrong Order")
   736 end;
   736 end;
   737 
   737 
   738 (*. cuts the first variable from a polynomial .*)
   738 (*. cuts the first variable from a polynomial .*)
   739 fun mv_cut([]:mv_poly)=[]:mv_poly
   739 fun mv_cut([]:mv_poly)=[]:mv_poly
   740   | mv_cut((x,[])::list) = raise error ("RATIONALS_MV_CUT_EXCEPTION: Invalid list ")
   740   | mv_cut((x,[])::list) = error ("RATIONALS_MV_CUT_EXCEPTION: Invalid list ")
   741   | mv_cut((x,y::ys)::list)=(x,ys)::mv_cut(list);
   741   | mv_cut((x,y::ys)::list)=(x,ys)::mv_cut(list);
   742 	    
   742 	    
   743 (*. leading power product .*)
   743 (*. leading power product .*)
   744 fun mv_lpp([]:mv_poly,order)  = []
   744 fun mv_lpp([]:mv_poly,order)  = []
   745   | mv_lpp([(x,y)],order) = y
   745   | mv_lpp([(x,y)],order) = y
   773 	 while (length(!p1o)>0 andalso hd(#2(hd(!p1o)))=lp) do
   773 	 while (length(!p1o)>0 andalso hd(#2(hd(!p1o)))=lp) do
   774 	     (
   774 	     (
   775 	      lc:=hd(mv_cut([hd(!p1o)]))::(!lc);
   775 	      lc:=hd(mv_cut([hd(!p1o)]))::(!lc);
   776 	      p1o:=tl(!p1o)
   776 	      p1o:=tl(!p1o)
   777 	      );
   777 	      );
   778 	 if !lc=[] then raise error ("RATIONALS_MV_LC_EXCEPTION: lc is empty") else ();
   778 	 if !lc=[] then error ("RATIONALS_MV_LC_EXCEPTION: lc is empty") else ();
   779 	 mv_rev_to(!lc)
   779 	 mv_rev_to(!lc)
   780 	 )
   780 	 )
   781     end;
   781     end;
   782 
   782 
   783 (*. compares two powerproducts .*)
   783 (*. compares two powerproducts .*)
   846 fun mv_is_negativ([])=false
   846 fun mv_is_negativ([])=false
   847   | mv_is_negativ(x::xs)=if x<0 then true else mv_is_negativ(xs);
   847   | mv_is_negativ(x::xs)=if x<0 then true else mv_is_negativ(xs);
   848 
   848 
   849 (*. division of monomials .*)
   849 (*. division of monomials .*)
   850 fun mv_mdiv((0,[]):mv_monom,_:mv_monom)=(0,[]):mv_monom
   850 fun mv_mdiv((0,[]):mv_monom,_:mv_monom)=(0,[]):mv_monom
   851   | mv_mdiv(_,(0,[]))= raise error ("RATIONALS_MV_MDIV_EXCEPTION Division by 0 ")
   851   | mv_mdiv(_,(0,[]))= error ("RATIONALS_MV_MDIV_EXCEPTION Division by 0 ")
   852   | mv_mdiv(p1:mv_monom,p2:mv_monom)= 
   852   | mv_mdiv(p1:mv_monom,p2:mv_monom)= 
   853     let
   853     let
   854 	val c= Unsynchronized.ref  (#1(p2));
   854 	val c= Unsynchronized.ref  (#1(p2));
   855 	val pp= Unsynchronized.ref  [];
   855 	val pp= Unsynchronized.ref  [];
   856     in 
   856     in 
   857 	(
   857 	(
   858 	 if !c=0 then raise error("MV_MDIV_EXCEPTION Dividing by zero")
   858 	 if !c=0 then error("MV_MDIV_EXCEPTION Dividing by zero")
   859 	 else c:=(#1(p1) div #1(p2));
   859 	 else c:=(#1(p1) div #1(p2));
   860 	     if #1(p2)<>0 then 
   860 	     if #1(p2)<>0 then 
   861 		 (
   861 		 (
   862 		  pp:=(#2(mv_mmul((1,#2(p1)),(1,(map mv_minus) (#2(p2))))));
   862 		  pp:=(#2(mv_mmul((1,#2(p1)),(1,(map mv_minus) (#2(p2))))));
   863 		  if mv_is_negativ(!pp) then (0,!pp)
   863 		  if mv_is_negativ(!pp) then (0,!pp)
   864 		  else (!c,!pp) 
   864 		  else (!c,!pp) 
   865 		      )
   865 		      )
   866 	     else raise error("MV_MDIV_EXCEPTION Dividing by empty Polynom")
   866 	     else error("MV_MDIV_EXCEPTION Dividing by empty Polynom")
   867 		 )
   867 		 )
   868     end;
   868     end;
   869 
   869 
   870 (*. prints a polynom for (internal use only) .*)
   870 (*. prints a polynom for (internal use only) .*)
   871 fun mv_print_poly([]:mv_poly)=tracing("[]\n")
   871 fun mv_print_poly([]:mv_poly)=tracing("[]\n")
   873   | mv_print_poly((x,y)::p1) = (tracing("("^Int.toString(x)^","^ints2str(y)^"),");mv_print_poly(p1));
   873   | mv_print_poly((x,y)::p1) = (tracing("("^Int.toString(x)^","^ints2str(y)^"),");mv_print_poly(p1));
   874 
   874 
   875 
   875 
   876 (*. division of two multivariate polynomials .*) 
   876 (*. division of two multivariate polynomials .*) 
   877 fun mv_division([]:mv_poly,g:mv_poly,order)=([]:mv_poly,[]:mv_poly)
   877 fun mv_division([]:mv_poly,g:mv_poly,order)=([]:mv_poly,[]:mv_poly)
   878   | mv_division(f,[],order)= raise error ("RATIONALS_MV_DIVISION_EXCEPTION Division by zero")
   878   | mv_division(f,[],order)= error ("RATIONALS_MV_DIVISION_EXCEPTION Division by zero")
   879   | mv_division(f,g,order)=
   879   | mv_division(f,g,order)=
   880     let 
   880     let 
   881 	val r= Unsynchronized.ref  [];
   881 	val r= Unsynchronized.ref  [];
   882 	val q= Unsynchronized.ref  [];
   882 	val q= Unsynchronized.ref  [];
   883 	val g'= Unsynchronized.ref  ([] : mv_monom list);
   883 	val g'= Unsynchronized.ref  ([] : mv_monom list);
   885 	val m= Unsynchronized.ref  (0,[0]);
   885 	val m= Unsynchronized.ref  (0,[0]);
   886 	val exit= Unsynchronized.ref  0;
   886 	val exit= Unsynchronized.ref  0;
   887     in
   887     in
   888 	r := rev(sort (mv_geq order) (mv_shorten(f,order)));
   888 	r := rev(sort (mv_geq order) (mv_shorten(f,order)));
   889 	g':= rev(sort (mv_geq order) (mv_shorten(g,order)));
   889 	g':= rev(sort (mv_geq order) (mv_shorten(g,order)));
   890 	if #1(hd(!g'))=0 then raise error("RATIONALS_MV_DIVISION_EXCEPTION: Dividing by zero") else ();
   890 	if #1(hd(!g'))=0 then error("RATIONALS_MV_DIVISION_EXCEPTION: Dividing by zero") else ();
   891 	if  (mv_monom_greater (hd(!g'),hd(!r),order)) then ([(0,mv_null2(#2(hd(f))))],(!r))
   891 	if  (mv_monom_greater (hd(!g'),hd(!r),order)) then ([(0,mv_null2(#2(hd(f))))],(!r))
   892 	else
   892 	else
   893 	    (
   893 	    (
   894 	     exit:=0;
   894 	     exit:=0;
   895 	     while (if (!exit)=0 then not(mv_monom_greater (hd(!g'),hd(!r),order)) else false) do
   895 	     while (if (!exit)=0 then not(mv_monom_greater (hd(!g'),hd(!r),order)) else false) do
   896 		 (
   896 		 (
   897 		  if (#1(mv_lm(!g',order)))<>0 then m:=mv_mdiv(mv_lm(!r,order),mv_lm(!g',order))
   897 		  if (#1(mv_lm(!g',order)))<>0 then m:=mv_mdiv(mv_lm(!r,order),mv_lm(!g',order))
   898 		  else raise error ("RATIONALS_MV_DIVISION_EXCEPTION: Dividing by zero");	  
   898 		  else error ("RATIONALS_MV_DIVISION_EXCEPTION: Dividing by zero");	  
   899 		  if #1(!m)<>0 then
   899 		  if #1(!m)<>0 then
   900 		      ( 
   900 		      ( 
   901 		       q:=(!m)::(!q);
   901 		       q:=(!m)::(!q);
   902 		       r:=mv_add((!r),mv_minus2(mv_mul(!g',[!m],order)),order)
   902 		       r:=mv_add((!r),mv_minus2(mv_mul(!g',[!m],order)),order)
   903 		       )
   903 		       )
   918   | mv_correct((x,y)::list,v:int)=(x,v::y)::mv_correct(list,v);
   918   | mv_correct((x,y)::list,v:int)=(x,v::y)::mv_correct(list,v);
   919 
   919 
   920 (*. multivariate case .*)
   920 (*. multivariate case .*)
   921 
   921 
   922 (*. decides if x is a factor of y .*)
   922 (*. decides if x is a factor of y .*)
   923 fun mv_divides([]:mv_poly,[]:mv_poly)=  raise error("RATIONALS_MV_DIVIDES_EXCEPTION: division by zero")
   923 fun mv_divides([]:mv_poly,[]:mv_poly)=  error("RATIONALS_MV_DIVIDES_EXCEPTION: division by zero")
   924   | mv_divides(x,[]) =  raise error("RATIONALS_MV_DIVIDES_EXCEPTION: division by zero")
   924   | mv_divides(x,[]) =  error("RATIONALS_MV_DIVIDES_EXCEPTION: division by zero")
   925   | mv_divides(x:mv_poly,y:mv_poly) = #2(mv_division(y,x,LEX_))=[];
   925   | mv_divides(x:mv_poly,y:mv_poly) = #2(mv_division(y,x,LEX_))=[];
   926 
   926 
   927 (*. gets the maximum of a and b .*)
   927 (*. gets the maximum of a and b .*)
   928 fun mv_max(a,b) = if a>b then a else b;
   928 fun mv_max(a,b) = if a>b then a else b;
   929 
   929 
   962 	val count= Unsynchronized.ref  0;
   962 	val count= Unsynchronized.ref  0;
   963 	val max=mv_grad((c1,e1)::others); 
   963 	val max=mv_grad((c1,e1)::others); 
   964 	val help= Unsynchronized.ref  ((c1,e1)::others);
   964 	val help= Unsynchronized.ref  ((c1,e1)::others);
   965 	val list= Unsynchronized.ref  [];
   965 	val list= Unsynchronized.ref  [];
   966     in
   966     in
   967 	if length(e1)>1 then raise error ("RATIONALS_TO_LIST_EXCEPTION: not univariate")
   967 	if length(e1)>1 then error ("RATIONALS_TO_LIST_EXCEPTION: not univariate")
   968 	else if length(e1)=0 then [c1]
   968 	else if length(e1)=0 then [c1]
   969 	     else
   969 	     else
   970 		 (
   970 		 (
   971 		  count:=0;
   971 		  count:=0;
   972 		  while (!count)<=max do
   972 		  while (!count)<=max do
  1174 		    val pp= Unsynchronized.ref [];
  1174 		    val pp= Unsynchronized.ref [];
  1175 		in
  1175 		in
  1176 		    cont:=mv_content(p1);
  1176 		    cont:=mv_content(p1);
  1177 		    pp:=(#1(mv_division(p1,!cont,LEX_)));
  1177 		    pp:=(#1(mv_division(p1,!cont,LEX_)));
  1178 		    if !pp=[] 
  1178 		    if !pp=[] 
  1179 			then raise error("RATIONALS_MV_PP_EXCEPTION: Invalid Content ")
  1179 			then error("RATIONALS_MV_PP_EXCEPTION: Invalid Content ")
  1180 		    else (!pp)
  1180 		    else (!pp)
  1181 		end
  1181 		end
  1182 
  1182 
  1183 (*. calculates the gcd of two multivariate polynomials with a modular approach .*)
  1183 (*. calculates the gcd of two multivariate polynomials with a modular approach .*)
  1184 and mv_gcd ([]:mv_poly) ([]:mv_poly) :mv_poly= []:mv_poly
  1184 and mv_gcd ([]:mv_poly) ([]:mv_poly) :mv_poly= []:mv_poly
  1424 		   vh:=tl(!vh);
  1424 		   vh:=tl(!vh);
  1425 		   i:=(!i)+1     
  1425 		   i:=(!i)+1     
  1426 		   );
  1426 		   );
  1427 	      SOME [(1,rev(!vl))] handle _ => NONE
  1427 	      SOME [(1,rev(!vl))] handle _ => NONE
  1428 	      )
  1428 	      )
  1429      else raise error ("RATIONALS_TERM2COEF_EXCEPTION 1: Invalid term")
  1429      else error ("RATIONALS_TERM2COEF_EXCEPTION 1: Invalid term")
  1430 	 )
  1430 	 )
  1431     end
  1431     end
  1432   | term2coef' (Const ("Groups.plus_class.plus",_) $ t1 $ t2) v :mv_poly option= 
  1432   | term2coef' (Const ("Groups.plus_class.plus",_) $ t1 $ t2) v :mv_poly option= 
  1433     (
  1433     (
  1434      SOME ((the(term2coef' t1 v)) @ (the(term2coef' t2 v))) handle _ => NONE
  1434      SOME ((the(term2coef' t1 v)) @ (the(term2coef' t2 v))) handle _ => NONE
  1435 	 )
  1435 	 )
  1436   | term2coef' (Const ("Groups.minus_class.minus",_) $ t1 $ t2) v :mv_poly option= 
  1436   | term2coef' (Const ("Groups.minus_class.minus",_) $ t1 $ t2) v :mv_poly option= 
  1437     (
  1437     (
  1438      SOME ((the(term2coef' t1 v)) @ mv_skalar_mul((the(term2coef' t2 v)),1)) handle _ => NONE
  1438      SOME ((the(term2coef' t1 v)) @ mv_skalar_mul((the(term2coef' t2 v)),1)) handle _ => NONE
  1439 	 )
  1439 	 )
  1440   | term2coef' (term) v = raise error ("RATIONALS_TERM2COEF_EXCEPTION 2: Invalid term");
  1440   | term2coef' (term) v = error ("RATIONALS_TERM2COEF_EXCEPTION 2: Invalid term");
  1441 
  1441 
  1442 (*. checks if all coefficients of a polynomial are positiv (except the first) .*)
  1442 (*. checks if all coefficients of a polynomial are positiv (except the first) .*)
  1443 fun check_coeff t = (* erste Koeffizient kann <0 sein !!! *)
  1443 fun check_coeff t = (* erste Koeffizient kann <0 sein !!! *)
  1444     if count_neg(tl(the(term2coef' t (get_vars(t)))))=0 then true 
  1444     if count_neg(tl(the(term2coef' t (get_vars(t)))))=0 then true 
  1445     else false;
  1445     else false;
  1539 		   vh:=tl(!vh);
  1539 		   vh:=tl(!vh);
  1540 		   i:=(!i)+1     
  1540 		   i:=(!i)+1     
  1541 		   );
  1541 		   );
  1542 	      SOME [(1,rev(!vl))] handle _ => NONE
  1542 	      SOME [(1,rev(!vl))] handle _ => NONE
  1543 	      )
  1543 	      )
  1544      else raise error ("RATIONALS_TERM2POLY_EXCEPTION 1: Invalid term")
  1544      else error ("RATIONALS_TERM2POLY_EXCEPTION 1: Invalid term")
  1545 	 )
  1545 	 )
  1546     end
  1546     end
  1547   | term2poly' (Const ("Groups.plus_class.plus",_) $ t1 $ t2) v :mv_poly option = 
  1547   | term2poly' (Const ("Groups.plus_class.plus",_) $ t1 $ t2) v :mv_poly option = 
  1548     (
  1548     (
  1549      SOME ((the(term2poly' t1 v)) @ (the(term2poly' t2 v))) handle _ => NONE
  1549      SOME ((the(term2poly' t1 v)) @ (the(term2poly' t2 v))) handle _ => NONE
  1550 	 )
  1550 	 )
  1551   | term2poly' (Const ("Groups.minus_class.minus",_) $ t1 $ t2) v :mv_poly option = 
  1551   | term2poly' (Const ("Groups.minus_class.minus",_) $ t1 $ t2) v :mv_poly option = 
  1552     (
  1552     (
  1553      SOME ((the(term2poly' t1 v)) @ mv_skalar_mul((the(term2poly' t2 v)),~1)) handle _ => NONE
  1553      SOME ((the(term2poly' t1 v)) @ mv_skalar_mul((the(term2poly' t2 v)),~1)) handle _ => NONE
  1554 	 )
  1554 	 )
  1555   | term2poly' (term) v = raise error ("RATIONALS_TERM2POLY_EXCEPTION 2: Invalid term");
  1555   | term2poly' (term) v = error ("RATIONALS_TERM2POLY_EXCEPTION 2: Invalid term");
  1556 
  1556 
  1557 (*. translates an Isabelle term into internal representation.
  1557 (*. translates an Isabelle term into internal representation.
  1558     term2poly
  1558     term2poly
  1559     fn : term ->              (*normalform [2]                    *)
  1559     fn : term ->              (*normalform [2]                    *)
  1560     	 string list ->       (*for ...!!! BITTE DIE ERKLÄRUNG, 
  1560     	 string list ->       (*for ...!!! BITTE DIE ERKLÄRUNG, 
  1562     	 mv_monom list        (*internal representation           *)
  1562     	 mv_monom list        (*internal representation           *)
  1563     		  option      (*the translation may fail with NONE*)
  1563     		  option      (*the translation may fail with NONE*)
  1564 .*)
  1564 .*)
  1565 fun term2poly (t:term) v = 
  1565 fun term2poly (t:term) v = 
  1566      if is_polynomial t then term2poly' t v
  1566      if is_polynomial t then term2poly' t v
  1567      else raise error ("term2poly: invalid = "^(term2str t));
  1567      else error ("term2poly: invalid = "^(term2str t));
  1568 
  1568 
  1569 (*. same as term2poly with automatic detection of the variables .*)
  1569 (*. same as term2poly with automatic detection of the variables .*)
  1570 fun term2polyx t = term2poly t (((map free2str) o vars) t); 
  1570 fun term2polyx t = term2poly t (((map free2str) o vars) t); 
  1571 
  1571 
  1572 (*. checks if the term is in expanded polynomial form and converts it into the internal representation .*)
  1572 (*. checks if the term is in expanded polynomial form and converts it into the internal representation .*)
  1573 fun expanded2poly (t:term) v = 
  1573 fun expanded2poly (t:term) v = 
  1574     (*if is_expanded t then*) term2poly' t v
  1574     (*if is_expanded t then*) term2poly' t v
  1575     (*else raise error ("RATIONALS_EXPANDED2POLY_EXCEPTION: Invalid Polynomial")*);
  1575     (*else error ("RATIONALS_EXPANDED2POLY_EXCEPTION: Invalid Polynomial")*);
  1576 
  1576 
  1577 (*. same as expanded2poly with automatic detection of the variables .*)
  1577 (*. same as expanded2poly with automatic detection of the variables .*)
  1578 fun expanded2polyx t = expanded2poly t (((map free2str) o vars) t);
  1578 fun expanded2polyx t = expanded2poly t (((map free2str) o vars) t);
  1579 
  1579 
  1580 (*. converts a powerproduct into term representation .*)
  1580 (*. converts a powerproduct into term representation .*)
  1802 		)	
  1802 		)	
  1803 	       )	  
  1803 	       )	  
  1804 	      )
  1804 	      )
  1805 	     )
  1805 	     )
  1806     end
  1806     end
  1807 | step_cancel _ = raise error ("RATIONALS_STEP_CANCEL_EXCEPTION: Invalid fraction"); 
  1807 | step_cancel _ = error ("RATIONALS_STEP_CANCEL_EXCEPTION: Invalid fraction"); 
  1808 
  1808 
  1809 
  1809 
  1810 (*. same as step_cancel, this time for expanded forms (input+output) .*)
  1810 (*. same as step_cancel, this time for expanded forms (input+output) .*)
  1811 fun step_cancel_expanded (t as Const ("Rings.inverse_class.divide",_) $ p1 $ p2) = 
  1811 fun step_cancel_expanded (t as Const ("Rings.inverse_class.divide",_) $ p1 $ p2) = 
  1812     let
  1812     let
  1867 		)	
  1867 		)	
  1868 	       )	  
  1868 	       )	  
  1869 	      )
  1869 	      )
  1870 	     )
  1870 	     )
  1871     end
  1871     end
  1872 | step_cancel_expanded _ = raise error ("RATIONALS_STEP_CANCEL_EXCEPTION: Invalid fraction"); 
  1872 | step_cancel_expanded _ = error ("RATIONALS_STEP_CANCEL_EXCEPTION: Invalid fraction"); 
  1873 
  1873 
  1874 (*. calculates the greatest common divisor of numerator and denominator and divides each through it .*)
  1874 (*. calculates the greatest common divisor of numerator and denominator and divides each through it .*)
  1875 fun direct_cancel (t as Const ("Rings.inverse_class.divide",_) $ p1 $ p2) = 
  1875 fun direct_cancel (t as Const ("Rings.inverse_class.divide",_) $ p1 $ p2) = 
  1876     let
  1876     let
  1877 	val p1' = Unsynchronized.ref [];
  1877 	val p1' = Unsynchronized.ref [];
  1952 			    )
  1952 			    )
  1953 		       )
  1953 		       )
  1954 		  )
  1954 		  )
  1955 	     )
  1955 	     )
  1956     end
  1956     end
  1957   | direct_cancel _ = raise error ("RATIONALS_DIRECT_CANCEL_EXCEPTION: Invalid fraction"); 
  1957   | direct_cancel _ = error ("RATIONALS_DIRECT_CANCEL_EXCEPTION: Invalid fraction"); 
  1958 
  1958 
  1959 (*. same es direct_cancel, this time for expanded forms (input+output).*) 
  1959 (*. same es direct_cancel, this time for expanded forms (input+output).*) 
  1960 fun direct_cancel_expanded (t as Const ("Rings.inverse_class.divide",_) $ p1 $ p2) =  
  1960 fun direct_cancel_expanded (t as Const ("Rings.inverse_class.divide",_) $ p1 $ p2) =  
  1961     let
  1961     let
  1962 	val p1' = Unsynchronized.ref [];
  1962 	val p1' = Unsynchronized.ref [];
  2037 			    )
  2037 			    )
  2038 		       )
  2038 		       )
  2039 		  )
  2039 		  )
  2040 	     )
  2040 	     )
  2041     end
  2041     end
  2042   | direct_cancel_expanded _ = raise error ("RATIONALS_DIRECT_CANCEL_EXCEPTION: Invalid fraction"); 
  2042   | direct_cancel_expanded _ = error ("RATIONALS_DIRECT_CANCEL_EXCEPTION: Invalid fraction"); 
  2043 
  2043 
  2044 
  2044 
  2045 (*. adds two fractions .*)
  2045 (*. adds two fractions .*)
  2046 fun add_fract ((Const("Rings.inverse_class.divide",_) $ t11 $ t12),(Const("Rings.inverse_class.divide",_) $ t21 $ t22)) =
  2046 fun add_fract ((Const("Rings.inverse_class.divide",_) $ t11 $ t12),(Const("Rings.inverse_class.divide",_) $ t21 $ t22)) =
  2047     let
  2047     let
  2084 	   poly2term((!den),vars)
  2084 	   poly2term((!den),vars)
  2085 	   )	      
  2085 	   )	      
  2086 	  )
  2086 	  )
  2087 	 )	     
  2087 	 )	     
  2088     end 
  2088     end 
  2089   | add_fract (_,_) = raise error ("RATIONALS_ADD_FRACTION_EXCEPTION: Invalid add_fraction call");
  2089   | add_fract (_,_) = error ("RATIONALS_ADD_FRACTION_EXCEPTION: Invalid add_fraction call");
  2090 
  2090 
  2091 (*. adds two expanded fractions .*)
  2091 (*. adds two expanded fractions .*)
  2092 fun add_fract_exp ((Const("Rings.inverse_class.divide",_) $ t11 $ t12),(Const("Rings.inverse_class.divide",_) $ t21 $ t22)) =
  2092 fun add_fract_exp ((Const("Rings.inverse_class.divide",_) $ t11 $ t12),(Const("Rings.inverse_class.divide",_) $ t21 $ t22)) =
  2093     let
  2093     let
  2094 	val vars=get_vars(t11) union get_vars(t12) union get_vars(t21) union get_vars(t22);
  2094 	val vars=get_vars(t11) union get_vars(t12) union get_vars(t21) union get_vars(t22);
  2118 	   poly2expanded((!den),vars)
  2118 	   poly2expanded((!den),vars)
  2119 	   )	      
  2119 	   )	      
  2120 	  )
  2120 	  )
  2121 	 )	     
  2121 	 )	     
  2122     end 
  2122     end 
  2123   | add_fract_exp (_,_) = raise error ("RATIONALS_ADD_FRACTION_EXP_EXCEPTION: Invalid add_fraction call");
  2123   | add_fract_exp (_,_) = error ("RATIONALS_ADD_FRACTION_EXP_EXCEPTION: Invalid add_fraction call");
  2124 
  2124 
  2125 (*. adds a list of terms .*)
  2125 (*. adds a list of terms .*)
  2126 fun add_list_of_fractions []= (Free("0",HOLogic.realT),[])
  2126 fun add_list_of_fractions []= (Free("0",HOLogic.realT),[])
  2127   | add_list_of_fractions [x]= direct_cancel x
  2127   | add_list_of_fractions [x]= direct_cancel x
  2128   | add_list_of_fractions (x::y::xs) = 
  2128   | add_list_of_fractions (x::y::xs) = 
  2574 	if rest=[] then
  2574 	if rest=[] then
  2575 	    (
  2575 	    (
  2576 	     if last=[(1,mv_null2(vars))] then make_term(factor_list,vars)
  2576 	     if last=[(1,mv_null2(vars))] then make_term(factor_list,vars)
  2577 	     else make_term(last::factor_list,vars)
  2577 	     else make_term(last::factor_list,vars)
  2578 	     )
  2578 	     )
  2579 	else raise error ("RATIONALS_FACTORIZE_DEN_EXCEPTION: Invalid factor by division")
  2579 	else error ("RATIONALS_FACTORIZE_DEN_EXCEPTION: Invalid factor by division")
  2580     end; 
  2580     end; 
  2581 
  2581 
  2582 (*. makes a term out of the elements of the list (expanded polynomial representation) .*)
  2582 (*. makes a term out of the elements of the list (expanded polynomial representation) .*)
  2583 fun make_exp ([],vars) = Free(str_of_int 0,HOLogic.realT) 
  2583 fun make_exp ([],vars) = Free(str_of_int 0,HOLogic.realT) 
  2584   | make_exp ((x::xs),vars) = if length(xs)=0 then poly2expanded(sort (mv_geq LEX_) (x),vars)
  2584   | make_exp ((x::xs),vars) = if length(xs)=0 then poly2expanded(sort (mv_geq LEX_) (x),vars)
  2599 	if rest=[] then
  2599 	if rest=[] then
  2600 	    (
  2600 	    (
  2601 	     if last=[(1,mv_null2(vars))] then make_exp(factor_list,vars)
  2601 	     if last=[(1,mv_null2(vars))] then make_exp(factor_list,vars)
  2602 	     else make_exp(last::factor_list,vars)
  2602 	     else make_exp(last::factor_list,vars)
  2603 	     )
  2603 	     )
  2604 	else raise error ("RATIONALS_FACTORIZE_DEN_EXP_EXCEPTION: Invalid factor by division")
  2604 	else error ("RATIONALS_FACTORIZE_DEN_EXP_EXCEPTION: Invalid factor by division")
  2605     end; 
  2605     end; 
  2606 
  2606 
  2607 (*. calculates the common denominator of all elements of the list and multiplies .*)
  2607 (*. calculates the common denominator of all elements of the list and multiplies .*)
  2608 (*. the nominators and denominators with the correct factor .*)
  2608 (*. the nominators and denominators with the correct factor .*)
  2609 (*. (polynomial representation) .*)
  2609 (*. (polynomial representation) .*)
  2610 fun step_add_list_of_fractions []=(Free("0",HOLogic.realT),[]:term list)
  2610 fun step_add_list_of_fractions []=(Free("0",HOLogic.realT),[]:term list)
  2611   | step_add_list_of_fractions [x]= raise error ("RATIONALS_STEP_ADD_LIST_OF_FRACTIONS_EXCEPTION: Nothing to add")
  2611   | step_add_list_of_fractions [x]= error ("RATIONALS_STEP_ADD_LIST_OF_FRACTIONS_EXCEPTION: Nothing to add")
  2612   | step_add_list_of_fractions (xs) = 
  2612   | step_add_list_of_fractions (xs) = 
  2613     let
  2613     let
  2614         val den_list=termlist2denominators (xs); (* list of denominators *)
  2614         val den_list=termlist2denominators (xs); (* list of denominators *)
  2615 	val (denom,var)=calc_lcm(den_list);      (* common denominator *)
  2615 	val (denom,var)=calc_lcm(den_list);      (* common denominator *)
  2616 	val den=factorize_den(#1(den_list),denom,var); (* faktorisierter Nenner !!! *)
  2616 	val den=factorize_den(#1(den_list),denom,var); (* faktorisierter Nenner !!! *)
  2620 
  2620 
  2621 (*. calculates the common denominator of all elements of the list and multiplies .*)
  2621 (*. calculates the common denominator of all elements of the list and multiplies .*)
  2622 (*. the nominators and denominators with the correct factor .*)
  2622 (*. the nominators and denominators with the correct factor .*)
  2623 (*. (expanded polynomial representation) .*)
  2623 (*. (expanded polynomial representation) .*)
  2624 fun step_add_list_of_fractions_exp []  = (Free("0",HOLogic.realT),[]:term list)
  2624 fun step_add_list_of_fractions_exp []  = (Free("0",HOLogic.realT),[]:term list)
  2625   | step_add_list_of_fractions_exp [x] = raise error ("RATIONALS_STEP_ADD_LIST_OF_FRACTIONS_EXP_EXCEPTION: Nothing to add")
  2625   | step_add_list_of_fractions_exp [x] = error ("RATIONALS_STEP_ADD_LIST_OF_FRACTIONS_EXP_EXCEPTION: Nothing to add")
  2626   | step_add_list_of_fractions_exp (xs)= 
  2626   | step_add_list_of_fractions_exp (xs)= 
  2627     let
  2627     let
  2628         val den_list=termlist2denominators_exp (xs); (* list of denominators *)
  2628         val den_list=termlist2denominators_exp (xs); (* list of denominators *)
  2629 	val (denom,var)=calc_lcm(den_list);      (* common denominator *)
  2629 	val (denom,var)=calc_lcm(den_list);      (* common denominator *)
  2630 	val den=factorize_den_exp(#1(den_list),denom,var); (* faktorisierter Nenner !!! *)
  2630 	val den=factorize_den_exp(#1(den_list),denom,var); (* faktorisierter Nenner !!! *)
  2686     [Const("Rings.inverse_class.divide",[HOLogic.realT,HOLogic.realT]--->HOLogic.realT) $ 
  2686     [Const("Rings.inverse_class.divide",[HOLogic.realT,HOLogic.realT]--->HOLogic.realT) $ 
  2687 	  t $ Free("1",HOLogic.realT)
  2687 	  t $ Free("1",HOLogic.realT)
  2688      ]
  2688      ]
  2689   | term2list (Const("Groups.plus_class.plus",_) $ t1 $ t2) = term2list(t1) @ term2list(t2)
  2689   | term2list (Const("Groups.plus_class.plus",_) $ t1 $ t2) = term2list(t1) @ term2list(t2)
  2690   | term2list (Const("Groups.minus_class.minus",_) $ t1 $ t2) = 
  2690   | term2list (Const("Groups.minus_class.minus",_) $ t1 $ t2) = 
  2691     raise error ("RATIONALS_TERM2LIST_EXCEPTION: - not implemented yet")
  2691     error ("RATIONALS_TERM2LIST_EXCEPTION: - not implemented yet")
  2692   | term2list _ = raise error ("RATIONALS_TERM2LIST_EXCEPTION: invalid term");
  2692   | term2list _ = error ("RATIONALS_TERM2LIST_EXCEPTION: invalid term");
  2693 
  2693 
  2694 (*.factors out the gcd of nominator and denominator:
  2694 (*.factors out the gcd of nominator and denominator:
  2695    a/b = (a' * gcd)/(b' * gcd),  a,b,gcd  are poly[2].*)
  2695    a/b = (a' * gcd)/(b' * gcd),  a,b,gcd  are poly[2].*)
  2696 fun factout_p_  (thy:theory) t = SOME (step_cancel t,[]:term list); 
  2696 fun factout_p_  (thy:theory) t = SOME (step_cancel t,[]:term list); 
  2697 fun factout_ (thy:theory) t = SOME (step_cancel_expanded t,[]:term list); 
  2697 fun factout_ (thy:theory) t = SOME (step_cancel_expanded t,[]:term list); 
  2730 fun add_fraction_p_ (thy:theory) t = 
  2730 fun add_fraction_p_ (thy:theory) t = 
  2731 (tracing("### add_fraction_p_ called");
  2731 (tracing("### add_fraction_p_ called");
  2732     (let val ts = term2list t
  2732     (let val ts = term2list t
  2733      in if 1 < length ts
  2733      in if 1 < length ts
  2734 	then SOME (add_list_of_fractions ts)
  2734 	then SOME (add_list_of_fractions ts)
  2735 	else NONE (*raise error ("RATIONALS_ADD_EXCEPTION: nothing to add")*)
  2735 	else NONE (*error ("RATIONALS_ADD_EXCEPTION: nothing to add")*)
  2736      end) handle _ => NONE
  2736      end) handle _ => NONE
  2737 );
  2737 );
  2738 (*.same as add_fraction_p_ but with normalform [3].*)
  2738 (*.same as add_fraction_p_ but with normalform [3].*)
  2739 (*SOME (step_add_list_of_fractions2(term2list(t))); *)
  2739 (*SOME (step_add_list_of_fractions2(term2list(t))); *)
  2740 fun add_fraction_ (thy:theory) t = 
  2740 fun add_fraction_ (thy:theory) t = 
  2741     if length(term2list(t))>1 
  2741     if length(term2list(t))>1 
  2742     then SOME (add_list_of_fractions_exp(term2list(t))) handle _ => NONE
  2742     then SOME (add_list_of_fractions_exp(term2list(t))) handle _ => NONE
  2743     else (*raise error ("RATIONALS_ADD_FRACTION_EXCEPTION: nothing to add")*)
  2743     else (*error ("RATIONALS_ADD_FRACTION_EXCEPTION: nothing to add")*)
  2744 	NONE;
  2744 	NONE;
  2745 fun add_fraction_ (thy:theory) t = 
  2745 fun add_fraction_ (thy:theory) t = 
  2746     (if 1 < length (term2list t)
  2746     (if 1 < length (term2list t)
  2747      then SOME (add_list_of_fractions_exp (term2list t))
  2747      then SOME (add_list_of_fractions_exp (term2list t))
  2748      else (*raise error ("RATIONALS_ADD_FRACTION_EXCEPTION: nothing to add")*)
  2748      else (*error ("RATIONALS_ADD_FRACTION_EXCEPTION: nothing to add")*)
  2749 	 NONE) handle _ => NONE;
  2749 	 NONE) handle _ => NONE;
  2750 
  2750 
  2751 (*SOME (step_add_list_of_fractions2_exp(term2list(t))); *)
  2751 (*SOME (step_add_list_of_fractions2_exp(term2list(t))); *)
  2752 
  2752 
  2753 (*. brings the term into a normal form .*)
  2753 (*. brings the term into a normal form .*)
  2945 	      | NONE => (tracing("### locate_rule:  rewrite "^
  2945 	      | NONE => (tracing("### locate_rule:  rewrite "^
  2946 				 (id_of_thm r)^" "^(term2str t)^" = NONE");
  2946 				 (id_of_thm r)^" "^(term2str t)^" = NONE");
  2947 			 []) end
  2947 			 []) end
  2948     else (tracing("### locate_rule:  "^(id_of_thm r)^" not mem rrls");[])
  2948     else (tracing("### locate_rule:  "^(id_of_thm r)^" not mem rrls");[])
  2949   | locate_rule _ _ _ _ _ _ =
  2949   | locate_rule _ _ _ _ _ _ =
  2950     raise error ("locate_rule: doesnt match rev-sets in istate");
  2950     error ("locate_rule: doesnt match rev-sets in istate");
  2951 
  2951 
  2952 (*.next_rule = fn : rule list -> term -> rule option
  2952 (*.next_rule = fn : rule list -> term -> rule option
  2953   for a given term return the next rules to be done for cancelling.
  2953   for a given term return the next rules to be done for cancelling.
  2954 arguments:
  2954 arguments:
  2955   rule list     : the reverse rule list
  2955   rule list     : the reverse rule list
  2973    *)
  2973    *)
  2974 	   (_,r,_)::_ => SOME r
  2974 	   (_,r,_)::_ => SOME r
  2975 	 | _ => NONE
  2975 	 | _ => NONE
  2976     end
  2976     end
  2977   | next_rule _ _ _ _ _ =
  2977   | next_rule _ _ _ _ _ =
  2978     raise error ("next_rule: doesnt match rev-sets in istate");
  2978     error ("next_rule: doesnt match rev-sets in istate");
  2979 
  2979 
  2980 (*.val attach_form = f : rule list -> term -> term
  2980 (*.val attach_form = f : rule list -> term -> term
  2981 			 -> (rule * (term * term list)) list
  2981 			 -> (rule * (term * term list)) list
  2982   checks an input term TI, if it may belong to a current cancellation, by
  2982   checks an input term TI, if it may belong to a current cancellation, by
  2983   trying to derive it from the given term TG.
  2983   trying to derive it from the given term TG.
  3052 	      | NONE => (tracing("### locate_rule:  rewrite "^
  3052 	      | NONE => (tracing("### locate_rule:  rewrite "^
  3053 				 (id_of_thm r)^" "^(term2str t)^" = NONE");
  3053 				 (id_of_thm r)^" "^(term2str t)^" = NONE");
  3054 			 []) end
  3054 			 []) end
  3055     else (tracing("### locate_rule:  "^(id_of_thm r)^" not mem rrls");[])
  3055     else (tracing("### locate_rule:  "^(id_of_thm r)^" not mem rrls");[])
  3056   | locate_rule _ _ _ _ _ _ = 
  3056   | locate_rule _ _ _ _ _ _ = 
  3057     raise error ("locate_rule: doesnt match rev-sets in istate");
  3057     error ("locate_rule: doesnt match rev-sets in istate");
  3058 
  3058 
  3059 fun next_rule thy eval_rls ro [rs] t =
  3059 fun next_rule thy eval_rls ro [rs] t =
  3060     let val der = make_deriv thy eval_rls rs ro NONE t;
  3060     let val der = make_deriv thy eval_rls rs ro NONE t;
  3061     in case der of 
  3061     in case der of 
  3062 (* val (_,r,_)::_ = der;
  3062 (* val (_,r,_)::_ = der;
  3063    *)
  3063    *)
  3064 	   (_,r,_)::_ => SOME r
  3064 	   (_,r,_)::_ => SOME r
  3065 	 | _ => NONE
  3065 	 | _ => NONE
  3066     end
  3066     end
  3067   | next_rule _ _ _ _ _ = 
  3067   | next_rule _ _ _ _ _ = 
  3068     raise error ("next_rule: doesnt match rev-sets in istate");
  3068     error ("next_rule: doesnt match rev-sets in istate");
  3069 
  3069 
  3070 fun attach_form (_:rule list list) (_:term) (_:term) = (*still missing*)
  3070 fun attach_form (_:rule list list) (_:term) (_:term) = (*still missing*)
  3071     []:(rule * (term * term list)) list;
  3071     []:(rule * (term * term list)) list;
  3072 
  3072 
  3073 val pat = parse_patt thy "?r/?s";
  3073 val pat = parse_patt thy "?r/?s";
  3169 	      | NONE => (tracing("### locate_rule:  rewrite "^
  3169 	      | NONE => (tracing("### locate_rule:  rewrite "^
  3170 				 (id_of_thm r)^" "^(term2str t)^" = NONE");
  3170 				 (id_of_thm r)^" "^(term2str t)^" = NONE");
  3171 			 []) end
  3171 			 []) end
  3172     else (tracing("### locate_rule:  "^(id_of_thm r)^" not mem rrls");[])
  3172     else (tracing("### locate_rule:  "^(id_of_thm r)^" not mem rrls");[])
  3173   | locate_rule _ _ _ _ _ _ =
  3173   | locate_rule _ _ _ _ _ _ =
  3174     raise error ("locate_rule: doesnt match rev-sets in istate");
  3174     error ("locate_rule: doesnt match rev-sets in istate");
  3175 
  3175 
  3176 (*.next_rule = fn : rule list -> term -> rule option
  3176 (*.next_rule = fn : rule list -> term -> rule option
  3177   for a given term return the next rules to be done for cancelling.
  3177   for a given term return the next rules to be done for cancelling.
  3178 arguments:
  3178 arguments:
  3179   rule list     : the reverse rule list
  3179   rule list     : the reverse rule list
  3197    *)
  3197    *)
  3198 	   (_,r,_)::_ => SOME r
  3198 	   (_,r,_)::_ => SOME r
  3199 	 | _ => NONE
  3199 	 | _ => NONE
  3200     end
  3200     end
  3201   | next_rule _ _ _ _ _ =
  3201   | next_rule _ _ _ _ _ =
  3202     raise error ("next_rule: doesnt match rev-sets in istate");
  3202     error ("next_rule: doesnt match rev-sets in istate");
  3203 
  3203 
  3204 (*.val attach_form = f : rule list -> term -> term
  3204 (*.val attach_form = f : rule list -> term -> term
  3205 			 -> (rule * (term * term list)) list
  3205 			 -> (rule * (term * term list)) list
  3206   checks an input term TI, if it may belong to a current cancellation, by
  3206   checks an input term TI, if it may belong to a current cancellation, by
  3207   trying to derive it from the given term TG.
  3207   trying to derive it from the given term TG.
  3313 	      | NONE => (tracing("### locate_rule:  rewrite "^
  3313 	      | NONE => (tracing("### locate_rule:  rewrite "^
  3314 				 (id_of_thm r)^" "^(term2str t)^" = NONE");
  3314 				 (id_of_thm r)^" "^(term2str t)^" = NONE");
  3315 			 []) end
  3315 			 []) end
  3316     else (tracing("### locate_rule:  "^(id_of_thm r)^" not mem rrls");[])
  3316     else (tracing("### locate_rule:  "^(id_of_thm r)^" not mem rrls");[])
  3317   | locate_rule _ _ _ _ _ _ =
  3317   | locate_rule _ _ _ _ _ _ =
  3318     raise error ("locate_rule: doesnt match rev-sets in istate");
  3318     error ("locate_rule: doesnt match rev-sets in istate");
  3319 
  3319 
  3320 (*.next_rule = fn : rule list -> term -> rule option
  3320 (*.next_rule = fn : rule list -> term -> rule option
  3321   for a given term return the next rules to be done for cancelling.
  3321   for a given term return the next rules to be done for cancelling.
  3322 arguments:
  3322 arguments:
  3323   rule list     : the reverse rule list
  3323   rule list     : the reverse rule list
  3341    *)
  3341    *)
  3342 	   (_,r,_)::_ => SOME r
  3342 	   (_,r,_)::_ => SOME r
  3343 	 | _ => NONE
  3343 	 | _ => NONE
  3344     end
  3344     end
  3345   | next_rule _ _ _ _ _ =
  3345   | next_rule _ _ _ _ _ =
  3346     raise error ("next_rule: doesnt match rev-sets in istate");
  3346     error ("next_rule: doesnt match rev-sets in istate");
  3347 
  3347 
  3348 (*.val attach_form = f : rule list -> term -> term
  3348 (*.val attach_form = f : rule list -> term -> term
  3349 			 -> (rule * (term * term list)) list
  3349 			 -> (rule * (term * term list)) list
  3350   checks an input term TI, if it may belong to a current cancellation, by
  3350   checks an input term TI, if it may belong to a current cancellation, by
  3351   trying to derive it from the given term TG.
  3351   trying to derive it from the given term TG.