Context Navigation

source: git/factory/int_poly.cc @ b761b9

spielwiese

Last change on this file since b761b9 was b761b9, checked in by Jens Schmidt <schmidt@…>, 27 years ago
* int_pp.cc, int_int.cc, int_rat.cc, int_poly.cc, int_cf.cc, canonicalform.cc (sign): doc fix git-svn-id: file:///usr/local/Singular/svn/trunk@700 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 29.8 KB

Line
1	/* emacs edit mode for this file is -- C++ -- */
2	/* $Id: int_poly.cc,v 1.5 1997-09-10 15:45:49 schmidt Exp $ */
3
4	#include <config.h>
5
6	#ifndef NOSTREAMIO
7	#include <string.h>
8	#include <strstream.h>
9	#endif /* NOSTREAMIO */
10
11	#include "assert.h"
12
13	#include "cf_defs.h"
14	#include "cf_factory.h"
15	#include "int_cf.h"
16	#include "int_poly.h"
17	#include "canonicalform.h"
18	#include "variable.h"
19	#include "imm.h"
20
21
22	InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
23	{
24	firstTerm = first;
25	lastTerm = last;
26	var = v;
27	}
28
29	InternalPoly::InternalPoly()
30	{
31	ASSERT( 0, "ups, why do you initialize an empty poly" );
32	}
33
34	InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
35	{
36	var = v;
37	firstTerm = new term( 0, c, e );
38	lastTerm = firstTerm;
39	}
40
41	InternalPoly::InternalPoly( const InternalPoly& )
42	{
43	ASSERT( 0, "ups there is something wrong in your code" );
44	};
45
46	InternalPoly::~InternalPoly()
47	{
48	freeTermList( firstTerm );
49	}
50
51	InternalCF*
52	InternalPoly::deepCopyObject() const
53	{
54	termList first, last;
55	first = deepCopyTermList( firstTerm, last );
56	return new InternalPoly( first, last, var );
57	}
58
59	InternalCF*
60	InternalPoly::genZero()
61	{
62	return firstTerm->coeff.genZero().getval();
63	}
64
65	InternalCF*
66	InternalPoly::genOne()
67	{
68	return firstTerm->coeff.genOne().getval();
69	}
70
71	bool
72	InternalPoly::isUnivariate() const
73	{
74	termList cursor = firstTerm;
75	while ( cursor ) {
76	if ( ! cursor->coeff.inCoeffDomain() )
77	return false;
78	cursor = cursor->next;
79	}
80	return true;
81	}
82
83	int
84	InternalPoly::degree()
85	{
86	return firstTerm->exp;
87	}
88
89	//{{{ int InternalPoly::sign () const
90	// docu: see CanonicalForm::sign()
91	int
92	InternalPoly::sign () const
93	{
94	return firstTerm->coeff.sign();
95	}
96	//}}}
97
98	CanonicalForm
99	InternalPoly::lc()
100	{
101	return firstTerm->coeff.lc();
102	}
103
104	CanonicalForm
105	InternalPoly::LC()
106	{
107	return firstTerm->coeff;
108	}
109
110	int
111	InternalPoly::taildegree()
112	{
113	return lastTerm->exp;
114	}
115
116	CanonicalForm
117	InternalPoly::tailcoeff()
118	{
119	return lastTerm->coeff;
120	}
121
122	CanonicalForm
123	InternalPoly::coeff( int i )
124	{
125	termList theCursor = firstTerm;
126	while ( theCursor ) {
127	if ( theCursor->exp == i )
128	return theCursor->coeff;
129	else if ( theCursor->exp > i )
130	theCursor = theCursor->next;
131	else
132	theCursor = 0;
133	}
134	return 0;
135	}
136
137	#ifndef NOSTREAMIO
138	void
139	InternalPoly::print(ostream &aStream, char * aString )
140	{
141	if ( ! firstTerm )
142	aStream << 0 << aString;
143	else {
144	char * theString;
145	termList theCursor = firstTerm;
146	while ( theCursor ) {
147	ostrstream theStream;
148	if ( theCursor->exp == 0 )
149	theCursor->coeff.print( aStream, aString );
150	else if ( theCursor->coeff.isOne() ) {
151	aStream << var;
152	if ( theCursor->exp != 1 )
153	aStream << '^' << theCursor->exp << aString;
154	else
155	aStream << aString;
156	}
157	else if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() ) {
158	aStream << '-' << var;
159	if ( theCursor->exp != 1 )
160	aStream << '^' << theCursor->exp << aString;
161	else
162	aStream << aString;
163	}
164	else {
165	theStream << '*' << var;
166	if ( theCursor->exp != 1 )
167	theStream << '^' << theCursor->exp << aString << ends;
168	else
169	theStream << aString << ends; // results from error in GNU strstream
170	theString = theStream.str();
171	theCursor->coeff.print( aStream, theString );
172	delete [] theString;
173	}
174	theCursor = theCursor->next;
175	if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
176	aStream << '+';
177	}
178	}
179	}
180	#endif /* NOSTREAMIO */
181
182	InternalCF*
183	InternalPoly::neg()
184	{
185	if ( getRefCount() == 1 ) {
186	negateTermList( firstTerm );
187	return this;
188	}
189	else {
190	decRefCount();
191	termList last, first = copyTermList( firstTerm, last, true );
192	return new InternalPoly( first, last, var );
193	}
194	}
195
196	InternalCF*
197	InternalPoly::invert()
198	{
199	if ( inExtension() && getReduce( var ) ) {
200	setReduce( var, false );
201	CanonicalForm a( this->copyObject() );
202	CanonicalForm b = getMipo( var );
203	CanonicalForm u, v;
204	CanonicalForm g = extgcd( a, b, u, v );
205	setReduce( var, true );
206	return u.getval();
207	}
208	else
209	return CFFactory::basic( 0 );
210	}
211
212	int
213	InternalPoly::comparesame ( InternalCF* acoeff )
214	{
215	InternalPoly* apoly = (InternalPoly*)acoeff;
216	if ( this == apoly )
217	return 0;
218	else {
219	termList cur1 = firstTerm;
220	termList cur2 = apoly->firstTerm;
221	for ( ; cur1 && cur2; cur1 = cur1->next, cur2 = cur2->next )
222	if ( ( cur1->exp != cur2->exp ) \|\| ( cur1->coeff != cur2->coeff ) )
223	if ( cur1->exp > cur2->exp )
224	return 1;
225	else if ( cur1->exp < cur2->exp )
226	return -1;
227	else if ( cur1->coeff > cur2->coeff )
228	return 1;
229	else
230	return -1;
231	return cur1 != cur2;
232	}
233	}
234
235	InternalCF*
236	InternalPoly::addsame( InternalCF* aCoeff )
237	{
238	InternalPoly * aPoly = (InternalPoly*)aCoeff;
239	if ( getRefCount() == 1 ) {
240	firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
241	if ( firstTerm && firstTerm->exp != 0 )
242	return this;
243	else if ( firstTerm ) {
244	InternalCF * res = firstTerm->coeff.getval();
245	delete this;
246	return res;
247	}
248	else {
249	delete this;
250	return CFFactory::basic( 0 );
251	}
252	}
253	else {
254	decRefCount();
255	termList last, first = copyTermList( firstTerm, last );
256	first = addTermList( first, aPoly->firstTerm, last, false );
257	if ( first && first->exp != 0 )
258	return new InternalPoly( first, last, var );
259	else if ( first ) {
260	InternalCF * res = first->coeff.getval();
261	delete first;
262	return res;
263	}
264	else
265	return CFFactory::basic( 0 );
266
267	}
268	}
269
270	InternalCF*
271	InternalPoly::subsame( InternalCF* aCoeff )
272	{
273	InternalPoly * aPoly = (InternalPoly*)aCoeff;
274	if ( getRefCount() == 1 ) {
275	firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
276	if ( firstTerm && firstTerm->exp != 0 )
277	return this;
278	else if ( firstTerm ) {
279	InternalCF * res = firstTerm->coeff.getval();
280	delete this;
281	return res;
282	}
283	else {
284	delete this;
285	return CFFactory::basic( 0 );
286	}
287	}
288	else {
289	decRefCount();
290	termList last, first = copyTermList( firstTerm, last );
291	first = addTermList( first, aPoly->firstTerm, last, true );
292	if ( first && first->exp != 0 )
293	return new InternalPoly( first, last, var );
294	else if ( first ) {
295	InternalCF * res = first->coeff.getval();
296	delete first;
297	return res;
298	}
299	else
300	return CFFactory::basic( 0 );
301
302	}
303	}
304
305	InternalCF*
306	InternalPoly::mulsame( InternalCF* aCoeff )
307	{
308	InternalPoly aPoly = (InternalPoly)aCoeff;
309	termList resultFirst = 0, resultLast = 0;
310	termList theCursor = firstTerm;
311
312	while ( theCursor ) {
313	resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm, theCursor->coeff, theCursor->exp, resultLast, false );
314	theCursor = theCursor->next;
315	}
316	if ( inExtension() && getReduce( var ) ) {
317	resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
318	if ( resultFirst == 0 )
319	if ( getRefCount() == 1 ) {
320	delete this;
321	return CFFactory::basic(0);
322	}
323	else {
324	decRefCount();
325	return CFFactory::basic(0);
326	}
327	else if ( resultFirst->exp == 0 )
328	if ( getRefCount() == 1 ) {
329	InternalCF * res = resultFirst->coeff.getval();
330	delete resultFirst;
331	delete this;
332	return res;
333	}
334	else {
335	decRefCount();
336	InternalCF * res = resultFirst->coeff.getval();
337	delete resultFirst;
338	return res;
339	}
340	}
341	if ( getRefCount() == 1 ) {
342	freeTermList( firstTerm );
343	firstTerm = resultFirst;
344	lastTerm = resultLast;
345	return this;
346	}
347	else {
348	decRefCount();
349	return new InternalPoly( resultFirst, resultLast, var );
350	}
351	}
352
353	InternalCF*
354	InternalPoly::dividesame( InternalCF* aCoeff )
355	{
356	return divsame( aCoeff );
357	}
358
359
360	InternalCF*
361	InternalPoly::divsame( InternalCF* aCoeff )
362	{
363	if ( inExtension() && getReduce( var ) ) {
364	InternalCF * dummy = aCoeff->invert();
365	dummy = dummy->mulsame( this );
366	if ( getRefCount() == 1 ) {
367	delete this;
368	return dummy;
369	}
370	else {
371	decRefCount();
372	return dummy;
373	}
374	}
375	InternalPoly aPoly = (InternalPoly)aCoeff;
376	termList dummy, first, last, resultfirst = 0, resultlast = 0;
377	CanonicalForm coeff, newcoeff;
378	int exp, newexp;
379	bool singleObject;
380
381	if ( getRefCount() == 1 ) {
382	first = firstTerm; last = lastTerm; singleObject = true;
383	}
384	else {
385	first = copyTermList( firstTerm, last ); singleObject = false;
386	decRefCount();
387	}
388	coeff = aPoly->firstTerm->coeff;
389	exp = aPoly->firstTerm->exp;
390	while (first && ( first->exp >= exp ) ) {
391	newcoeff = first->coeff / coeff;
392	newexp = first->exp - exp;
393	dummy = first;
394	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
395	delete dummy;
396	appendTermList( resultfirst, resultlast, newcoeff, newexp );
397	}
398	freeTermList( first );
399	if ( singleObject ) {
400	if ( resultfirst && resultfirst->exp != 0 ) {
401	firstTerm = resultfirst;
402	lastTerm = resultlast;
403	return this;
404	}
405	else if ( resultfirst ) {
406	InternalCF * res = resultfirst->coeff.getval();
407	delete resultfirst;
408	firstTerm = 0;
409	delete this;
410	return res;
411	}
412	else {
413	// this should not happen (evtl use assertion)
414	ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
415	firstTerm = 0;
416	delete this;
417	return CFFactory::basic( 0 );
418	}
419	}
420	else {
421	if ( resultfirst && resultfirst->exp != 0 )
422	return new InternalPoly( resultfirst, resultlast, var );
423	else if ( resultfirst ) {
424	InternalCF * res = resultfirst->coeff.getval();
425	delete resultfirst;
426	return res;
427	}
428	else
429	return CFFactory::basic( 0 );
430	}
431	}
432
433	InternalCF*
434	InternalPoly::modulosame( InternalCF* aCoeff )
435	{
436	return modsame( aCoeff );
437	}
438
439	InternalCF*
440	InternalPoly::modsame( InternalCF* aCoeff )
441	{
442	if ( inExtension() && getReduce( var ) ) {
443	if ( deleteObject() ) delete this;
444	return CFFactory::basic( 0 );
445	}
446	InternalPoly aPoly = (InternalPoly)aCoeff;
447	termList dummy, first, last;
448	CanonicalForm coeff, newcoeff;
449	int exp, newexp;
450	bool singleObject;
451
452	if ( getRefCount() == 1 ) {
453	first = firstTerm; last = lastTerm; singleObject = true;
454	}
455	else {
456	first = copyTermList( firstTerm, last ); singleObject = false;
457	decRefCount();
458	}
459	coeff = aPoly->firstTerm->coeff;
460	exp = aPoly->firstTerm->exp;
461	while (first && ( first->exp >= exp ) ) {
462	newcoeff = first->coeff / coeff;
463	newexp = first->exp - exp;
464	dummy = first;
465	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
466	delete dummy;
467	}
468	if ( singleObject ) {
469	if ( first && first->exp != 0 ) {
470	firstTerm = first;
471	lastTerm = last;
472	return this;
473	}
474	else if ( first ) {
475	InternalCF * res = first->coeff.getval();
476	delete first;
477	firstTerm = 0;
478	delete this;
479	return res;
480	}
481	else {
482	firstTerm = 0;
483	delete this;
484	return CFFactory::basic( 0 );
485	}
486	}
487	else {
488	if ( first && first->exp != 0 )
489	return new InternalPoly( first, last, var );
490	else if ( first ) {
491	InternalCF * res = first->coeff.getval();
492	delete first;
493	return res;
494	}
495	else
496	return CFFactory::basic( 0 );
497	}
498	}
499
500
501	void
502	InternalPoly::divremsame( InternalCF* acoeff, InternalCF& quot, InternalCF& rem )
503	{
504	if ( inExtension() && getReduce( var ) ) {
505	InternalCF * dummy = acoeff->invert();
506	quot = dummy->mulsame( this );
507	rem = CFFactory::basic( 0 );
508	}
509	else {
510	InternalPoly aPoly = (InternalPoly)acoeff;
511	termList dummy, first, last, resultfirst = 0, resultlast = 0;
512	CanonicalForm coeff, newcoeff;
513	int exp, newexp;
514
515	first = copyTermList( firstTerm, last );
516
517	coeff = aPoly->firstTerm->coeff;
518	exp = aPoly->firstTerm->exp;
519	while (first && ( first->exp >= exp ) ) {
520	newcoeff = first->coeff / coeff;
521	newexp = first->exp - exp;
522	dummy = first;
523	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
524	delete dummy;
525	appendTermList( resultfirst, resultlast, newcoeff, newexp );
526	}
527	if ( resultfirst )
528	if ( resultfirst->exp == 0 ) {
529	quot = resultfirst->coeff.getval();
530	delete resultfirst;
531	}
532	else
533	quot = new InternalPoly( resultfirst, resultlast, var );
534	else
535	quot = CFFactory::basic( 0 );
536	if ( first )
537	if ( first->exp == 0 ) {
538	rem = first->coeff.getval();
539	delete first;
540	}
541	else
542	rem = new InternalPoly( first, last, var );
543	else
544	rem = CFFactory::basic( 0 );
545	}
546	}
547
548
549	bool
550	InternalPoly::divremsamet( InternalCF* acoeff, InternalCF& quot, InternalCF& rem )
551	{
552	if ( inExtension() && getReduce( var ) ) {
553	divremsame( acoeff, quot, rem );
554	return true;
555	}
556	InternalPoly aPoly = (InternalPoly)acoeff;
557	termList dummy, first, last, resultfirst = 0, resultlast = 0;
558	CanonicalForm coeff, newcoeff, dummycoeff;
559	int exp, newexp;
560	bool divideok = true;
561
562	// if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
563	// return false;
564
565	first = copyTermList( firstTerm, last );
566
567	coeff = aPoly->firstTerm->coeff;
568	exp = aPoly->firstTerm->exp;
569	while (first && ( first->exp >= exp ) && divideok ) {
570	divideok = ::divremt( first->coeff, coeff, newcoeff, dummycoeff );
571	if ( divideok && dummycoeff.isZero() ) {
572	newexp = first->exp - exp;
573	dummy = first;
574	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
575	delete dummy;
576	appendTermList( resultfirst, resultlast, newcoeff, newexp );
577	}
578	else
579	divideok = false;
580	}
581	if ( divideok ) {
582	if ( resultfirst )
583	if ( resultfirst->exp == 0 ) {
584	quot = resultfirst->coeff.getval();
585	delete resultfirst;
586	}
587	else
588	quot = new InternalPoly( resultfirst, resultlast, var );
589	else
590	quot = CFFactory::basic( 0 );
591	if ( first )
592	if ( first->exp == 0 ) {
593	rem = first->coeff.getval();
594	delete first;
595	}
596	else
597	rem = new InternalPoly( first, last, var );
598	else
599	rem = CFFactory::basic( 0 );
600	}
601	else {
602	freeTermList( resultfirst );
603	freeTermList( first );
604	}
605	return divideok;
606	}
607
608	int
609	InternalPoly::comparecoeff ( InternalCF* acoeff )
610	{
611	return 1;
612	}
613
614	InternalCF*
615	InternalPoly::addcoeff( InternalCF* cc )
616	{
617	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
618	if ( c.isZero() )
619	return this;
620	else {
621	if ( getRefCount() == 1 ) {
622	if ( lastTerm->exp == 0 ) {
623	lastTerm->coeff += c;
624	if ( lastTerm->coeff.isZero() ) {
625	termList cursor = firstTerm;
626	while ( cursor->next != lastTerm )
627	cursor = cursor->next;
628	delete lastTerm;
629	cursor->next = 0;
630	lastTerm = cursor;
631	}
632	}
633	else {
634	lastTerm->next = new term( 0, c, 0 );
635	lastTerm = lastTerm->next;
636	}
637	return this;
638	}
639	else {
640	decRefCount();
641	termList last, first = copyTermList( firstTerm, last, false );
642	if ( last->exp == 0 ) {
643	last->coeff += c;
644	if ( last->coeff.isZero() ) {
645	termList cursor = first;
646	while ( cursor->next != last )
647	cursor = cursor->next;
648	delete last;
649	cursor->next = 0;
650	last = cursor;
651	}
652	}
653	else {
654	last->next = new term( 0, c, 0 );
655	last = last->next;
656	}
657	return new InternalPoly( first, last, var );
658	}
659	}
660	}
661
662	InternalCF*
663	InternalPoly::subcoeff( InternalCF* cc, bool negate )
664	{
665	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
666	if ( c.isZero() )
667	if ( getRefCount() > 1 ) {
668	decRefCount();
669	termList last, first = copyTermList( firstTerm, last, negate );
670	return new InternalPoly( first, last, var );
671	}
672	else {
673	if ( negate )
674	negateTermList( firstTerm );
675	return this;
676	}
677	else {
678	if ( getRefCount() == 1 ) {
679	if ( lastTerm->exp == 0 ) {
680	if ( negate ) {
681	negateTermList( firstTerm );
682	lastTerm->coeff += c;
683	}
684	else
685	lastTerm->coeff -= c;
686	if ( lastTerm->coeff.isZero() ) {
687	termList cursor = firstTerm;
688	while ( cursor->next != lastTerm )
689	cursor = cursor->next;
690	delete lastTerm;
691	cursor->next = 0;
692	lastTerm = cursor;
693	}
694	}
695	else {
696	if ( negate ) {
697	negateTermList( firstTerm );
698	lastTerm->next = new term( 0, c, 0 );
699	}
700	else
701	lastTerm->next = new term( 0, -c, 0 );
702	lastTerm = lastTerm->next;
703	}
704	return this;
705	}
706	else {
707	decRefCount();
708	termList last, first = copyTermList( firstTerm, last, negate );
709	if ( last->exp == 0 ) {
710	if ( negate )
711	last->coeff += c;
712	else
713	last->coeff -= c;
714	if ( last->coeff.isZero() ) {
715	termList cursor = first;
716	while ( cursor->next != last )
717	cursor = cursor->next;
718	delete last;
719	cursor->next = 0;
720	last = cursor;
721	}
722	}
723	else {
724	if ( negate )
725	last->next = new term( 0, c, 0 );
726	else
727	last->next = new term( 0, -c, 0 );
728	last = last->next;
729	}
730	return new InternalPoly( first, last, var );
731	}
732	}
733	}
734
735	InternalCF*
736	InternalPoly::mulcoeff( InternalCF* cc )
737	{
738	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
739	if ( c.isZero() ) {
740	if ( getRefCount() == 1 ) {
741	delete this;
742	return CFFactory::basic( 0 );
743	}
744	else {
745	decRefCount();
746	return CFFactory::basic( 0 );
747	}
748	}
749	else if ( c.isOne() )
750	return this;
751	else {
752	if ( getRefCount() == 1 ) {
753	mulTermList( firstTerm, c, 0 );
754	return this;
755	}
756	else {
757	decRefCount();
758	termList last, first = copyTermList( firstTerm, last );
759	mulTermList( first, c, 0 );
760	return new InternalPoly( first, last, var );
761	}
762	}
763	}
764
765	InternalCF*
766	InternalPoly::dividecoeff( InternalCF* c, bool invert )
767	{
768	return divcoeff( c, invert );
769	}
770
771	InternalCF*
772	InternalPoly::divcoeff( InternalCF* cc, bool invert )
773	{
774	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
775	if ( inExtension() && getReduce( var ) && invert ) {
776	InternalCF * dummy;
777	dummy = this->invert();
778	dummy = dummy->mulcoeff( cc );
779	if ( getRefCount() == 1 ) {
780	delete this;
781	return dummy;
782	}
783	else {
784	decRefCount();
785	return dummy;
786	}
787	}
788	if ( invert )
789	if ( getRefCount() == 1 ) {
790	delete this;
791	return CFFactory::basic( 0 );
792	}
793	else {
794	decRefCount();
795	return CFFactory::basic( 0 );
796	}
797	if ( c.isOne() )
798	return this;
799	else {
800	if ( getRefCount() == 1 ) {
801	firstTerm = divTermList( firstTerm, c, lastTerm );
802	if ( firstTerm && firstTerm->exp != 0 )
803	return this;
804	else if ( firstTerm ) {
805	InternalCF * res = firstTerm->coeff.getval();
806	delete this;
807	return res;
808	}
809	else {
810	delete this;
811	return CFFactory::basic( 0 );
812	}
813	}
814	else {
815	decRefCount();
816	termList last, first = copyTermList( firstTerm, last );
817	first = divTermList( first, c, last );
818	if ( first && first->exp != 0 )
819	return new InternalPoly( first, last, var );
820	else if ( first ) {
821	InternalCF * res = first->coeff.getval();
822	delete first;
823	return res;
824	}
825	else {
826	delete first;
827	return CFFactory::basic( 0 );
828	}
829	}
830	}
831	}
832
833	InternalCF*
834	InternalPoly::modulocoeff( InternalCF* cc, bool invert )
835	{
836	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
837	if ( invert ) {
838	if ( deleteObject() ) delete this;
839	return c.getval();
840	}
841	ASSERT( ! c.isZero(), "divide by zero!" );
842	if ( deleteObject() ) delete this;
843	return CFFactory::basic( 0 );
844	}
845
846	InternalCF*
847	InternalPoly::modcoeff( InternalCF* cc, bool invert )
848	{
849	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
850	if ( invert ) {
851	if ( deleteObject() ) delete this;
852	return c.getval();
853	}
854	ASSERT( ! c.isZero(), "divide by zero!" );
855	if ( c.isOne() ) {
856	if ( getRefCount() == 1 ) {
857	delete this;
858	return CFFactory::basic( 0 );
859	}
860	else {
861	decRefCount();
862	return CFFactory::basic( 0 );
863	}
864	}
865	else {
866	if ( getRefCount() == 1 ) {
867	firstTerm = modTermList( firstTerm, c, lastTerm );
868	if ( firstTerm && firstTerm->exp != 0 )
869	return this;
870	else if ( firstTerm ) {
871	InternalCF * res = firstTerm->coeff.getval();
872	delete this;
873	return res;
874	}
875	else {
876	delete this;
877	return CFFactory::basic( 0 );
878	}
879	}
880	else {
881	decRefCount();
882	termList last, first = copyTermList( firstTerm, last );
883	first = modTermList( first, c, last );
884	if ( first && first->exp != 0 )
885	return new InternalPoly( first, last, var );
886	else if ( first ) {
887	InternalCF * res = first->coeff.getval();
888	delete first;
889	return res;
890	}
891	else {
892	delete first;
893	return CFFactory::basic( 0 );
894	}
895	}
896	}
897	}
898
899	void
900	InternalPoly::divremcoeff( InternalCF* cc, InternalCF& quot, InternalCF& rem, bool invert )
901	{
902	if ( inExtension() && getReduce( var ) ) {
903	quot = copyObject();
904	quot = quot->dividecoeff( cc, invert );
905	rem = CFFactory::basic( 0 );
906	}
907	else if ( invert ) {
908	if ( is_imm( cc ) )
909	rem = cc;
910	else
911	rem = cc->copyObject();
912	quot = CFFactory::basic( 0 );
913	}
914	else {
915	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
916	ASSERT( ! c.isZero(), "divide by zero!" );
917	termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
918	quotfirst = divTermList( quotfirst, c, quotlast );
919	if ( quotfirst )
920	if ( quotfirst->exp == 0 ) {
921	quot = quotfirst->coeff.getval();
922	delete quotfirst;
923	}
924	else
925	quot = new InternalPoly( quotfirst, quotlast, var );
926	else
927	quot = CFFactory::basic( 0 );
928	rem = CFFactory::basic( 0 );
929	}
930	}
931
932	bool
933	InternalPoly::divremcoefft( InternalCF* cc, InternalCF& quot, InternalCF& rem, bool invert )
934	{
935	if ( inExtension() && getReduce( var ) ) {
936	quot = copyObject();
937	quot = quot->dividecoeff( cc, invert );
938	rem = CFFactory::basic( 0 );
939	return true;
940	}
941	else if ( invert ) {
942	if ( is_imm( cc ) )
943	rem = cc;
944	else
945	rem = cc->copyObject();
946	quot = CFFactory::basic( 0 );
947	return true;
948	}
949	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
950	ASSERT( ! c.isZero(), "divide by zero!" );
951	termList quotfirst, quotcursor;
952	termList cursor;
953	CanonicalForm cquot, crem;
954	bool divideok = true;
955
956	cursor = firstTerm;
957	quotcursor = quotfirst = new term;
958
959	while ( cursor && divideok ) {
960	divideok = ::divremt( cursor->coeff, c, cquot, crem );
961	divideok = divideok && crem.isZero();
962	if ( divideok ) {
963	if ( ! cquot.isZero() ) {
964	quotcursor->next = new term( 0, cquot, cursor->exp );
965	quotcursor = quotcursor->next;
966	}
967	cursor = cursor->next;
968	}
969	}
970	quotcursor->next = 0;
971	if ( divideok ) {
972	cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
973	if ( quotfirst )
974	if ( quotfirst->exp == 0 ) {
975	quot = quotfirst->coeff.getval();
976	delete quotfirst;
977	}
978	else
979	quot = new InternalPoly( quotfirst, quotcursor, var );
980	else
981	quot = CFFactory::basic( 0 );
982	rem = CFFactory::basic( 0 );
983	}
984	else {
985	freeTermList( quotfirst );
986	}
987	return divideok;
988	}
989
990	// static functions
991
992	termList
993	InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
994	{
995	if ( aTermList == 0 )
996	return 0;
997	else if ( negate ) {
998	termList sourceCursor = aTermList;
999	termList dummy = new term;
1000	termList targetCursor = dummy;
1001
1002	while ( sourceCursor ) {
1003	targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
1004	targetCursor = targetCursor->next;
1005	sourceCursor = sourceCursor->next;
1006	}
1007	targetCursor->next = 0;
1008	theLastTerm = targetCursor;
1009	targetCursor = dummy->next;
1010	delete dummy;
1011	return targetCursor;
1012	}
1013	else {
1014	termList sourceCursor = aTermList;
1015	termList dummy = new term;
1016	termList targetCursor = dummy;
1017
1018	while ( sourceCursor ) {
1019	targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
1020	targetCursor = targetCursor->next;
1021	sourceCursor = sourceCursor->next;
1022	}
1023	targetCursor->next = 0;
1024	theLastTerm = targetCursor;
1025	targetCursor = dummy->next;
1026	delete dummy;
1027	return targetCursor;
1028	}
1029	}
1030
1031	termList
1032	InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
1033	{
1034	if ( aTermList == 0 )
1035	return 0;
1036	else {
1037	termList sourceCursor = aTermList;
1038	termList dummy = new term;
1039	termList targetCursor = dummy;
1040
1041	while ( sourceCursor ) {
1042	targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
1043	targetCursor = targetCursor->next;
1044	sourceCursor = sourceCursor->next;
1045	}
1046	targetCursor->next = 0;
1047	theLastTerm = targetCursor;
1048	targetCursor = dummy->next;
1049	delete dummy;
1050	return targetCursor;
1051	}
1052	}
1053
1054	void
1055	InternalPoly::freeTermList ( termList aTermList )
1056	{
1057	termList cursor = aTermList;
1058
1059	while ( cursor ) {
1060	cursor = cursor->next;
1061	delete aTermList;
1062	aTermList = cursor;
1063	}
1064	}
1065
1066	void
1067	InternalPoly::negateTermList ( termList terms )
1068	{
1069	termList cursor = terms;
1070	while ( cursor ) {
1071	cursor->coeff = -cursor->coeff;
1072	cursor = cursor->next;
1073	}
1074	}
1075
1076	termList
1077	InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
1078	{
1079	termList theCursor = theList;
1080	termList aCursor = aList;
1081	termList predCursor = 0;
1082
1083	while ( theCursor && aCursor ) {
1084	if ( theCursor->exp == aCursor->exp ) {
1085	if ( negate )
1086	theCursor->coeff -= aCursor->coeff;
1087	else
1088	theCursor->coeff += aCursor->coeff;
1089	if ( theCursor->coeff.isZero() ) {
1090	if ( predCursor ) {
1091	predCursor->next = theCursor->next;
1092	delete theCursor;
1093	theCursor = predCursor->next;
1094	}
1095	else {
1096	theList = theList->next;
1097	delete theCursor;
1098	theCursor = theList;
1099	}
1100	}
1101	else {
1102	predCursor = theCursor;
1103	theCursor = theCursor->next;
1104	}
1105	aCursor = aCursor->next;
1106	}
1107	else if ( theCursor->exp < aCursor->exp ) {
1108	if ( negate )
1109	if ( predCursor ) {
1110	predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
1111	predCursor = predCursor->next;
1112	}
1113	else {
1114	theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
1115	predCursor = theList;
1116	}
1117	else
1118	if ( predCursor ) {
1119	predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
1120	predCursor = predCursor->next;
1121	}
1122	else {
1123	theList = new term( theCursor, aCursor->coeff, aCursor->exp );
1124	predCursor = theList;
1125	}
1126	aCursor = aCursor->next;
1127	}
1128	else {
1129	predCursor = theCursor;
1130	theCursor = theCursor->next;
1131	}
1132	}
1133	if ( aCursor ) {
1134	if ( predCursor )
1135	predCursor->next = copyTermList( aCursor, lastTerm, negate );
1136	else
1137	theList = copyTermList( aCursor, lastTerm, negate );
1138	}
1139	else if ( ! theCursor )
1140	lastTerm = predCursor;
1141
1142	return theList;
1143	}
1144
1145	void
1146	InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
1147	{
1148	while ( theCursor ) {
1149	theCursor->coeff *= coeff;
1150	theCursor->exp += exp;
1151	theCursor = theCursor->next;
1152	}
1153	}
1154
1155	termList
1156	InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1157	{
1158	termList theCursor = firstTerm;
1159	lastTerm = 0;
1160	termList dummy;
1161
1162	while ( theCursor ) {
1163	theCursor->coeff /= coeff;
1164	if ( theCursor->coeff.isZero() ) {
1165	if ( theCursor == firstTerm )
1166	firstTerm = theCursor->next;
1167	else
1168	lastTerm->next = theCursor->next;
1169	dummy = theCursor;
1170	theCursor = theCursor->next;
1171	delete dummy;
1172	}
1173	else {
1174	lastTerm = theCursor;
1175	theCursor = theCursor->next;
1176	}
1177	}
1178	return firstTerm;
1179	}
1180
1181	termList
1182	InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1183	{
1184	termList theCursor = firstTerm;
1185	lastTerm = 0;
1186	termList dummy;
1187
1188	while ( theCursor ) {
1189	theCursor->coeff.mod( coeff );
1190	if ( theCursor->coeff.isZero() ) {
1191	if ( theCursor == firstTerm )
1192	firstTerm = theCursor->next;
1193	else
1194	lastTerm->next = theCursor->next;
1195	dummy = theCursor;
1196	theCursor = theCursor-> next;
1197	delete dummy;
1198	}
1199	else {
1200	lastTerm = theCursor;
1201	theCursor = theCursor->next;
1202	}
1203	}
1204	return firstTerm;
1205	}
1206
1207	void
1208	InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
1209	{
1210	if ( last ) {
1211	last->next = new term( 0, coeff, exp );
1212	last = last->next;
1213	}
1214	else {
1215	first = new term( 0, coeff, exp );
1216	last = first;
1217	}
1218	}
1219
1220	termList
1221	InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
1222	{
1223	termList theCursor = theList;
1224	termList aCursor = aList;
1225	termList predCursor = 0;
1226	CanonicalForm coeff;
1227
1228	if ( negate )
1229	coeff = -c;
1230	else
1231	coeff = c;
1232
1233	while ( theCursor && aCursor ) {
1234	if ( theCursor->exp == aCursor->exp + exp ) {
1235	theCursor->coeff += aCursor->coeff * coeff;
1236	if ( theCursor->coeff.isZero() ) {
1237	if ( predCursor ) {
1238	predCursor->next = theCursor->next;
1239	delete theCursor;
1240	theCursor = predCursor->next;
1241	}
1242	else {
1243	theList = theList->next;
1244	delete theCursor;
1245	theCursor = theList;
1246	}
1247	}
1248	else {
1249	predCursor = theCursor;
1250	theCursor = theCursor->next;
1251	}
1252	aCursor = aCursor->next;
1253	}
1254	else if ( theCursor->exp < aCursor->exp + exp ) {
1255	if ( predCursor ) {
1256	predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1257	predCursor = predCursor->next;
1258	}
1259	else {
1260	theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1261	predCursor = theList;
1262	}
1263	aCursor = aCursor->next;
1264	}
1265	else {
1266	predCursor = theCursor;
1267	theCursor = theCursor->next;
1268	}
1269	}
1270	if ( aCursor ) {
1271	if ( predCursor ) {
1272	predCursor->next = copyTermList( aCursor, lastTerm );
1273	predCursor = predCursor->next;
1274	}
1275	else {
1276	theList = copyTermList( aCursor, lastTerm );
1277	predCursor = theList;
1278	}
1279	while ( predCursor ) {
1280	predCursor->exp += exp;
1281	predCursor->coeff *= coeff;
1282	predCursor = predCursor->next;
1283	}
1284	}
1285	else if ( ! theCursor )
1286	lastTerm = predCursor;
1287	return theList;
1288	}
1289
1290	termList
1291	InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
1292	{
1293	CanonicalForm coeff = redterms->coeff;
1294	CanonicalForm newcoeff;
1295	int newexp;
1296	int exp = redterms->exp;
1297	termList dummy;
1298	while ( first && ( first->exp >= exp ) ) {
1299	newcoeff = first->coeff / coeff;
1300	newexp = first->exp - exp;
1301	dummy = first;
1302	first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
1303	delete dummy;
1304	}
1305	return first;
1306	}

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

Download in other formats: