Context Navigation

source: git/factory/int_poly.cc @ 76470b9

spielwiese

Last change on this file since 76470b9 was 76470b9, checked in by Rüdiger Stobbe <stobbe@…>, 28 years ago
"modulocoeff: Bug fix, invert is now handled as it should be. " git-svn-id: file:///usr/local/Singular/svn/trunk@11 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 29.7 KB

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

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

Download in other formats: