Context Navigation

source: git/factory/int_poly.cc @ c4682e0

spielwiese

Last change on this file since c4682e0 was c4682e0, checked in by Niels Ranosch <ranosch@…>, 13 years ago
FIX: In some (inheriting) copy-constructors their base class should be explicitly initialized
Property mode set to `100644`
File size: 57.7 KB

Rev	Line
[493c477]	1	/* emacs edit mode for this file is -- C++ -- */
[341696]	2	/* $Id$ */
[2dd068]	3
[e4fe2b]	4	#include "config.h"
[9d7aaa]	5
[32e9cd7]	6	#ifndef NOSTREAMIO
[2dd068]	7	#include <string.h>
[049c4f]	8	#if defined(WINNT) && ! defined(__GNUC__)
[4e8da2]	9	#include <strstrea.h>
	10	#else
[22347b6]	11	#if __GNUC__ < 3
[2dd068]	12	#include <strstream.h>
[22347b6]	13	#else
	14	#include <strstream>
	15	using namespace std;
	16	#endif
[4e8da2]	17	#endif
[32e9cd7]	18	#endif /* NOSTREAMIO */
[2dd068]	19
[650f2d8]	20	#include "cf_assert.h"
[32e9cd7]	21
[2dd068]	22	#include "cf_defs.h"
	23	#include "cf_factory.h"
	24	#include "int_cf.h"
[778a4e]	25	#include "int_int.h"
[2dd068]	26	#include "int_poly.h"
	27	#include "canonicalform.h"
	28	#include "variable.h"
	29	#include "imm.h"
	30
[f79b94c]	31	#ifdef HAVE_OMALLOC
	32	const omBin term::term_bin = omGetSpecBin(sizeof(term));
	33	const omBin InternalPoly::InternalPoly_bin = omGetSpecBin(sizeof(InternalPoly));
	34	#endif
[2dd068]	35
	36	InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
	37	{
	38	firstTerm = first;
	39	lastTerm = last;
	40	var = v;
	41	}
	42
	43	InternalPoly::InternalPoly()
	44	{
	45	ASSERT( 0, "ups, why do you initialize an empty poly" );
	46	}
	47
	48	InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
	49	{
	50	var = v;
	51	firstTerm = new term( 0, c, e );
	52	lastTerm = firstTerm;
	53	}
	54
[c4682e0]	55	InternalPoly::InternalPoly( const InternalPoly& ):InternalCF()
[2dd068]	56	{
[32e9cd7]	57	ASSERT( 0, "ups there is something wrong in your code" );
[e76d7a6]	58	}
[2dd068]	59
	60	InternalPoly::~InternalPoly()
	61	{
	62	freeTermList( firstTerm );
	63	}
	64
	65	InternalCF*
	66	InternalPoly::deepCopyObject() const
	67	{
	68	termList first, last;
	69	first = deepCopyTermList( firstTerm, last );
	70	return new InternalPoly( first, last, var );
	71	}
	72
	73	InternalCF*
	74	InternalPoly::genZero()
	75	{
	76	return firstTerm->coeff.genZero().getval();
	77	}
	78
	79	InternalCF*
	80	InternalPoly::genOne()
	81	{
	82	return firstTerm->coeff.genOne().getval();
	83	}
	84
	85	bool
	86	InternalPoly::isUnivariate() const
	87	{
	88	termList cursor = firstTerm;
[4ccbc25]	89	while ( cursor )
	90	{
[a29d092]	91	if ( ! cursor->coeff.inCoeffDomain() )
	92	return false;
	93	cursor = cursor->next;
[2dd068]	94	}
	95	return true;
	96	}
	97
[791c0a]	98	//{{{ int InternalPoly::degree ()
	99	// docu: see CanonicalForm::sign ()
[2dd068]	100	int
[791c0a]	101	InternalPoly::degree ()
[2dd068]	102	{
	103	return firstTerm->exp;
	104	}
[791c0a]	105	//}}}
[2dd068]	106
[b761b9]	107	//{{{ int InternalPoly::sign () const
	108	// docu: see CanonicalForm::sign()
[2dd068]	109	int
[b761b9]	110	InternalPoly::sign () const
[2dd068]	111	{
	112	return firstTerm->coeff.sign();
	113	}
[b761b9]	114	//}}}
[2dd068]	115
[791c0a]	116	//{{{ CanonicalForm InternalPoly::lc (), Lc (), LC ()
	117	// docu: see CanonicalForm::lc(), Lc(), LC()
[2dd068]	118	CanonicalForm
[791c0a]	119	InternalPoly::lc ()
[2dd068]	120	{
	121	return firstTerm->coeff.lc();
	122	}
	123
	124	CanonicalForm
[791c0a]	125	InternalPoly::Lc ()
[2dd068]	126	{
[791c0a]	127	return firstTerm->coeff.Lc();
[2dd068]	128	}
	129
[791c0a]	130	CanonicalForm
	131	InternalPoly::LC ()
[2dd068]	132	{
[791c0a]	133	return firstTerm->coeff;
[2dd068]	134	}
[791c0a]	135	//}}}
[2dd068]	136
[791c0a]	137	//{{{ CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
	138	// docu: see CanonicalForm::tailcoeff(), taildegree()
[2dd068]	139	CanonicalForm
[791c0a]	140	InternalPoly::tailcoeff ()
[2dd068]	141	{
	142	return lastTerm->coeff;
	143	}
	144
[791c0a]	145	int
	146	InternalPoly::taildegree ()
	147	{
	148	return lastTerm->exp;
	149	}
	150	//}}}
	151
[4e8da2]	152	//{{{ CanonicalForm InternalPoly::coeff ( int i )
	153	// docu: see CanonicalForm::operator []()
[2dd068]	154	CanonicalForm
[4e8da2]	155	InternalPoly::coeff ( int i )
[2dd068]	156	{
	157	termList theCursor = firstTerm;
[4ccbc25]	158	while ( theCursor )
	159	{
[a29d092]	160	if ( theCursor->exp == i )
	161	return theCursor->coeff;
	162	else if ( theCursor->exp < i )
	163	return CanonicalForm( 0 );
	164	else
	165	theCursor = theCursor->next;
[2dd068]	166	}
[4e8da2]	167	return CanonicalForm( 0 );
[2dd068]	168	}
[4e8da2]	169	//}}}
[2dd068]	170
[32e9cd7]	171	#ifndef NOSTREAMIO
[2dd068]	172	void
[181148]	173	InternalPoly::print(OSTREAM &aStream, char * aString )
[2dd068]	174	{
[32e9cd7]	175	if ( ! firstTerm )
[a29d092]	176	aStream << 0 << aString;
[4ccbc25]	177	else
	178	{
[a29d092]	179	char * theString;
	180	termList theCursor = firstTerm;
[4ccbc25]	181	while ( theCursor )
	182	{
[a29d092]	183	ostrstream theStream;
	184	if ( theCursor->exp == 0 )
	185	theCursor->coeff.print( aStream, aString );
[4ccbc25]	186	else if ( theCursor->coeff.isOne() )
	187	{
[a29d092]	188	aStream << var;
	189	if ( theCursor->exp != 1 )
	190	aStream << '^' << theCursor->exp << aString;
	191	else
	192	aStream << aString;
	193	}
[4ccbc25]	194	else if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() )
	195	{
[a29d092]	196	aStream << '-' << var;
	197	if ( theCursor->exp != 1 )
	198	aStream << '^' << theCursor->exp << aString;
	199	else
	200	aStream << aString;
	201	}
[4ccbc25]	202	else
	203	{
[a29d092]	204	theStream << '*' << var;
	205	if ( theCursor->exp != 1 )
	206	theStream << '^' << theCursor->exp << aString << ends;
	207	else
	208	theStream << aString << ends; // results from error in GNU strstream
	209	theString = theStream.str();
	210	theCursor->coeff.print( aStream, theString );
[8d1ad78]	211	theStream.freeze(0);//delete [] theString;
[a29d092]	212	}
	213	theCursor = theCursor->next;
	214	if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
	215	aStream << '+';
	216	}
[2dd068]	217	}
	218	}
[32e9cd7]	219	#endif /* NOSTREAMIO */
[2dd068]	220
[43a44b]	221	//{{{ InternalCF * InternalPoly::neg ()
	222	// docu: see CanonicalForm::operator -()
	223	InternalCF *
	224	InternalPoly::neg ()
[2dd068]	225	{
[8ce2d8c]	226	if ( getRefCount() <= 1 )
[4ccbc25]	227	{
[a29d092]	228	negateTermList( firstTerm );
	229	return this;
[4ccbc25]	230	}
	231	else
	232	{
[a29d092]	233	decRefCount();
	234	termList last, first = copyTermList( firstTerm, last, true );
	235	return new InternalPoly( first, last, var );
[2dd068]	236	}
	237	}
[43a44b]	238	//}}}
[2dd068]	239
	240	InternalCF*
	241	InternalPoly::invert()
	242	{
[4ccbc25]	243	if ( inExtension() && getReduce( var ) )
	244	{
[a29d092]	245	setReduce( var, false );
	246	CanonicalForm a( this->copyObject() );
	247	CanonicalForm b = getMipo( var );
	248	CanonicalForm u, v;
	249	CanonicalForm g = extgcd( a, b, u, v );
	250	setReduce( var, true );
	251	return u.getval();
[2dd068]	252	}
	253	else
[a29d092]	254	return CFFactory::basic( 0 );
[2dd068]	255	}
	256
[ec970e]	257	InternalCF*
	258	InternalPoly::tryInvert ( const CanonicalForm& M, bool& fail)
	259	{
	260	if ( inExtension() && !getReduce ( var ) )
	261	{
	262	CanonicalForm b, inverse;
	263	CanonicalForm F ( this ->copyObject() );
	264	Variable a = M.mvar();
	265	Variable x = Variable(1);
	266	F= mod (F, M); //reduce mod M
	267	CanonicalForm g= extgcd (replacevar( F, a, x ), replacevar( M, a, x ), inverse, b );
	268	if(!g.isOne())
	269	fail = true;
	270	else
	271	inverse = replacevar( inverse, x, a ); // change back to alg var
	272	CanonicalForm test= mod (inverse*F, M);
	273	return inverse.getval();
	274	}
	275	else
	276	return CFFactory::basic( 0 );
	277	}
	278
[2dd068]	279	InternalCF*
	280	InternalPoly::addsame( InternalCF* aCoeff )
	281	{
	282	InternalPoly * aPoly = (InternalPoly*)aCoeff;
[8ce2d8c]	283	if ( getRefCount() <= 1 )
[4ccbc25]	284	{
[a29d092]	285	firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
	286	if ( firstTerm && firstTerm->exp != 0 )
	287	return this;
[4ccbc25]	288	else if ( firstTerm )
	289	{
[a29d092]	290	InternalCF * res = firstTerm->coeff.getval();
	291	delete this;
	292	return res;
	293	}
[4ccbc25]	294	else
	295	{
[a29d092]	296	delete this;
	297	return CFFactory::basic( 0 );
	298	}
[2dd068]	299	}
[4ccbc25]	300	else
	301	{
[a29d092]	302	decRefCount();
	303	termList last, first = copyTermList( firstTerm, last );
	304	first = addTermList( first, aPoly->firstTerm, last, false );
	305	if ( first && first->exp != 0 )
	306	return new InternalPoly( first, last, var );
[4ccbc25]	307	else if ( first )
	308	{
[a29d092]	309	InternalCF * res = first->coeff.getval();
	310	delete first;
	311	return res;
	312	}
	313	else
	314	return CFFactory::basic( 0 );
[2dd068]	315
	316	}
	317	}
	318
	319	InternalCF*
	320	InternalPoly::subsame( InternalCF* aCoeff )
	321	{
	322	InternalPoly * aPoly = (InternalPoly*)aCoeff;
[8ce2d8c]	323	if ( getRefCount() <= 1 )
[4ccbc25]	324	{
[a29d092]	325	firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
	326	if ( firstTerm && firstTerm->exp != 0 )
	327	return this;
[4ccbc25]	328	else if ( firstTerm )
	329	{
[a29d092]	330	InternalCF * res = firstTerm->coeff.getval();
	331	delete this;
	332	return res;
	333	}
[4ccbc25]	334	else
	335	{
[a29d092]	336	delete this;
	337	return CFFactory::basic( 0 );
	338	}
[2dd068]	339	}
[4ccbc25]	340	else
	341	{
[a29d092]	342	decRefCount();
	343	termList last, first = copyTermList( firstTerm, last );
	344	first = addTermList( first, aPoly->firstTerm, last, true );
	345	if ( first && first->exp != 0 )
	346	return new InternalPoly( first, last, var );
[4ccbc25]	347	else if ( first )
	348	{
[a29d092]	349	InternalCF * res = first->coeff.getval();
	350	delete first;
	351	return res;
	352	}
	353	else
	354	return CFFactory::basic( 0 );
[2dd068]	355
	356	}
	357	}
	358
	359	InternalCF*
	360	InternalPoly::mulsame( InternalCF* aCoeff )
	361	{
[778a4e]	362	if (is_imm(aCoeff)) return mulcoeff(aCoeff);
[2dd068]	363	InternalPoly aPoly = (InternalPoly)aCoeff;
	364	termList resultFirst = 0, resultLast = 0;
	365	termList theCursor = firstTerm;
	366
[4ccbc25]	367	while ( theCursor )
	368	{
	369	resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
[778a4e]	370	theCursor->coeff, theCursor->exp, resultLast, false );
[a29d092]	371	theCursor = theCursor->next;
[2dd068]	372	}
[4ccbc25]	373	if ( inExtension() && getReduce( var ) )
	374	{
[a29d092]	375	resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
	376	if ( resultFirst == 0 )
[ac8e1a]	377	{
[8ce2d8c]	378	if ( getRefCount() <= 1 )
[4ccbc25]	379	{
[a29d092]	380	delete this;
	381	return CFFactory::basic(0);
	382	}
[4ccbc25]	383	else
	384	{
[a29d092]	385	decRefCount();
	386	return CFFactory::basic(0);
	387	}
[ac8e1a]	388	}
[a29d092]	389	else if ( resultFirst->exp == 0 )
[ac8e1a]	390	{
[8ce2d8c]	391	if ( getRefCount() <= 1 )
[4ccbc25]	392	{
[a29d092]	393	InternalCF * res = resultFirst->coeff.getval();
	394	delete resultFirst;
	395	delete this;
	396	return res;
	397	}
[4ccbc25]	398	else
	399	{
[a29d092]	400	decRefCount();
	401	InternalCF * res = resultFirst->coeff.getval();
	402	delete resultFirst;
	403	return res;
	404	}
[ac8e1a]	405	}
[2dd068]	406	}
[8ce2d8c]	407	if ( getRefCount() <= 1 )
[4ccbc25]	408	{
[a29d092]	409	freeTermList( firstTerm );
	410	firstTerm = resultFirst;
	411	lastTerm = resultLast;
	412	return this;
[2dd068]	413	}
[4ccbc25]	414	else
	415	{
[a29d092]	416	decRefCount();
	417	return new InternalPoly( resultFirst, resultLast, var );
[2dd068]	418	}
	419	}
	420
[ec970e]	421	InternalCF*
	422	InternalPoly::tryMulsame( InternalCF* aCoeff, const CanonicalForm& M)
	423	{
	424	if (is_imm(aCoeff))
	425	return mulcoeff(aCoeff);
	426	InternalPoly aPoly = (InternalPoly)aCoeff;
	427	termList resultFirst = 0, resultLast = 0;
	428	termList theCursor = firstTerm;
	429
	430	while ( theCursor )
	431	{
	432	resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
	433	theCursor->coeff, theCursor->exp, resultLast, false );
	434	theCursor = theCursor->next;
	435	}
	436	if ( inExtension() && !getReduce( var ) )
	437	{
	438	resultFirst= reduceTermList (resultFirst, ((InternalPoly*) M.getval())->firstTerm, resultLast);
	439	if ( resultFirst == 0 )
	440	{
	441	if ( getRefCount() <= 1 )
	442	{
	443	delete this;
	444	return CFFactory::basic(0);
	445	}
	446	else
	447	{
	448	decRefCount();
	449	return CFFactory::basic(0);
	450	}
	451	}
	452	else if ( resultFirst->exp == 0 )
	453	{
	454	if ( getRefCount() <= 1 )
	455	{
	456	InternalCF * res = resultFirst->coeff.getval();
	457	delete resultFirst;
	458	delete this;
	459	return res;
	460	}
	461	else
	462	{
	463	decRefCount();
	464	InternalCF * res = resultFirst->coeff.getval();
	465	delete resultFirst;
	466	return res;
	467	}
	468	}
	469	}
	470	if ( getRefCount() <= 1 )
	471	{
	472	freeTermList( firstTerm );
	473	firstTerm = resultFirst;
	474	lastTerm = resultLast;
	475	return this;
	476	}
	477	else
	478	{
	479	decRefCount();
	480	return new InternalPoly( resultFirst, resultLast, var );
	481	}
	482	}
	483
[2dd068]	484	InternalCF*
	485	InternalPoly::dividesame( InternalCF* aCoeff )
	486	{
	487	return divsame( aCoeff );
	488	}
	489
	490
	491	InternalCF*
	492	InternalPoly::divsame( InternalCF* aCoeff )
	493	{
[4ccbc25]	494	if ( inExtension() && getReduce( var ) )
	495	{
[a29d092]	496	InternalCF * dummy = aCoeff->invert();
[778a4e]	497	if (is_imm(dummy)) dummy=this->mulsame(dummy);
	498	else dummy = dummy->mulsame( this );
[8ce2d8c]	499	if ( getRefCount() <= 1 )
[4ccbc25]	500	{
[a29d092]	501	delete this;
	502	return dummy;
	503	}
[4ccbc25]	504	else
	505	{
[a29d092]	506	decRefCount();
	507	return dummy;
	508	}
[2dd068]	509	}
	510	InternalPoly aPoly = (InternalPoly)aCoeff;
	511	termList dummy, first, last, resultfirst = 0, resultlast = 0;
	512	CanonicalForm coeff, newcoeff;
	513	int exp, newexp;
	514	bool singleObject;
	515
[8ce2d8c]	516	if ( getRefCount() <= 1 )
[4ccbc25]	517	{
[a29d092]	518	first = firstTerm; last = lastTerm; singleObject = true;
[2dd068]	519	}
[4ccbc25]	520	else
	521	{
[a29d092]	522	first = copyTermList( firstTerm, last ); singleObject = false;
	523	decRefCount();
[2dd068]	524	}
	525	coeff = aPoly->firstTerm->coeff;
	526	exp = aPoly->firstTerm->exp;
[4ccbc25]	527	while (first && ( first->exp >= exp ) )
	528	{
[a29d092]	529	newcoeff = first->coeff / coeff;
	530	newexp = first->exp - exp;
	531	dummy = first;
	532	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
	533	delete dummy;
	534	appendTermList( resultfirst, resultlast, newcoeff, newexp );
[2dd068]	535	}
	536	freeTermList( first );
[4ccbc25]	537	if ( singleObject )
	538	{
	539	if ( resultfirst && resultfirst->exp != 0 )
	540	{
[a29d092]	541	firstTerm = resultfirst;
	542	lastTerm = resultlast;
	543	return this;
	544	}
[4ccbc25]	545	else if ( resultfirst )
	546	{
[a29d092]	547	InternalCF * res = resultfirst->coeff.getval();
	548	delete resultfirst;
	549	firstTerm = 0;
	550	delete this;
	551	return res;
	552	}
[4ccbc25]	553	else
	554	{
[a29d092]	555	// this should not happen (evtl use assertion)
	556	ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
	557	firstTerm = 0;
	558	delete this;
	559	return CFFactory::basic( 0 );
	560	}
[2dd068]	561	}
[4ccbc25]	562	else
	563	{
[a29d092]	564	if ( resultfirst && resultfirst->exp != 0 )
	565	return new InternalPoly( resultfirst, resultlast, var );
[4ccbc25]	566	else if ( resultfirst )
	567	{
[a29d092]	568	InternalCF * res = resultfirst->coeff.getval();
	569	delete resultfirst;
	570	return res;
	571	}
	572	else
	573	return CFFactory::basic( 0 );
[2dd068]	574	}
	575	}
	576
[ec970e]	577	InternalCF*
	578	InternalPoly::tryDivsame( InternalCF* aCoeff, const CanonicalForm& M, bool& fail )
	579	{
	580	if ( inExtension() && !getReduce( var ) )
	581	{
	582	InternalCF * dummy = aCoeff->tryInvert(M, fail);
	583	if (fail)
	584	return CFFactory::basic( 0 );
	585	if (is_imm(dummy)) dummy=this->tryMulsame(dummy, M);
	586	else dummy = dummy->tryMulsame( this, M);
	587	if (fail)
	588	{
	589	if (getRefCount() <= 1)
	590	delete this;
	591	else
	592	decRefCount();
	593	return dummy;
	594	}
	595	if ( getRefCount() <= 1 )
	596	{
	597	delete this;
	598	return dummy;
	599	}
	600	else
	601	{
	602	decRefCount();
	603	return dummy;
	604	}
	605	}
	606	InternalPoly aPoly = (InternalPoly)aCoeff;
	607	termList dummy, first, last, resultfirst = 0, resultlast = 0;
	608	CanonicalForm coeff, newcoeff;
	609	int exp, newexp;
	610	bool singleObject;
	611
	612	if ( getRefCount() <= 1 )
	613	{
	614	first = firstTerm; last = lastTerm; singleObject = true;
	615	}
	616	else
	617	{
	618	first = copyTermList( firstTerm, last ); singleObject = false;
	619	decRefCount();
	620	}
	621	coeff = aPoly->firstTerm->coeff;
	622	exp = aPoly->firstTerm->exp;
	623	while (first && ( first->exp >= exp ) )
	624	{
	625	newcoeff= first->coeff.tryDiv (coeff, M, fail);
	626	if (fail)
	627	{
	628	freeTermList (first);
	629	return CFFactory::basic (0);
	630	}
	631	newcoeff= reduce (newcoeff, M);
	632	newexp = first->exp - exp;
	633	dummy = first;
	634	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
	635	delete dummy;
	636	if (!newcoeff.isZero())
	637	appendTermList( resultfirst, resultlast, newcoeff, newexp );
	638	}
	639	freeTermList( first );
	640	if ( singleObject )
	641	{
	642	if ( resultfirst && resultfirst->exp != 0 )
	643	{
	644	firstTerm = resultfirst;
	645	lastTerm = resultlast;
	646	return this;
	647	}
	648	else if ( resultfirst )
	649	{
	650	InternalCF * res = resultfirst->coeff.getval();
	651	delete resultfirst;
	652	firstTerm = 0;
	653	delete this;
	654	return res;
	655	}
	656	else
	657	{
	658	// this should not happen (evtl use assertion)
	659	ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
	660	firstTerm = 0;
	661	delete this;
	662	return CFFactory::basic( 0 );
	663	}
	664	}
	665	else
	666	{
	667	if ( resultfirst && resultfirst->exp != 0 )
	668	return new InternalPoly( resultfirst, resultlast, var );
	669	else if ( resultfirst )
	670	{
	671	InternalCF * res = resultfirst->coeff.getval();
	672	delete resultfirst;
	673	return res;
	674	}
	675	else
	676	return CFFactory::basic( 0 );
	677	}
	678	}
	679
[2dd068]	680	InternalCF*
	681	InternalPoly::modulosame( InternalCF* aCoeff )
	682	{
	683	return modsame( aCoeff );
	684	}
	685
	686	InternalCF*
	687	InternalPoly::modsame( InternalCF* aCoeff )
	688	{
[4ccbc25]	689	if ( inExtension() && getReduce( var ) )
	690	{
[a29d092]	691	if ( deleteObject() ) delete this;
	692	return CFFactory::basic( 0 );
[2dd068]	693	}
	694	InternalPoly aPoly = (InternalPoly)aCoeff;
	695	termList dummy, first, last;
	696	CanonicalForm coeff, newcoeff;
	697	int exp, newexp;
	698	bool singleObject;
	699
[8ce2d8c]	700	if ( getRefCount() <= 1 )
[4ccbc25]	701	{
[a29d092]	702	first = firstTerm; last = lastTerm; singleObject = true;
[2dd068]	703	}
[4ccbc25]	704	else
	705	{
[a29d092]	706	first = copyTermList( firstTerm, last ); singleObject = false;
	707	decRefCount();
[2dd068]	708	}
	709	coeff = aPoly->firstTerm->coeff;
	710	exp = aPoly->firstTerm->exp;
[4ccbc25]	711	while (first && ( first->exp >= exp ) )
	712	{
[a29d092]	713	newcoeff = first->coeff / coeff;
	714	newexp = first->exp - exp;
	715	dummy = first;
	716	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
	717	delete dummy;
[2dd068]	718	}
[4ccbc25]	719	if ( singleObject )
	720	{
	721	if ( first && first->exp != 0 )
	722	{
[a29d092]	723	firstTerm = first;
	724	lastTerm = last;
	725	return this;
	726	}
[4ccbc25]	727	else if ( first )
	728	{
[a29d092]	729	InternalCF * res = first->coeff.getval();
	730	delete first;
	731	firstTerm = 0;
	732	delete this;
	733	return res;
	734	}
[4ccbc25]	735	else
	736	{
[a29d092]	737	firstTerm = 0;
	738	delete this;
	739	return CFFactory::basic( 0 );
	740	}
[2dd068]	741	}
[4ccbc25]	742	else
	743	{
[a29d092]	744	if ( first && first->exp != 0 )
	745	return new InternalPoly( first, last, var );
[4ccbc25]	746	else if ( first )
	747	{
[a29d092]	748	InternalCF * res = first->coeff.getval();
	749	delete first;
	750	return res;
	751	}
	752	else
	753	return CFFactory::basic( 0 );
[2dd068]	754	}
	755	}
	756
	757
	758	void
	759	InternalPoly::divremsame( InternalCF* acoeff, InternalCF& quot, InternalCF& rem )
	760	{
[4ccbc25]	761	if ( inExtension() && getReduce( var ) )
	762	{
[a29d092]	763	InternalCF * dummy = acoeff->invert();
	764	quot = dummy->mulsame( this );
	765	rem = CFFactory::basic( 0 );
[2dd068]	766	}
[4ccbc25]	767	else
	768	{
[a29d092]	769	InternalPoly aPoly = (InternalPoly)acoeff;
	770	termList dummy, first, last, resultfirst = 0, resultlast = 0;
	771	CanonicalForm coeff, newcoeff;
	772	int exp, newexp;
	773
	774	first = copyTermList( firstTerm, last );
	775
	776	coeff = aPoly->firstTerm->coeff;
	777	exp = aPoly->firstTerm->exp;
[4ccbc25]	778	while (first && ( first->exp >= exp ) )
	779	{
[a29d092]	780	newcoeff = first->coeff / coeff;
	781	newexp = first->exp - exp;
	782	dummy = first;
	783	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
	784	delete dummy;
	785	appendTermList( resultfirst, resultlast, newcoeff, newexp );
	786	}
	787	if ( resultfirst )
[4ccbc25]	788	if ( resultfirst->exp == 0 )
	789	{
[a29d092]	790	quot = resultfirst->coeff.getval();
	791	delete resultfirst;
	792	}
	793	else
	794	quot = new InternalPoly( resultfirst, resultlast, var );
	795	else
	796	quot = CFFactory::basic( 0 );
	797	if ( first )
[4ccbc25]	798	if ( first->exp == 0 )
	799	{
[a29d092]	800	rem = first->coeff.getval();
	801	delete first;
	802	}
	803	else
	804	rem = new InternalPoly( first, last, var );
	805	else
	806	rem = CFFactory::basic( 0 );
[2dd068]	807	}
	808	}
	809
	810	bool
	811	InternalPoly::divremsamet( InternalCF* acoeff, InternalCF& quot, InternalCF& rem )
	812	{
[4ccbc25]	813	if ( inExtension() && getReduce( var ) )
	814	{
[a29d092]	815	divremsame( acoeff, quot, rem );
	816	return true;
[2dd068]	817	}
	818	InternalPoly aPoly = (InternalPoly)acoeff;
	819	termList dummy, first, last, resultfirst = 0, resultlast = 0;
	820	CanonicalForm coeff, newcoeff, dummycoeff;
	821	int exp, newexp;
	822	bool divideok = true;
	823
	824	// if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
[a29d092]	825	// return false;
[2dd068]	826
	827	first = copyTermList( firstTerm, last );
	828
	829	coeff = aPoly->firstTerm->coeff;
	830	exp = aPoly->firstTerm->exp;
[4ccbc25]	831	while (first && ( first->exp >= exp ) && divideok )
	832	{
[6b503c]	833	divideok = divremt( first->coeff, coeff, newcoeff, dummycoeff );
[4ccbc25]	834	if ( divideok && dummycoeff.isZero() )
	835	{
[a29d092]	836	newexp = first->exp - exp;
	837	dummy = first;
	838	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
	839	delete dummy;
	840	appendTermList( resultfirst, resultlast, newcoeff, newexp );
	841	}
	842	else
	843	divideok = false;
[2dd068]	844	}
[4ccbc25]	845	if ( divideok )
	846	{
[a29d092]	847	if ( resultfirst )
[4ccbc25]	848	if ( resultfirst->exp == 0 )
	849	{
[a29d092]	850	quot = resultfirst->coeff.getval();
	851	delete resultfirst;
	852	}
	853	else
	854	quot = new InternalPoly( resultfirst, resultlast, var );
	855	else
	856	quot = CFFactory::basic( 0 );
	857	if ( first )
[4ccbc25]	858	if ( first->exp == 0 )
	859	{
[a29d092]	860	rem = first->coeff.getval();
	861	delete first;
	862	}
	863	else
	864	rem = new InternalPoly( first, last, var );
	865	else
	866	rem = CFFactory::basic( 0 );
[2dd068]	867	}
[4ccbc25]	868	else
	869	{
[a29d092]	870	freeTermList( resultfirst );
	871	freeTermList( first );
[2dd068]	872	}
	873	return divideok;
	874	}
	875
[ec970e]	876	bool
	877	InternalPoly::tryDivremsamet( InternalCF* acoeff, InternalCF& quot, InternalCF& rem, const CanonicalForm& M, bool& fail)
	878	{
	879	if (inExtension() && !getReduce (var))
	880	{
	881	InternalCF * dummy = acoeff->tryInvert(M, fail);
	882	if (fail)
	883	return false;
	884	quot = dummy->tryMulsame( this, M);
	885	rem = CFFactory::basic( 0 );
	886	if (fail)
	887	return false;
	888	return true;
	889	}
	890	InternalPoly aPoly = (InternalPoly)acoeff;
	891	termList dummy, first, last, resultfirst = 0, resultlast = 0;
	892	CanonicalForm coeff, newcoeff, dummycoeff;
	893	int exp, newexp;
	894	bool divideok = true;
	895
	896	first = copyTermList( firstTerm, last );
	897
	898	coeff = aPoly->firstTerm->coeff;
	899	exp = aPoly->firstTerm->exp;
	900	while (first && ( first->exp >= exp ) && divideok )
	901	{
	902	divideok = tryDivremt( first->coeff, coeff, newcoeff, dummycoeff, M, fail );
	903	if (fail)
	904	{
	905	freeTermList (first);
	906	return false;
	907	}
	908	if ( divideok && dummycoeff.isZero() )
	909	{
	910	newexp = first->exp - exp;
	911	dummy = first;
	912	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
	913	delete dummy;
	914	if (!newcoeff.isZero())
	915	appendTermList( resultfirst, resultlast, newcoeff, newexp );
	916	}
	917	else
	918	divideok = false;
	919	}
	920	if ( divideok )
	921	{
	922	if ( resultfirst )
	923	if ( resultfirst->exp == 0 )
	924	{
	925	quot = resultfirst->coeff.getval();
	926	delete resultfirst;
	927	}
	928	else
	929	quot = new InternalPoly( resultfirst, resultlast, var );
	930	else
	931	quot = CFFactory::basic( 0 );
	932	if ( first )
	933	if ( first->exp == 0 )
	934	{
	935	rem = first->coeff.getval();
	936	delete first;
	937	}
	938	else
	939	{
	940	if (first->coeff.isZero())
	941	{
	942	rem= CFFactory::basic (0);
	943	delete first;
	944	}
	945	else
	946	rem = new InternalPoly( first, last, var );
	947	}
	948	else
	949	rem = CFFactory::basic( 0 );
	950	}
	951	else
	952	{
	953	freeTermList( resultfirst );
	954	freeTermList( first );
	955	}
	956	return divideok;
	957	}
	958
[2085fc]	959	//{{{ int InternalPoly::comparesame, comparecoeff ( InternalCF * acoeff )
	960	//{{{ docu
	961	//
	962	// comparesame(), comparecoeff() - compare with an
	963	// InternalPoly.
	964	//
	965	// comparecoeff() always returns 1 since CO is defined to be
	966	// larger than anything which is a coefficient w.r.t. CO.
	967	//
	968	// comparesame() compares the coefficient vectors of f=CO and
	969	// g=acoeff w.r.t to a lexicographic order in the following way:
[a29d092]	970	// f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t.
[2085fc]	971	// i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and
	972	// ii) g[i] occurs in g (i.e. is not equal to zero) and
	973	// f[i] does not occur in f or f[i] < g[i] if f[i] occurs
	974	// where f[i] denotes the coefficient to the power x^i of f.
	975	//
	976	// As usual, comparesame() returns 1 if CO is larger than c, 0 if
	977	// CO equals c, and -1 if CO is less than c. However, this
	978	// function is optimized to test on equality since this is its
	979	// most important and frequent usage.
	980	//
	981	// See the respective `CanonicalForm'-methods for an explanation
	982	// why we define such a strange (but total) ordering on
	983	// polynomials.
	984	//
[7d9585]	985	// See also: CanonicalForm::operator <(), CanonicalForm::operator ==()
	986	//
[2085fc]	987	//}}}
[2dd068]	988	int
[2085fc]	989	InternalPoly::comparesame ( InternalCF * acoeff )
	990	{
	991	ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" );
	992	InternalPoly* apoly = (InternalPoly*)acoeff;
	993	// check on triviality
	994	if ( this == apoly )
[a29d092]	995	return 0;
[4ccbc25]	996	else
	997	{
[a29d092]	998	termList cursor1 = firstTerm;
	999	termList cursor2 = apoly->firstTerm;
	1000	for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next )
	1001	// we test on inequality of coefficients at this
	1002	// point instead of testing on "less than" at the
	1003	// last `else' in the enclosed `if' statement since a
	1004	// test on inequaltiy in general is cheaper
	1005	if ( (cursor1->exp != cursor2->exp) \|\| (cursor1->coeff != cursor2->coeff) )
[ac8e1a]	1006	{
[a29d092]	1007	if ( cursor1->exp > cursor2->exp )
	1008	return 1;
	1009	else if ( cursor1->exp < cursor2->exp )
	1010	return -1;
	1011	else if ( cursor1->coeff > cursor2->coeff )
	1012	return 1;
	1013	else
	1014	return -1;
[ac8e1a]	1015	}
[a29d092]	1016	// check trailing terms
	1017	if ( cursor1 == cursor2 )
	1018	return 0;
	1019	else if ( cursor1 != 0 )
	1020	return 1;
	1021	else
	1022	return -1;
[2085fc]	1023	}
	1024	}
	1025
	1026	int
	1027	InternalPoly::comparecoeff ( InternalCF * )
[2dd068]	1028	{
	1029	return 1;
	1030	}
[2085fc]	1031	//}}}
[2dd068]	1032
	1033	InternalCF*
	1034	InternalPoly::addcoeff( InternalCF* cc )
	1035	{
	1036	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
	1037	if ( c.isZero() )
[a29d092]	1038	return this;
[4ccbc25]	1039	else
	1040	{
[8ce2d8c]	1041	if ( getRefCount() <= 1 )
[4ccbc25]	1042	{
	1043	if ( lastTerm->exp == 0 )
	1044	{
[a29d092]	1045	lastTerm->coeff += c;
[4ccbc25]	1046	if ( lastTerm->coeff.isZero() )
	1047	{
[a29d092]	1048	termList cursor = firstTerm;
	1049	while ( cursor->next != lastTerm )
	1050	cursor = cursor->next;
	1051	delete lastTerm;
	1052	cursor->next = 0;
	1053	lastTerm = cursor;
	1054	}
	1055	}
[4ccbc25]	1056	else
	1057	{
[a29d092]	1058	lastTerm->next = new term( 0, c, 0 );
	1059	lastTerm = lastTerm->next;
	1060	}
	1061	return this;
	1062	}
[4ccbc25]	1063	else
	1064	{
[a29d092]	1065	decRefCount();
	1066	termList last, first = copyTermList( firstTerm, last, false );
[4ccbc25]	1067	if ( last->exp == 0 )
	1068	{
[a29d092]	1069	last->coeff += c;
[4ccbc25]	1070	if ( last->coeff.isZero() )
	1071	{
[a29d092]	1072	termList cursor = first;
	1073	while ( cursor->next != last )
	1074	cursor = cursor->next;
	1075	delete last;
	1076	cursor->next = 0;
	1077	last = cursor;
	1078	}
	1079	}
[4ccbc25]	1080	else
	1081	{
[a29d092]	1082	last->next = new term( 0, c, 0 );
	1083	last = last->next;
	1084	}
	1085	return new InternalPoly( first, last, var );
	1086	}
[2dd068]	1087	}
	1088	}
	1089
	1090	InternalCF*
	1091	InternalPoly::subcoeff( InternalCF* cc, bool negate )
	1092	{
	1093	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
	1094	if ( c.isZero() )
[4ccbc25]	1095	if ( getRefCount() > 1 )
	1096	{
[a29d092]	1097	decRefCount();
	1098	termList last, first = copyTermList( firstTerm, last, negate );
	1099	return new InternalPoly( first, last, var );
	1100	}
[4ccbc25]	1101	else
	1102	{
[a29d092]	1103	if ( negate )
	1104	negateTermList( firstTerm );
	1105	return this;
	1106	}
[4ccbc25]	1107	else
	1108	{
[8ce2d8c]	1109	if ( getRefCount() <= 1 )
[4ccbc25]	1110	{
	1111	if ( lastTerm->exp == 0 )
	1112	{
	1113	if ( negate )
	1114	{
[a29d092]	1115	negateTermList( firstTerm );
	1116	lastTerm->coeff += c;
	1117	}
	1118	else
	1119	lastTerm->coeff -= c;
[4ccbc25]	1120	if ( lastTerm->coeff.isZero() )
	1121	{
[a29d092]	1122	termList cursor = firstTerm;
	1123	while ( cursor->next != lastTerm )
	1124	cursor = cursor->next;
	1125	delete lastTerm;
	1126	cursor->next = 0;
	1127	lastTerm = cursor;
	1128	}
	1129	}
[4ccbc25]	1130	else
	1131	{
	1132	if ( negate )
	1133	{
[a29d092]	1134	negateTermList( firstTerm );
	1135	lastTerm->next = new term( 0, c, 0 );
	1136	}
	1137	else
	1138	lastTerm->next = new term( 0, -c, 0 );
	1139	lastTerm = lastTerm->next;
	1140	}
	1141	return this;
	1142	}
[4ccbc25]	1143	else
	1144	{
[a29d092]	1145	decRefCount();
	1146	termList last, first = copyTermList( firstTerm, last, negate );
[4ccbc25]	1147	if ( last->exp == 0 )
	1148	{
[a29d092]	1149	if ( negate )
	1150	last->coeff += c;
	1151	else
	1152	last->coeff -= c;
[4ccbc25]	1153	if ( last->coeff.isZero() )
	1154	{
[a29d092]	1155	termList cursor = first;
	1156	while ( cursor->next != last )
	1157	cursor = cursor->next;
	1158	delete last;
	1159	cursor->next = 0;
	1160	last = cursor;
	1161	}
	1162	}
[4ccbc25]	1163	else
	1164	{
[a29d092]	1165	if ( negate )
	1166	last->next = new term( 0, c, 0 );
	1167	else
	1168	last->next = new term( 0, -c, 0 );
	1169	last = last->next;
	1170	}
	1171	return new InternalPoly( first, last, var );
	1172	}
[2dd068]	1173	}
	1174	}
	1175
	1176	InternalCF*
	1177	InternalPoly::mulcoeff( InternalCF* cc )
	1178	{
	1179	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
[4ccbc25]	1180	if ( c.isZero() )
	1181	{
[8ce2d8c]	1182	if ( getRefCount() <= 1 )
[4ccbc25]	1183	{
[a29d092]	1184	delete this;
	1185	return CFFactory::basic( 0 );
	1186	}
[4ccbc25]	1187	else
	1188	{
[a29d092]	1189	decRefCount();
	1190	return CFFactory::basic( 0 );
	1191	}
[2dd068]	1192	}
	1193	else if ( c.isOne() )
[a29d092]	1194	return this;
[4ccbc25]	1195	else
	1196	{
[8ce2d8c]	1197	if ( getRefCount() <= 1 )
[4ccbc25]	1198	{
[a29d092]	1199	mulTermList( firstTerm, c, 0 );
	1200	return this;
	1201	}
[4ccbc25]	1202	else
	1203	{
[a29d092]	1204	decRefCount();
	1205	termList last, first = copyTermList( firstTerm, last );
	1206	mulTermList( first, c, 0 );
	1207	return new InternalPoly( first, last, var );
	1208	}
[2dd068]	1209	}
	1210	}
	1211
	1212	InternalCF*
[fc732a9]	1213	InternalPoly::dividecoeff( InternalCF* cc, bool invert )
[2dd068]	1214	{
[fc732a9]	1215	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
[4ccbc25]	1216	if ( inExtension() && getReduce( var ) && invert )
	1217	{
[a29d092]	1218	InternalCF * dummy;
	1219	dummy = this->invert();
[4ccbc25]	1220	if (is_imm(dummy))
[778a4e]	1221	{
	1222	if (is_imm(cc))
	1223	{
	1224	InternalInteger d=new InternalInteger(imm2int(dummy)imm2int(cc));
	1225	dummy=d;
	1226	}
	1227	else
	1228	dummy=cc->mulcoeff(dummy);
	1229	}
	1230	else dummy = dummy->mulcoeff( cc );
[8ce2d8c]	1231	if ( getRefCount() <= 1 )
[4ccbc25]	1232	{
[a29d092]	1233	delete this;
	1234	return dummy;
	1235	}
[4ccbc25]	1236	else
	1237	{
[a29d092]	1238	decRefCount();
	1239	return dummy;
	1240	}
[fc732a9]	1241	}
	1242	if ( invert )
[ac8e1a]	1243	{
[8ce2d8c]	1244	if ( getRefCount() <= 1 )
[4ccbc25]	1245	{
[a29d092]	1246	delete this;
	1247	return CFFactory::basic( 0 );
	1248	}
[4ccbc25]	1249	else
	1250	{
[a29d092]	1251	decRefCount();
	1252	return CFFactory::basic( 0 );
	1253	}
[ac8e1a]	1254	}
[fc732a9]	1255	if ( c.isOne() )
[a29d092]	1256	return this;
[4ccbc25]	1257	else
	1258	{
[8ce2d8c]	1259	if ( getRefCount() <= 1 )
[4ccbc25]	1260	{
[a29d092]	1261	firstTerm = divideTermList( firstTerm, c, lastTerm );
	1262	if ( firstTerm && firstTerm->exp != 0 )
	1263	return this;
[4ccbc25]	1264	else if ( firstTerm )
	1265	{
[a29d092]	1266	InternalCF * res = firstTerm->coeff.getval();
	1267	delete this;
	1268	return res;
	1269	}
[4ccbc25]	1270	else
	1271	{
[a29d092]	1272	delete this;
	1273	return CFFactory::basic( 0 );
	1274	}
	1275	}
[4ccbc25]	1276	else
	1277	{
[a29d092]	1278	decRefCount();
	1279	termList last, first = copyTermList( firstTerm, last );
	1280	first = divideTermList( first, c, last );
	1281	if ( first && first->exp != 0 )
	1282	return new InternalPoly( first, last, var );
[4ccbc25]	1283	else if ( first )
	1284	{
[a29d092]	1285	InternalCF * res = first->coeff.getval();
	1286	delete first;
	1287	return res;
	1288	}
[4ccbc25]	1289	else
	1290	{
[a29d092]	1291	delete first;
	1292	return CFFactory::basic( 0 );
	1293	}
	1294	}
[fc732a9]	1295	}
[2dd068]	1296	}
	1297
[ec970e]	1298	InternalCF*
	1299	InternalPoly::tryDividecoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail )
	1300	{
	1301	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
	1302	if ( inExtension() && !getReduce( var ) && invert )
	1303	{
	1304	InternalCF * dummy;
	1305	dummy = this->tryInvert(M, fail);
	1306	if (fail)
	1307	{
	1308	if (getRefCount() <= 1)
	1309	delete this;
	1310	else
	1311	decRefCount();
	1312	return dummy; //is equal to CFFactory::basic (0) in this case
	1313	}
	1314	if (is_imm(dummy))
	1315	{
	1316	if (is_imm(cc))
	1317	{
	1318	InternalInteger d=new InternalInteger(imm2int(dummy)imm2int(cc));
	1319	dummy=d;
	1320	}
	1321	else
	1322	dummy=cc->mulcoeff(dummy);
	1323	}
	1324	else dummy = dummy->mulcoeff( cc );
	1325	if ( getRefCount() <= 1 )
	1326	{
	1327	delete this;
	1328	return dummy;
	1329	}
	1330	else
	1331	{
	1332	decRefCount();
	1333	return dummy;
	1334	}
	1335	}
	1336	if ( invert )
	1337	{
	1338	if ( getRefCount() <= 1 )
	1339	{
	1340	delete this;
	1341	return CFFactory::basic( 0 );
	1342	}
	1343	else
	1344	{
	1345	decRefCount();
	1346	return CFFactory::basic( 0 );
	1347	}
	1348	}
	1349	if ( c.isOne() )
	1350	return this;
	1351	//one should never get here
	1352	else
	1353	{
	1354	if ( getRefCount() <= 1 )
	1355	{
	1356	firstTerm = divideTermList( firstTerm, c, lastTerm );
	1357	if ( firstTerm && firstTerm->exp != 0 )
	1358	return this;
	1359	else if ( firstTerm )
	1360	{
	1361	InternalCF * res = firstTerm->coeff.getval();
	1362	delete this;
	1363	return res;
	1364	}
	1365	else
	1366	{
	1367	delete this;
	1368	return CFFactory::basic( 0 );
	1369	}
	1370	}
	1371	else
	1372	{
	1373	decRefCount();
	1374	termList last, first = copyTermList( firstTerm, last );
	1375	first = divideTermList( first, c, last );
	1376	if ( first && first->exp != 0 )
	1377	return new InternalPoly( first, last, var );
	1378	else if ( first )
	1379	{
	1380	InternalCF * res = first->coeff.getval();
	1381	delete first;
	1382	return res;
	1383	}
	1384	else
	1385	{
	1386	delete first;
	1387	return CFFactory::basic( 0 );
	1388	}
	1389	}
	1390	}
	1391	}
	1392
	1393
[2dd068]	1394	InternalCF*
	1395	InternalPoly::divcoeff( InternalCF* cc, bool invert )
	1396	{
	1397	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
[4ccbc25]	1398	if ( inExtension() && getReduce( var ) && invert )
	1399	{
[a29d092]	1400	InternalCF * dummy;
	1401	dummy = this->invert();
	1402	dummy = dummy->mulcoeff( cc );
[8ce2d8c]	1403	if ( getRefCount() <= 1 )
[4ccbc25]	1404	{
[a29d092]	1405	delete this;
	1406	return dummy;
	1407	}
[4ccbc25]	1408	else
	1409	{
[a29d092]	1410	decRefCount();
	1411	return dummy;
	1412	}
[2dd068]	1413	}
	1414	if ( invert )
[ac8e1a]	1415	{
[8ce2d8c]	1416	if ( getRefCount() <= 1 )
[4ccbc25]	1417	{
[a29d092]	1418	delete this;
	1419	return CFFactory::basic( 0 );
	1420	}
[4ccbc25]	1421	else
	1422	{
[a29d092]	1423	decRefCount();
	1424	return CFFactory::basic( 0 );
	1425	}
[ac8e1a]	1426	}
[2dd068]	1427	if ( c.isOne() )
[a29d092]	1428	return this;
[4ccbc25]	1429	else
	1430	{
[8ce2d8c]	1431	if ( getRefCount() <= 1 )
[4ccbc25]	1432	{
[a29d092]	1433	firstTerm = divTermList( firstTerm, c, lastTerm );
	1434	if ( firstTerm && firstTerm->exp != 0 )
	1435	return this;
[4ccbc25]	1436	else if ( firstTerm )
	1437	{
[a29d092]	1438	InternalCF * res = firstTerm->coeff.getval();
	1439	delete this;
	1440	return res;
	1441	}
[4ccbc25]	1442	else
	1443	{
[a29d092]	1444	delete this;
	1445	return CFFactory::basic( 0 );
	1446	}
	1447	}
[4ccbc25]	1448	else
	1449	{
[a29d092]	1450	decRefCount();
	1451	termList last, first = copyTermList( firstTerm, last );
	1452	first = divTermList( first, c, last );
	1453	if ( first && first->exp != 0 )
	1454	return new InternalPoly( first, last, var );
[4ccbc25]	1455	else if ( first )
	1456	{
[a29d092]	1457	InternalCF * res = first->coeff.getval();
	1458	delete first;
	1459	return res;
	1460	}
[4ccbc25]	1461	else
	1462	{
[a29d092]	1463	delete first;
	1464	return CFFactory::basic( 0 );
	1465	}
	1466	}
[2dd068]	1467	}
	1468	}
	1469
[ec970e]	1470	InternalCF*
	1471	InternalPoly::tryDivcoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail )
	1472	{
	1473	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
	1474	if ( inExtension() && !getReduce( var ) && invert )
	1475	{
	1476	InternalCF * dummy;
	1477	dummy = this->tryInvert(M, fail);
	1478	if (fail)
	1479	{
	1480	if (getRefCount() <= 1)
	1481	delete this;
	1482	else
	1483	decRefCount();
	1484	return dummy;
	1485	}
	1486	dummy = dummy->mulcoeff( cc );
	1487	if ( getRefCount() <= 1 )
	1488	{
	1489	delete this;
	1490	return dummy;
	1491	}
	1492	else
	1493	{
	1494	decRefCount();
	1495	return dummy;
	1496	}
	1497	}
	1498	if ( invert )
	1499	{
	1500	if ( getRefCount() <= 1 )
	1501	{
	1502	delete this;
	1503	return CFFactory::basic( 0 );
	1504	}
	1505	else
	1506	{
	1507	decRefCount();
	1508	return CFFactory::basic( 0 );
	1509	}
	1510	}
	1511	if ( c.isOne() )
	1512	return this;
	1513	else
	1514	{
	1515	if ( getRefCount() <= 1 )
	1516	{
	1517	firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail );
	1518	if (fail)
	1519	{
	1520	delete this;
	1521	return CFFactory::basic (0);
	1522	}
	1523	if ( firstTerm && firstTerm->exp != 0 )
	1524	return this;
	1525	else if ( firstTerm )
	1526	{
	1527	InternalCF * res = firstTerm->coeff.getval();
	1528	delete this;
	1529	return res;
	1530	}
	1531	else
	1532	{
	1533	delete this;
	1534	return CFFactory::basic( 0 );
	1535	}
	1536	}
	1537	else
	1538	{
	1539	decRefCount();
	1540	termList last, first = copyTermList( firstTerm, last );
	1541	first = tryDivTermList( first, c, last, M, fail );
	1542	if (fail)
	1543	{
	1544	delete this;
	1545	return CFFactory::basic (0);
	1546	}
	1547	if (fail)
	1548	{
	1549	delete first;
	1550	return CFFactory::basic (0);
	1551	}
	1552	if ( first && first->exp != 0 )
	1553	return new InternalPoly( first, last, var );
	1554	else if ( first )
	1555	{
	1556	InternalCF * res = first->coeff.getval();
	1557	delete first;
	1558	return res;
	1559	}
	1560	else
	1561	{
	1562	delete first;
	1563	return CFFactory::basic( 0 );
	1564	}
	1565	}
	1566	}
	1567	}
	1568
[2dd068]	1569	InternalCF*
	1570	InternalPoly::modulocoeff( InternalCF* cc, bool invert )
	1571	{
	1572	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
[4ccbc25]	1573	if ( invert )
	1574	{
[a29d092]	1575	if ( deleteObject() ) delete this;
	1576	return c.getval();
[2dd068]	1577	}
	1578	ASSERT( ! c.isZero(), "divide by zero!" );
	1579	if ( deleteObject() ) delete this;
	1580	return CFFactory::basic( 0 );
	1581	}
	1582
	1583	InternalCF*
	1584	InternalPoly::modcoeff( InternalCF* cc, bool invert )
	1585	{
	1586	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
[4ccbc25]	1587	if ( invert )
	1588	{
[a29d092]	1589	if ( deleteObject() ) delete this;
	1590	return c.getval();
[2dd068]	1591	}
	1592	ASSERT( ! c.isZero(), "divide by zero!" );
[4ccbc25]	1593	if ( c.isOne() )
	1594	{
[8ce2d8c]	1595	if ( getRefCount() <= 1 )
[4ccbc25]	1596	{
[2dd068]	1597	delete this;
	1598	return CFFactory::basic( 0 );
	1599	}
[4ccbc25]	1600	else
	1601	{
[2dd068]	1602	decRefCount();
	1603	return CFFactory::basic( 0 );
	1604	}
	1605	}
[4ccbc25]	1606	else
	1607	{
[8ce2d8c]	1608	if ( getRefCount() <= 1 )
[4ccbc25]	1609	{
[2dd068]	1610	firstTerm = modTermList( firstTerm, c, lastTerm );
	1611	if ( firstTerm && firstTerm->exp != 0 )
	1612	return this;
[4ccbc25]	1613	else if ( firstTerm )
	1614	{
[2dd068]	1615	InternalCF * res = firstTerm->coeff.getval();
	1616	delete this;
	1617	return res;
	1618	}
[4ccbc25]	1619	else
	1620	{
[2dd068]	1621	delete this;
	1622	return CFFactory::basic( 0 );
	1623	}
	1624	}
[4ccbc25]	1625	else
	1626	{
[2dd068]	1627	decRefCount();
	1628	termList last, first = copyTermList( firstTerm, last );
	1629	first = modTermList( first, c, last );
	1630	if ( first && first->exp != 0 )
	1631	return new InternalPoly( first, last, var );
[4ccbc25]	1632	else if ( first )
	1633	{
[2dd068]	1634	InternalCF * res = first->coeff.getval();
	1635	delete first;
	1636	return res;
	1637	}
[4ccbc25]	1638	else
	1639	{
[2dd068]	1640	delete first;
	1641	return CFFactory::basic( 0 );
	1642	}
	1643	}
	1644	}
	1645	}
	1646
	1647	void
	1648	InternalPoly::divremcoeff( InternalCF* cc, InternalCF& quot, InternalCF& rem, bool invert )
	1649	{
[4ccbc25]	1650	if ( inExtension() && getReduce( var ) )
	1651	{
[a29d092]	1652	quot = copyObject();
	1653	quot = quot->dividecoeff( cc, invert );
	1654	rem = CFFactory::basic( 0 );
[2dd068]	1655	}
[4ccbc25]	1656	else if ( invert )
	1657	{
[a29d092]	1658	if ( is_imm( cc ) )
	1659	rem = cc;
	1660	else
	1661	rem = cc->copyObject();
	1662	quot = CFFactory::basic( 0 );
[2dd068]	1663	}
[4ccbc25]	1664	else
	1665	{
[a29d092]	1666	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
	1667	ASSERT( ! c.isZero(), "divide by zero!" );
	1668	termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
	1669	quotfirst = divideTermList( quotfirst, c, quotlast );
	1670	if ( quotfirst )
[4ccbc25]	1671	if ( quotfirst->exp == 0 )
	1672	{
[a29d092]	1673	quot = quotfirst->coeff.getval();
	1674	delete quotfirst;
	1675	}
	1676	else
	1677	quot = new InternalPoly( quotfirst, quotlast, var );
	1678	else
	1679	quot = CFFactory::basic( 0 );
	1680	rem = CFFactory::basic( 0 );
[2dd068]	1681	}
	1682	}
	1683
	1684	bool
	1685	InternalPoly::divremcoefft( InternalCF* cc, InternalCF& quot, InternalCF& rem, bool invert )
	1686	{
[4ccbc25]	1687	if ( inExtension() && getReduce( var ) )
	1688	{
[a29d092]	1689	quot = copyObject();
	1690	quot = quot->dividecoeff( cc, invert );
	1691	rem = CFFactory::basic( 0 );
	1692	return true;
[2dd068]	1693	}
[4ccbc25]	1694	else if ( invert )
	1695	{
[a29d092]	1696	if ( is_imm( cc ) )
	1697	rem = cc;
	1698	else
	1699	rem = cc->copyObject();
	1700	quot = CFFactory::basic( 0 );
	1701	return true;
[2dd068]	1702	}
	1703	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
	1704	ASSERT( ! c.isZero(), "divide by zero!" );
	1705	termList quotfirst, quotcursor;
	1706	termList cursor;
	1707	CanonicalForm cquot, crem;
	1708	bool divideok = true;
	1709
	1710	cursor = firstTerm;
	1711	quotcursor = quotfirst = new term;
	1712
[4ccbc25]	1713	while ( cursor && divideok )
	1714	{
[6b503c]	1715	divideok = divremt( cursor->coeff, c, cquot, crem );
[a29d092]	1716	divideok = divideok && crem.isZero();
[4ccbc25]	1717	if ( divideok )
	1718	{
	1719	if ( ! cquot.isZero() )
	1720	{
[a29d092]	1721	quotcursor->next = new term( 0, cquot, cursor->exp );
	1722	quotcursor = quotcursor->next;
	1723	}
	1724	cursor = cursor->next;
	1725	}
[2dd068]	1726	}
	1727	quotcursor->next = 0;
[4ccbc25]	1728	if ( divideok )
	1729	{
[a29d092]	1730	cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
	1731	if ( quotfirst )
[4ccbc25]	1732	if ( quotfirst->exp == 0 )
	1733	{
[a29d092]	1734	quot = quotfirst->coeff.getval();
	1735	delete quotfirst;
	1736	}
	1737	else
	1738	quot = new InternalPoly( quotfirst, quotcursor, var );
	1739	else
	1740	quot = CFFactory::basic( 0 );
	1741	rem = CFFactory::basic( 0 );
[2dd068]	1742	}
[4ccbc25]	1743	else
	1744	{
[a29d092]	1745	freeTermList( quotfirst );
[2dd068]	1746	}
	1747	return divideok;
	1748	}
	1749
[ec970e]	1750	bool
	1751	InternalPoly::tryDivremcoefft( InternalCF* cc, InternalCF& quot, InternalCF& rem, bool invert, const CanonicalForm& M, bool& fail )
	1752	{
	1753	if ( inExtension() && !getReduce( var ) )
	1754	{
	1755	quot = copyObject();
	1756	quot = quot->tryDividecoeff( cc, invert, M, fail );
	1757	if (fail)
	1758	return false;
	1759	rem = CFFactory::basic( 0 );
	1760	return true;
	1761	}
	1762	else if ( invert )
	1763	{
	1764	if ( is_imm( cc ) )
	1765	rem = cc;
	1766	else
	1767	rem = cc->copyObject();
	1768	quot = CFFactory::basic( 0 );
	1769	return true;
	1770	}
	1771	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
	1772	ASSERT( ! c.isZero(), "divide by zero!" );
	1773	termList quotfirst, quotcursor;
	1774	termList cursor;
	1775	CanonicalForm cquot, crem;
	1776	bool divideok = true;
	1777
	1778	cursor = firstTerm;
	1779	quotcursor = quotfirst = new term;
	1780
	1781	while ( cursor && divideok )
	1782	{
	1783	divideok = tryDivremt( cursor->coeff, c, cquot, crem, M, fail );
	1784	if (fail)
	1785	{
	1786	freeTermList (quotfirst);
	1787	return false;
	1788	}
	1789	divideok = divideok && crem.isZero();
	1790	if ( divideok )
	1791	{
	1792	if ( ! cquot.isZero() )
	1793	{
	1794	quotcursor->next = new term( 0, cquot, cursor->exp );
	1795	quotcursor = quotcursor->next;
	1796	}
	1797	cursor = cursor->next;
	1798	}
	1799	}
	1800	quotcursor->next = 0;
	1801	if ( divideok )
	1802	{
	1803	cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
	1804	if ( quotfirst )
	1805	if ( quotfirst->exp == 0 )
	1806	{
	1807	quot = quotfirst->coeff.getval();
	1808	delete quotfirst;
	1809	}
	1810	else
	1811	quot = new InternalPoly( quotfirst, quotcursor, var );
	1812	else
	1813	quot = CFFactory::basic( 0 );
	1814	rem = CFFactory::basic( 0 );
	1815	}
	1816	else
	1817	{
	1818	freeTermList( quotfirst );
	1819	}
	1820	return divideok;
	1821	}
	1822
[2dd068]	1823	// static functions
	1824
	1825	termList
	1826	InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
	1827	{
[32e9cd7]	1828	if ( aTermList == 0 )
[a29d092]	1829	return 0;
[1e6de6]	1830	else if ( negate )
	1831	{
[a29d092]	1832	termList sourceCursor = aTermList;
	1833	termList dummy = new term;
	1834	termList targetCursor = dummy;
	1835
[1e6de6]	1836	while ( sourceCursor )
	1837	{
[a29d092]	1838	targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
	1839	targetCursor = targetCursor->next;
	1840	sourceCursor = sourceCursor->next;
	1841	}
	1842	targetCursor->next = 0;
	1843	theLastTerm = targetCursor;
	1844	targetCursor = dummy->next;
	1845	delete dummy;
	1846	return targetCursor;
[2dd068]	1847	}
[1e6de6]	1848	else
	1849	{
[a29d092]	1850	termList sourceCursor = aTermList;
	1851	termList dummy = new term;
	1852	termList targetCursor = dummy;
	1853
[1e6de6]	1854	while ( sourceCursor )
	1855	{
[a29d092]	1856	targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
	1857	targetCursor = targetCursor->next;
	1858	sourceCursor = sourceCursor->next;
	1859	}
	1860	targetCursor->next = 0;
	1861	theLastTerm = targetCursor;
	1862	targetCursor = dummy->next;
	1863	delete dummy;
	1864	return targetCursor;
[2dd068]	1865	}
	1866	}
	1867
	1868	termList
	1869	InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
	1870	{
[32e9cd7]	1871	if ( aTermList == 0 )
[a29d092]	1872	return 0;
[1e6de6]	1873	else
	1874	{
[a29d092]	1875	termList sourceCursor = aTermList;
	1876	termList dummy = new term;
	1877	termList targetCursor = dummy;
	1878
[1e6de6]	1879	while ( sourceCursor )
	1880	{
[a29d092]	1881	targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
	1882	targetCursor = targetCursor->next;
	1883	sourceCursor = sourceCursor->next;
	1884	}
	1885	targetCursor->next = 0;
	1886	theLastTerm = targetCursor;
	1887	targetCursor = dummy->next;
	1888	delete dummy;
	1889	return targetCursor;
[2dd068]	1890	}
	1891	}
	1892
	1893	void
	1894	InternalPoly::freeTermList ( termList aTermList )
	1895	{
	1896	termList cursor = aTermList;
	1897
[1e6de6]	1898	while ( cursor )
	1899	{
[a29d092]	1900	cursor = cursor->next;
	1901	delete aTermList;
	1902	aTermList = cursor;
[2dd068]	1903	}
	1904	}
	1905
	1906	void
	1907	InternalPoly::negateTermList ( termList terms )
	1908	{
	1909	termList cursor = terms;
[1e6de6]	1910	while ( cursor )
	1911	{
[a29d092]	1912	cursor->coeff = -cursor->coeff;
	1913	cursor = cursor->next;
[2dd068]	1914	}
	1915	}
	1916
	1917	termList
	1918	InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
	1919	{
	1920	termList theCursor = theList;
	1921	termList aCursor = aList;
	1922	termList predCursor = 0;
	1923
[1e6de6]	1924	while ( theCursor && aCursor )
	1925	{
	1926	if ( theCursor->exp == aCursor->exp )
	1927	{
[a29d092]	1928	if ( negate )
	1929	theCursor->coeff -= aCursor->coeff;
	1930	else
	1931	theCursor->coeff += aCursor->coeff;
[1e6de6]	1932	if ( theCursor->coeff.isZero() )
	1933	{
	1934	if ( predCursor )
	1935	{
[a29d092]	1936	predCursor->next = theCursor->next;
	1937	delete theCursor;
	1938	theCursor = predCursor->next;
	1939	}
[1e6de6]	1940	else
	1941	{
[a29d092]	1942	theList = theList->next;
	1943	delete theCursor;
	1944	theCursor = theList;
	1945	}
	1946	}
[1e6de6]	1947	else
	1948	{
[a29d092]	1949	predCursor = theCursor;
	1950	theCursor = theCursor->next;
	1951	}
	1952	aCursor = aCursor->next;
	1953	}
[1e6de6]	1954	else if ( theCursor->exp < aCursor->exp )
	1955	{
[a29d092]	1956	if ( negate )
[1e6de6]	1957	if ( predCursor )
	1958	{
[a29d092]	1959	predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
	1960	predCursor = predCursor->next;
	1961	}
[1e6de6]	1962	else
	1963	{
[a29d092]	1964	theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
	1965	predCursor = theList;
	1966	}
	1967	else
[1e6de6]	1968	if ( predCursor )
	1969	{
[a29d092]	1970	predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
	1971	predCursor = predCursor->next;
	1972	}
[1e6de6]	1973	else
	1974	{
[a29d092]	1975	theList = new term( theCursor, aCursor->coeff, aCursor->exp );
	1976	predCursor = theList;
	1977	}
	1978	aCursor = aCursor->next;
	1979	}
[1e6de6]	1980	else
	1981	{
[a29d092]	1982	predCursor = theCursor;
	1983	theCursor = theCursor->next;
	1984	}
[2dd068]	1985	}
[1e6de6]	1986	if ( aCursor )
	1987	{
[a29d092]	1988	if ( predCursor )
	1989	predCursor->next = copyTermList( aCursor, lastTerm, negate );
	1990	else
	1991	theList = copyTermList( aCursor, lastTerm, negate );
[2dd068]	1992	}
	1993	else if ( ! theCursor )
[a29d092]	1994	lastTerm = predCursor;
[2dd068]	1995
	1996	return theList;
	1997	}
	1998
	1999	void
	2000	InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
	2001	{
[1e6de6]	2002	while ( theCursor )
	2003	{
[a29d092]	2004	theCursor->coeff *= coeff;
	2005	theCursor->exp += exp;
	2006	theCursor = theCursor->next;
[2dd068]	2007	}
	2008	}
	2009
	2010	termList
[fc732a9]	2011	InternalPoly::divideTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
[2dd068]	2012	{
	2013	termList theCursor = firstTerm;
	2014	lastTerm = 0;
	2015	termList dummy;
	2016
[1e6de6]	2017	while ( theCursor )
	2018	{
[a29d092]	2019	theCursor->coeff /= coeff;
[1e6de6]	2020	if ( theCursor->coeff.isZero() )
	2021	{
[a29d092]	2022	if ( theCursor == firstTerm )
	2023	firstTerm = theCursor->next;
	2024	else
	2025	lastTerm->next = theCursor->next;
	2026	dummy = theCursor;
	2027	theCursor = theCursor->next;
	2028	delete dummy;
	2029	}
[1e6de6]	2030	else
	2031	{
[a29d092]	2032	lastTerm = theCursor;
	2033	theCursor = theCursor->next;
	2034	}
[fc732a9]	2035	}
	2036	return firstTerm;
	2037	}
	2038
	2039	termList
	2040	InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
	2041	{
	2042	termList theCursor = firstTerm;
	2043	lastTerm = 0;
	2044	termList dummy;
	2045
[1e6de6]	2046	while ( theCursor )
	2047	{
[a29d092]	2048	theCursor->coeff.div( coeff );
[1e6de6]	2049	if ( theCursor->coeff.isZero() )
	2050	{
[a29d092]	2051	if ( theCursor == firstTerm )
	2052	firstTerm = theCursor->next;
	2053	else
	2054	lastTerm->next = theCursor->next;
	2055	dummy = theCursor;
	2056	theCursor = theCursor->next;
	2057	delete dummy;
	2058	}
[1e6de6]	2059	else
	2060	{
[a29d092]	2061	lastTerm = theCursor;
	2062	theCursor = theCursor->next;
	2063	}
[2dd068]	2064	}
	2065	return firstTerm;
	2066	}
	2067
[ec970e]	2068	termList
	2069	InternalPoly::tryDivTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm, const CanonicalForm& M, bool& fail )
	2070	{
	2071	termList theCursor = firstTerm;
	2072	lastTerm = 0;
	2073	termList dummy;
	2074
	2075	while ( theCursor )
	2076	{
	2077	theCursor->coeff.tryDiv( coeff, M, fail );
	2078	if (fail)
	2079	return 0;
	2080	if ( theCursor->coeff.isZero() )
	2081	{
	2082	if ( theCursor == firstTerm )
	2083	firstTerm = theCursor->next;
	2084	else
	2085	lastTerm->next = theCursor->next;
	2086	dummy = theCursor;
	2087	theCursor = theCursor->next;
	2088	delete dummy;
	2089	}
	2090	else
	2091	{
	2092	lastTerm = theCursor;
	2093	theCursor = theCursor->next;
	2094	}
	2095	}
	2096	return firstTerm;
	2097	}
	2098
[2dd068]	2099	termList
	2100	InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
	2101	{
	2102	termList theCursor = firstTerm;
	2103	lastTerm = 0;
	2104	termList dummy;
	2105
[1e6de6]	2106	while ( theCursor )
	2107	{
[a29d092]	2108	theCursor->coeff.mod( coeff );
[1e6de6]	2109	if ( theCursor->coeff.isZero() )
	2110	{
[a29d092]	2111	if ( theCursor == firstTerm )
	2112	firstTerm = theCursor->next;
	2113	else
	2114	lastTerm->next = theCursor->next;
	2115	dummy = theCursor;
	2116	theCursor = theCursor-> next;
	2117	delete dummy;
	2118	}
[1e6de6]	2119	else
	2120	{
[a29d092]	2121	lastTerm = theCursor;
	2122	theCursor = theCursor->next;
	2123	}
[2dd068]	2124	}
	2125	return firstTerm;
	2126	}
	2127
	2128	void
	2129	InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
	2130	{
[1e6de6]	2131	if ( last )
	2132	{
[a29d092]	2133	last->next = new term( 0, coeff, exp );
	2134	last = last->next;
[2dd068]	2135	}
[1e6de6]	2136	else
	2137	{
[a29d092]	2138	first = new term( 0, coeff, exp );
	2139	last = first;
[2dd068]	2140	}
	2141	}
	2142
	2143	termList
	2144	InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
	2145	{
	2146	termList theCursor = theList;
	2147	termList aCursor = aList;
	2148	termList predCursor = 0;
	2149	CanonicalForm coeff;
	2150
	2151	if ( negate )
[a29d092]	2152	coeff = -c;
[2dd068]	2153	else
[a29d092]	2154	coeff = c;
[2dd068]	2155
[1e6de6]	2156	while ( theCursor && aCursor )
	2157	{
	2158	if ( theCursor->exp == aCursor->exp + exp )
	2159	{
[a29d092]	2160	theCursor->coeff += aCursor->coeff * coeff;
[1e6de6]	2161	if ( theCursor->coeff.isZero() )
	2162	{
	2163	if ( predCursor )
	2164	{
[a29d092]	2165	predCursor->next = theCursor->next;
	2166	delete theCursor;
	2167	theCursor = predCursor->next;
	2168	}
[1e6de6]	2169	else
	2170	{
[a29d092]	2171	theList = theList->next;
	2172	delete theCursor;
	2173	theCursor = theList;
	2174	}
	2175	}
[1e6de6]	2176	else
	2177	{
[a29d092]	2178	predCursor = theCursor;
	2179	theCursor = theCursor->next;
	2180	}
	2181	aCursor = aCursor->next;
	2182	}
[1e6de6]	2183	else if ( theCursor->exp < aCursor->exp + exp )
	2184	{
	2185	if ( predCursor )
	2186	{
[a29d092]	2187	predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
	2188	predCursor = predCursor->next;
	2189	}
[1e6de6]	2190	else
	2191	{
[a29d092]	2192	theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
	2193	predCursor = theList;
	2194	}
	2195	aCursor = aCursor->next;
	2196	}
[1e6de6]	2197	else
	2198	{
[a29d092]	2199	predCursor = theCursor;
	2200	theCursor = theCursor->next;
	2201	}
[2dd068]	2202	}
[1e6de6]	2203	if ( aCursor )
	2204	{
	2205	if ( predCursor )
	2206	{
[a29d092]	2207	predCursor->next = copyTermList( aCursor, lastTerm );
	2208	predCursor = predCursor->next;
	2209	}
[1e6de6]	2210	else
	2211	{
[a29d092]	2212	theList = copyTermList( aCursor, lastTerm );
	2213	predCursor = theList;
	2214	}
[1e6de6]	2215	while ( predCursor )
	2216	{
[a29d092]	2217	predCursor->exp += exp;
	2218	predCursor->coeff *= coeff;
	2219	predCursor = predCursor->next;
	2220	}
[2dd068]	2221	}
	2222	else if ( ! theCursor )
[a29d092]	2223	lastTerm = predCursor;
[2dd068]	2224	return theList;
	2225	}
	2226
	2227	termList
	2228	InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
	2229	{
	2230	CanonicalForm coeff = redterms->coeff;
	2231	CanonicalForm newcoeff;
	2232	int newexp;
	2233	int exp = redterms->exp;
	2234	termList dummy;
[1e6de6]	2235	while ( first && ( first->exp >= exp ) )
	2236	{
[a29d092]	2237	newcoeff = first->coeff / coeff;
	2238	newexp = first->exp - exp;
	2239	dummy = first;
	2240	first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
	2241	delete dummy;
[2dd068]	2242	}
	2243	return first;
	2244	}
[ec970e]	2245

Note: See TracBrowser for help on using the repository browser.

Download in other formats: