Context Navigation

source: git/factory/canonicalform.cc @ 8c38a0e

spielwiese

Last change on this file since 8c38a0e was 8c38a0e, checked in by Jens Schmidt <schmidt@…>, 27 years ago
* canonicalform.cc: doc fix git-svn-id: file:///usr/local/Singular/svn/trunk@724 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 33.3 KB

Line
1	/* emacs edit mode for this file is -- C++ -- */
2	/* $Id: canonicalform.cc,v 1.18 1997-09-12 15:25:25 schmidt Exp $ */
3
4	#include <config.h>
5
6	#include "assert.h"
7
8	#include "cf_defs.h"
9	#include "cf_globals.h"
10	#include "canonicalform.h"
11	#include "cf_iter.h"
12	#include "int_cf.h"
13	#include "cf_factory.h"
14	#include "imm.h"
15	#include "gfops.h"
16	#include "cf_binom.h"
17	#if defined (USE_MEMUTIL) && ! defined (USE_OLD_MEMMAN)
18	#include "memman.h"
19	#endif
20
21	#ifndef NOSTREAMIO
22	CanonicalForm readCF( istream& );
23	#endif /* NOSTREAMIO */
24
25	CanonicalForm::CanonicalForm() : value( CFFactory::basic( (int)0 ) )
26	{
27	}
28
29	CanonicalForm::CanonicalForm( const int i ) : value( CFFactory::basic( i ) )
30	{
31	}
32
33	CanonicalForm::CanonicalForm( const CanonicalForm & cf ) : value( is_imm( cf.value ) ? cf.value : cf.value->copyObject() )
34	{
35	}
36
37	CanonicalForm::CanonicalForm( InternalCF * cf ) : value( cf )
38	{
39	}
40
41	CanonicalForm::CanonicalForm( const Variable & v ) : value( CFFactory::poly( v ) )
42	{
43	}
44
45	CanonicalForm::CanonicalForm( const Variable & v, int e ) : value( CFFactory::poly( v, e ) )
46	{
47	}
48
49	CanonicalForm::CanonicalForm( const char * str ) : value( CFFactory::basic( str ) )
50	{
51	}
52
53	CanonicalForm::~CanonicalForm()
54	{
55	if ( (! is_imm( value )) && value->deleteObject() )
56	delete value;
57	}
58
59	InternalCF*
60	CanonicalForm::getval() const
61	{
62	if ( is_imm( value ) )
63	return value;
64	else
65	return value->copyObject();
66	}
67
68	bool
69	CanonicalForm::isOne() const
70	{
71	if ( is_imm( value ) == FFMARK )
72	return imm_isone_p( value );
73	else if ( is_imm( value ) == GFMARK )
74	return imm_isone_gf( value );
75	else if ( is_imm( value ) )
76	return imm_isone( value );
77	else
78	return value->isOne();
79	}
80
81	bool
82	CanonicalForm::isZero() const
83	{
84	if ( is_imm( value ) == FFMARK )
85	return imm_iszero_p( value );
86	else if ( is_imm( value ) == GFMARK )
87	return imm_iszero_gf( value );
88	else if ( is_imm( value ) )
89	return imm_iszero( value );
90	else
91	return value->isZero();
92	}
93
94	bool
95	CanonicalForm::isImm() const
96	{
97	return is_imm( value );
98	}
99
100	bool
101	CanonicalForm::inZ() const
102	{
103	if ( is_imm( value ) == INTMARK )
104	return true;
105	else if ( is_imm( value ) )
106	return false;
107	else
108	return value->levelcoeff() == IntegerDomain;
109	}
110
111	bool
112	CanonicalForm::inQ() const
113	{
114	if ( is_imm( value ) == INTMARK )
115	return true;
116	else if ( is_imm( value ) )
117	return false;
118	else
119	return value->levelcoeff() == IntegerDomain \|\|
120	value->levelcoeff() == RationalDomain;
121	}
122
123	bool
124	CanonicalForm::inFF() const
125	{
126	return is_imm( value ) == FFMARK;
127	}
128
129	bool
130	CanonicalForm::inGF() const
131	{
132	return is_imm( value ) == GFMARK;
133	}
134
135	bool
136	CanonicalForm::inPP() const
137	{
138	return ! is_imm( value ) && ( value->levelcoeff() == PrimePowerDomain );
139	}
140
141	bool
142	CanonicalForm::inBaseDomain() const
143	{
144	if ( is_imm( value ) )
145	return true;
146	else
147	return value->inBaseDomain();
148	}
149
150	bool
151	CanonicalForm::inExtension() const
152	{
153	if ( is_imm( value ) )
154	return false;
155	else
156	return value->inExtension();
157	}
158
159	bool
160	CanonicalForm::inCoeffDomain() const
161	{
162	if ( is_imm( value ) )
163	return true;
164	else
165	return value->inCoeffDomain();
166	}
167
168	bool
169	CanonicalForm::inPolyDomain() const
170	{
171	if ( is_imm( value ) )
172	return false;
173	else
174	return value->inPolyDomain();
175	}
176
177	bool
178	CanonicalForm::inQuotDomain() const
179	{
180	if ( is_imm( value ) )
181	return false;
182	else
183	return value->inQuotDomain();
184	}
185
186	int
187	CanonicalForm::intval() const
188	{
189	if ( is_imm( value ) )
190	return imm_intval( value );
191	else
192	return value->intval();
193	}
194
195	CanonicalForm
196	CanonicalForm::lc() const
197	{
198	if ( is_imm( value ) )
199	return *this;
200	else
201	return value->lc();
202	}
203
204	CanonicalForm
205	CanonicalForm::LC() const
206	{
207	if ( inBaseDomain() )
208	return *this;
209	else
210	return value->LC();
211	}
212
213	CanonicalForm
214	CanonicalForm::LC( const Variable & v ) const
215	{
216	if ( inBaseDomain() )
217	return *this;
218	else if ( v == mvar() )
219	return value->LC();
220	else {
221	CanonicalForm f = swapvar( *this, v, mvar() );
222	if ( f.mvar() == mvar() )
223	return swapvar( f.value->LC(), v, mvar() );
224	else
225	return *this;
226	}
227	}
228
229	//{{{ int CanonicalForm::degree() const
230	//{{{ docu
231	//
232	// degree() - return degree in main variable.
233	//
234	// Returns -1 for the zero polynomial.
235	//
236	//}}}
237	int
238	CanonicalForm::degree() const
239	{
240	if ( isZero() )
241	return -1;
242	else if ( is_imm( value ) )
243	return 0;
244	else
245	return value->degree();
246	}
247	//}}}
248
249	//{{{ int CanonicalForm::degree( const Variable & v ) const
250	//{{{ docu
251	//
252	// degree() - return degree in variable v.
253	//
254	// Returns -1 for the zero polynomial.
255	//
256	// Note: If v is less than the main variable of CO we have to swap
257	// variables which may be quite expensive. Calculating the degree in
258	// respect to an algebraic variable may fail.
259	//
260	//}}}
261	int
262	CanonicalForm::degree( const Variable & v ) const
263	{
264	if ( isZero() )
265	return -1;
266	else if ( is_imm( value ) )
267	return 0;
268	else if ( inBaseDomain() )
269	return 0;
270
271	Variable x = mvar();
272	if ( v == x )
273	return value->degree();
274	else if ( v > x )
275	// relatively to v, f is in a coefficient ring
276	return 0;
277	else {
278	// v < mvar(), make v main variable
279	CanonicalForm f = swapvar( *this, v, x );
280	if ( f.mvar() == x )
281	return f.value->degree();
282	else
283	// in this case, we lost our main variable because
284	// v did not occur in CO
285	return 0;
286	}
287	}
288	//}}}
289
290	int
291	CanonicalForm::taildegree() const
292	{
293	if ( isZero() )
294	return -1;
295	else if ( is_imm( value ) )
296	return 0;
297	else
298	return value->taildegree();
299	}
300
301	CanonicalForm
302	CanonicalForm::tailcoeff() const
303	{
304	if ( inCoeffDomain() )
305	return *this;
306	else
307	return value->tailcoeff();
308	}
309
310	int
311	CanonicalForm::level() const
312	{
313	if ( is_imm( value ) )
314	return LEVELBASE;
315	else
316	return value->level();
317	}
318
319	Variable
320	CanonicalForm::mvar() const
321	{
322	if ( is_imm( value ) \|\| value->inBaseDomain() )
323	return Variable();
324	else
325	return value->variable();
326	}
327
328	CanonicalForm
329	CanonicalForm::num() const
330	{
331	if ( is_imm( value ) )
332	return *this;
333	else
334	return CanonicalForm( value->num() );
335	}
336
337	CanonicalForm
338	CanonicalForm::den() const
339	{
340	if ( is_imm( value ) )
341	return 1;
342	else
343	return CanonicalForm( value->den() );
344	}
345
346	CanonicalForm
347	CanonicalForm::deepCopy() const
348	{
349	if ( is_imm( value ) )
350	return *this;
351	else
352	return CanonicalForm( value->deepCopyObject() );
353	}
354
355	CanonicalForm
356	CanonicalForm::gcd( const CanonicalForm & ) const
357	{
358	// return ::gcd( *this, f );
359	return 1;
360	}
361
362	//{{{ CanonicalForm CanonicalForm::deriv() const
363	//{{{ docu
364	//
365	// deriv() - return the formal derivation of CO.
366	//
367	// Derives CO with respect to its main variable. Returns zero if
368	// f is in a coefficient domain.
369	//
370	//}}}
371	CanonicalForm
372	CanonicalForm::deriv() const
373	{
374	if ( inCoeffDomain() )
375	return 0;
376	else {
377	CanonicalForm res = 0;
378	Variable x = mvar();
379	for ( CFIterator i = *this; i.hasTerms(); i++ )
380	if ( i.exp() > 0 )
381	res += power( x, i.exp()-1 ) * i.coeff() * i.exp();
382	return res;
383	}
384	}
385	//}}}
386
387	//{{{ CanonicalForm CanonicalForm::deriv( const Variable & x ) const
388	//{{{ docu
389	//
390	// deriv() - return the formal derivation of CO with respect to x.
391	//
392	// Note: If x is less than the main variable of CO we have to
393	// swap variables which may be quite expensive. x should be a
394	// polynomial variable. Returns zero if f is in a coefficient
395	// domain.
396	//
397	// Timing Note (for the developer): I tried the same without
398	// 'Variable y = mvar()', replacing each occurence of y directly
399	// with 'mvar()'. It turned out that this version is slower in all
400	// cases.
401	//
402	//}}}
403	CanonicalForm
404	CanonicalForm::deriv( const Variable & x ) const
405	{
406	ASSERT( x.level() > 0, "cannot derive with respect to algebraic variables" );
407	if ( inCoeffDomain() )
408	return 0;
409
410	Variable y = mvar();
411	if ( x > y )
412	return 0;
413	else if ( x == y )
414	return deriv();
415	else
416	return swapvar( swapvar( *this, x, y ).deriv( y ), x, y );
417	}
418	//}}}
419
420	CanonicalForm
421	CanonicalForm::genCoeff( int type, int i )
422	{
423	return CanonicalForm( CFFactory::basic( type, i ) );
424	}
425
426	CanonicalForm
427	CanonicalForm::genZero() const
428	{
429	int what = is_imm( value );
430	if ( what == FFMARK )
431	return CanonicalForm( CFFactory::basic( FiniteFieldDomain, 0 ) );
432	else if ( what == GFMARK )
433	return CanonicalForm( CFFactory::basic( GaloisFieldDomain, 0 ) );
434	else if ( what )
435	return CanonicalForm( CFFactory::basic( IntegerDomain, 0 ) );
436	else
437	return CanonicalForm( value->genZero() );
438	}
439
440	CanonicalForm
441	CanonicalForm::genOne() const
442	{
443	int what = is_imm( value );
444	if ( what == FFMARK )
445	return CanonicalForm( CFFactory::basic( FiniteFieldDomain, 1 ) );
446	else if ( what == GFMARK )
447	return CanonicalForm( CFFactory::basic( GaloisFieldDomain, 1 ) );
448	else if ( what )
449	return CanonicalForm( CFFactory::basic( IntegerDomain, 1 ) );
450	else
451	return CanonicalForm( value->genOne() );
452	}
453
454	bool
455	CanonicalForm::isUnivariate() const
456	{
457	if ( is_imm( value ) )
458	return false;
459	else
460	return value->isUnivariate();
461	}
462
463	#ifndef NOSTREAMIO
464	void
465	CanonicalForm::print( ostream & os, char * str ) const
466	{
467	if ( is_imm( value ) )
468	imm_print( os, value, str );
469	else
470	value->print( os, str );
471	}
472	#endif /* NOSTREAMIO */
473
474	bool
475	operator == ( const CanonicalForm & lhs, const CanonicalForm & rhs )
476	{
477	int what = is_imm( lhs.value );
478	if ( what )
479	if ( what == is_imm( rhs.value ) )
480	return lhs.value == rhs.value;
481	else
482	return false;
483	else if ( is_imm( rhs.value ) )
484	return false;
485	else if ( lhs.level() == rhs.level() )
486	if ( lhs.value->levelcoeff() >= rhs.value->levelcoeff() )
487	return lhs.value->comparesame( rhs.value ) == 0;
488	else
489	return rhs.value->comparesame( lhs.value ) == 0;
490	else
491	return false;
492	}
493
494	bool
495	operator != ( const CanonicalForm & lhs, const CanonicalForm & rhs )
496	{
497	int what = is_imm( lhs.value );
498	if ( what )
499	if ( what == is_imm( rhs.value ) )
500	return lhs.value != rhs.value;
501	else
502	return true;
503	else if ( is_imm( rhs.value ) )
504	return true;
505	else if ( lhs.level() == rhs.level() )
506	if ( lhs.value->levelcoeff() >= rhs.value->levelcoeff() )
507	return lhs.value->comparesame( rhs.value ) != 0;
508	else
509	return rhs.value->comparesame( lhs.value ) != 0;
510	else
511	return true;
512	}
513
514	bool
515	operator > ( const CanonicalForm & lhs, const CanonicalForm & rhs )
516	{
517	int what = is_imm( lhs.value );
518	if ( what ) {
519	ASSERT ( ! is_imm( rhs.value ) \|\| (what==is_imm( rhs.value )), "illegal base coefficients" );
520	if ( what == INTMARK ) {
521	if ( what == is_imm( rhs.value ) )
522	return imm_cmp( lhs.value, rhs.value ) > 0;
523	else
524	return rhs.value->comparecoeff( lhs.value ) < 0;
525	}
526	else if ( what == FFMARK ) {
527	if ( what == is_imm( rhs.value ) )
528	return imm_cmp_p( lhs.value, rhs.value ) > 0;
529	else
530	return rhs.value->comparecoeff( lhs.value ) < 0;
531	}
532	else {
533	if ( what == is_imm( rhs.value ) )
534	return imm_cmp_gf( lhs.value, rhs.value ) > 0;
535	else
536	return rhs.value->comparecoeff( lhs.value ) < 0;
537	}
538	}
539	else if ( is_imm( rhs.value ) )
540	return lhs.value->comparecoeff( rhs.value ) > 0;
541	else if ( lhs.level() == rhs.level() )
542	if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
543	return lhs.value->comparesame( rhs.value ) > 0;
544	else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
545	return lhs.value->comparecoeff( lhs.value ) > 0;
546	else
547	return rhs.value->comparecoeff( lhs.value ) < 0;
548	else
549	return lhs.value->level() > rhs.value->level();
550	}
551
552	bool
553	operator < ( const CanonicalForm & lhs, const CanonicalForm & rhs )
554	{
555	int what = is_imm( lhs.value );
556	if ( what ) {
557	ASSERT ( ! is_imm( rhs.value ) \|\| (what==is_imm( rhs.value )), "illegal base coefficients" );
558	if ( what == INTMARK ) {
559	if ( what == is_imm( rhs.value ) )
560	return imm_cmp( lhs.value, rhs.value ) < 0;
561	else
562	return rhs.value->comparecoeff( lhs.value ) > 0;
563	}
564	else if ( what == FFMARK ) {
565	if ( what == is_imm( rhs.value ) )
566	return imm_cmp( lhs.value, rhs.value ) < 0;
567	else
568	return rhs.value->comparecoeff( lhs.value ) > 0;
569	}
570	else {
571	if ( what == is_imm( rhs.value ) )
572	return imm_cmp( lhs.value, rhs.value ) < 0;
573	else
574	return rhs.value->comparecoeff( lhs.value ) > 0;
575	}
576	}
577	else if ( is_imm( rhs.value ) )
578	return lhs.value->comparecoeff( rhs.value ) < 0;
579	else if ( lhs.level() == rhs.level() )
580	if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() )
581	return lhs.value->comparesame( rhs.value ) < 0;
582	else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() )
583	return lhs.value->comparecoeff( lhs.value ) < 0;
584	else
585	return rhs.value->comparecoeff( lhs.value ) > 0;
586	else
587	return lhs.value->level() < rhs.value->level();
588	}
589
590	CanonicalForm&
591	CanonicalForm::operator = ( const CanonicalForm & cf )
592	{
593	if ( this != &cf ) {
594	if ( (! is_imm( value )) && value->deleteObject() )
595	delete value;
596	value = (is_imm( cf.value )) ? cf.value : cf.value->copyObject();
597	}
598	return *this;
599	}
600
601	CanonicalForm&
602	CanonicalForm::operator = ( const int cf )
603	{
604	if ( (! is_imm( value )) && value->deleteObject() )
605	delete value;
606	value = CFFactory::basic( cf );
607	return *this;
608	}
609
610	CanonicalForm&
611	CanonicalForm::operator += ( const CanonicalForm & cf )
612	{
613	int what = is_imm( value );
614	if ( what ) {
615	ASSERT ( ! is_imm( cf.value ) \|\| (what==is_imm( cf.value )), "illegal base coefficients" );
616	if ( (what = is_imm( cf.value )) == FFMARK )
617	value = imm_add_p( value, cf.value );
618	else if ( what == GFMARK )
619	value = imm_add_gf( value, cf.value );
620	else if ( what )
621	value = imm_add( value, cf.value );
622	else {
623	InternalCF * dummy = cf.value->copyObject();
624	value = dummy->addcoeff( value );
625	}
626	}
627	else if ( is_imm( cf.value ) )
628	value = value->addcoeff( cf.value );
629	else if ( value->level() == cf.value->level() ) {
630	if ( value->levelcoeff() == cf.value->levelcoeff() )
631	value = value->addsame( cf.value );
632	else if ( value->levelcoeff() > cf.value->levelcoeff() )
633	value = value->addcoeff( cf.value );
634	else {
635	InternalCF * dummy = cf.value->copyObject();
636	dummy = dummy->addcoeff( value );
637	if ( value->deleteObject() ) delete value;
638	value = dummy;
639	}
640	}
641	else if ( level() > cf.level() )
642	value = value->addcoeff( cf.value );
643	else {
644	InternalCF * dummy = cf.value->copyObject();
645	dummy = dummy->addcoeff( value );
646	if ( value->deleteObject() ) delete value;
647	value = dummy;
648	}
649	return *this;
650	}
651
652	CanonicalForm&
653	CanonicalForm::operator -= ( const CanonicalForm & cf )
654	{
655	int what = is_imm( value );
656	if ( what ) {
657	ASSERT ( ! is_imm( cf.value ) \|\| (what==is_imm( cf.value )), "illegal base coefficients" );
658	if ( (what = is_imm( cf.value )) == FFMARK )
659	value = imm_sub_p( value, cf.value );
660	else if ( what == GFMARK )
661	value = imm_sub_gf( value, cf.value );
662	else if ( what )
663	value = imm_sub( value, cf.value );
664	else {
665	InternalCF * dummy = cf.value->copyObject();
666	value = dummy->subcoeff( value, true );
667	}
668	}
669	else if ( is_imm( cf.value ) )
670	value = value->subcoeff( cf.value, false );
671	else if ( value->level() == cf.value->level() ) {
672	if ( value->levelcoeff() == cf.value->levelcoeff() )
673	value = value->subsame( cf.value );
674	else if ( value->levelcoeff() > cf.value->levelcoeff() )
675	value = value->subcoeff( cf.value, false );
676	else {
677	InternalCF * dummy = cf.value->copyObject();
678	dummy = dummy->subcoeff( value, true );
679	if ( value->deleteObject() ) delete value;
680	value = dummy;
681	}
682	}
683	else if ( level() > cf.level() )
684	value = value->subcoeff( cf.value, false );
685	else {
686	InternalCF * dummy = cf.value->copyObject();
687	dummy = dummy->subcoeff( value, true );
688	if ( value->deleteObject() ) delete value;
689	value = dummy;
690	}
691	return *this;
692	}
693
694	CanonicalForm&
695	CanonicalForm::operator *= ( const CanonicalForm & cf )
696	{
697	int what = is_imm( value );
698	if ( what ) {
699	ASSERT ( ! is_imm( cf.value ) \|\| (what==is_imm( cf.value )), "illegal base coefficients" );
700	if ( (what = is_imm( cf.value )) == FFMARK )
701	value = imm_mul_p( value, cf.value );
702	else if ( what == GFMARK )
703	value = imm_mul_gf( value, cf.value );
704	else if ( what )
705	value = imm_mul( value, cf.value );
706	else {
707	InternalCF * dummy = cf.value->copyObject();
708	value = dummy->mulcoeff( value );
709	}
710	}
711	else if ( is_imm( cf.value ) )
712	value = value->mulcoeff( cf.value );
713	else if ( value->level() == cf.value->level() ) {
714	if ( value->levelcoeff() == cf.value->levelcoeff() )
715	value = value->mulsame( cf.value );
716	else if ( value->levelcoeff() > cf.value->levelcoeff() )
717	value = value->mulcoeff( cf.value );
718	else {
719	InternalCF * dummy = cf.value->copyObject();
720	dummy = dummy->mulcoeff( value );
721	if ( value->deleteObject() ) delete value;
722	value = dummy;
723	}
724	}
725	else if ( level() > cf.level() )
726	value = value->mulcoeff( cf.value );
727	else {
728	InternalCF * dummy = cf.value->copyObject();
729	dummy = dummy->mulcoeff( value );
730	if ( value->deleteObject() ) delete value;
731	value = dummy;
732	}
733	return *this;
734	}
735
736	CanonicalForm&
737	CanonicalForm::operator /= ( const CanonicalForm & cf )
738	{
739	int what = is_imm( value );
740	if ( what ) {
741	ASSERT ( ! is_imm( cf.value ) \|\| (what==is_imm( cf.value )), "illegal base coefficients" );
742	if ( (what = is_imm( cf.value )) == FFMARK )
743	value = imm_div_p( value, cf.value );
744	else if ( what == GFMARK )
745	value = imm_div_gf( value, cf.value );
746	else if ( what )
747	value = imm_divrat( value, cf.value );
748	else {
749	InternalCF * dummy = cf.value->copyObject();
750	value = dummy->dividecoeff( value, true );
751	}
752	}
753	else if ( is_imm( cf.value ) )
754	value = value->dividecoeff( cf.value, false );
755	else if ( value->level() == cf.value->level() ) {
756	if ( value->levelcoeff() == cf.value->levelcoeff() )
757	value = value->dividesame( cf.value );
758	else if ( value->levelcoeff() > cf.value->levelcoeff() )
759	value = value->dividecoeff( cf.value, false );
760	else {
761	InternalCF * dummy = cf.value->copyObject();
762	dummy = dummy->dividecoeff( value, true );
763	if ( value->deleteObject() ) delete value;
764	value = dummy;
765	}
766	}
767	else if ( level() > cf.level() )
768	value = value->dividecoeff( cf.value, false );
769	else {
770	InternalCF * dummy = cf.value->copyObject();
771	dummy = dummy->dividecoeff( value, true );
772	if ( value->deleteObject() ) delete value;
773	value = dummy;
774	}
775	return *this;
776	}
777
778	CanonicalForm&
779	CanonicalForm::div ( const CanonicalForm & cf )
780	{
781	int what = is_imm( value );
782	if ( what ) {
783	ASSERT ( ! is_imm( cf.value ) \|\| (what==is_imm( cf.value )), "illegal base coefficients" );
784	if ( (what = is_imm( cf.value )) == FFMARK )
785	value = imm_div_p( value, cf.value );
786	else if ( what == GFMARK )
787	value = imm_div_gf( value, cf.value );
788	else if ( what )
789	value = imm_div( value, cf.value );
790	else {
791	InternalCF * dummy = cf.value->copyObject();
792	value = dummy->divcoeff( value, true );
793	}
794	}
795	else if ( is_imm( cf.value ) )
796	value = value->divcoeff( cf.value, false );
797	else if ( value->level() == cf.value->level() ) {
798	if ( value->levelcoeff() == cf.value->levelcoeff() )
799	value = value->divsame( cf.value );
800	else if ( value->levelcoeff() > cf.value->levelcoeff() )
801	value = value->divcoeff( cf.value, false );
802	else {
803	InternalCF * dummy = cf.value->copyObject();
804	dummy = dummy->divcoeff( value, true );
805	if ( value->deleteObject() ) delete value;
806	value = dummy;
807	}
808	}
809	else if ( level() > cf.level() )
810	value = value->divcoeff( cf.value, false );
811	else {
812	InternalCF * dummy = cf.value->copyObject();
813	dummy = dummy->divcoeff( value, true );
814	if ( value->deleteObject() ) delete value;
815	value = dummy;
816	}
817	return *this;
818	}
819
820	CanonicalForm&
821	CanonicalForm::operator %= ( const CanonicalForm& cf )
822	{
823	int what = is_imm( value );
824	if ( what ) {
825	ASSERT ( ! is_imm( cf.value ) \|\| (what==is_imm( cf.value )), "illegal base coefficients" );
826	if ( (what = is_imm( cf.value )) == FFMARK )
827	value = imm_mod_p( value, cf.value );
828	else if ( what == GFMARK )
829	value = imm_mod_gf( value, cf.value );
830	else if ( what )
831	value = imm_mod( value, cf.value );
832	else {
833	InternalCF * dummy = cf.value->copyObject();
834	value = dummy->modulocoeff( value, true );
835	}
836	}
837	else if ( is_imm( cf.value ) )
838	value = value->modulocoeff( cf.value, false );
839	else if ( value->level() == cf.value->level() ) {
840	if ( value->levelcoeff() == cf.value->levelcoeff() )
841	value = value->modulosame( cf.value );
842	else if ( value->levelcoeff() > cf.value->levelcoeff() )
843	value = value->modulocoeff( cf.value, false );
844	else {
845	InternalCF * dummy = cf.value->copyObject();
846	dummy = dummy->modulocoeff( value, true );
847	if ( value->deleteObject() ) delete value;
848	value = dummy;
849	}
850	}
851	else if ( level() > cf.level() )
852	value = value->modulocoeff( cf.value, false );
853	else {
854	InternalCF * dummy = cf.value->copyObject();
855	dummy = dummy->modulocoeff( value, true );
856	if ( value->deleteObject() ) delete value;
857	value = dummy;
858	}
859	return *this;
860	}
861
862	CanonicalForm&
863	CanonicalForm::mod( const CanonicalForm & cf )
864	{
865	int what = is_imm( value );
866	if ( what ) {
867	ASSERT ( ! is_imm( cf.value ) \|\| (what==is_imm( cf.value )), "illegal base coefficients" );
868	if ( (what = is_imm( cf.value )) == FFMARK )
869	value = imm_mod_p( value, cf.value );
870	else if ( what == GFMARK )
871	value = imm_mod_gf( value, cf.value );
872	else if ( what )
873	value = imm_mod( value, cf.value );
874	else {
875	InternalCF * dummy = cf.value->copyObject();
876	value = dummy->modcoeff( value, true );
877	}
878	}
879	else if ( is_imm( cf.value ) )
880	value = value->modcoeff( cf.value, false );
881	else if ( value->level() == cf.value->level() ) {
882	if ( value->levelcoeff() == cf.value->levelcoeff() )
883	value = value->modsame( cf.value );
884	else if ( value->levelcoeff() > cf.value->levelcoeff() )
885	value = value->modcoeff( cf.value, false );
886	else {
887	InternalCF * dummy = cf.value->copyObject();
888	dummy = dummy->modcoeff( value, true );
889	if ( value->deleteObject() ) delete value;
890	value = dummy;
891	}
892	}
893	else if ( level() > cf.level() )
894	value = value->modcoeff( cf.value, false );
895	else {
896	InternalCF * dummy = cf.value->copyObject();
897	dummy = dummy->modcoeff( value, true );
898	if ( value->deleteObject() ) delete value;
899	value = dummy;
900	}
901	return *this;
902	}
903
904	CanonicalForm
905	operator - ( const CanonicalForm & cf )
906	{
907	CanonicalForm result( cf );
908	int what = is_imm( result.value );
909	if ( what == FFMARK )
910	result.value = imm_neg_p( result.value );
911	else if ( what == GFMARK )
912	result.value = imm_neg_gf( result.value );
913	else if ( what )
914	result.value = imm_neg( result.value );
915	else
916	result.value = result.value->neg();
917	return result;
918	}
919
920	CanonicalForm
921	operator + ( const CanonicalForm &c1, const CanonicalForm &c2 )
922	{
923	CanonicalForm result( c1 );
924	result += c2;
925	return result;
926	}
927
928	CanonicalForm
929	operator - ( const CanonicalForm &c1, const CanonicalForm &c2 )
930	{
931	CanonicalForm result( c1 );
932	result -= c2;
933	return result;
934	}
935
936	CanonicalForm
937	operator * ( const CanonicalForm &c1, const CanonicalForm &c2 )
938	{
939	CanonicalForm result( c1 );
940	result *= c2;
941	return result;
942	}
943
944	CanonicalForm
945	operator / ( const CanonicalForm &c1, const CanonicalForm &c2 )
946	{
947	CanonicalForm result( c1 );
948	result /= c2;
949	return result;
950	}
951
952	CanonicalForm
953	div ( const CanonicalForm &c1, const CanonicalForm &c2 )
954	{
955	CanonicalForm result( c1 );
956	result.div( c2 );
957	return result;
958	}
959
960	CanonicalForm
961	mod ( const CanonicalForm &c1, const CanonicalForm &c2 )
962	{
963	CanonicalForm result( c1 );
964	result.mod( c2 );
965	return result;
966	}
967
968	CanonicalForm
969	operator % ( const CanonicalForm &c1, const CanonicalForm &c2 )
970	{
971	CanonicalForm result( c1 );
972	result %= c2;
973	return result;
974	}
975
976	void
977	divrem ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r )
978	{
979	InternalCF * qq = 0, * rr = 0;
980	int what = is_imm( f.value );
981	if ( what )
982	if ( is_imm( g.value ) ) {
983	if ( what == FFMARK )
984	imm_divrem_p( f.value, g.value, qq, rr );
985	else if ( what == GFMARK )
986	imm_divrem_gf( f.value, g.value, qq, rr );
987	else
988	imm_divrem( f.value, g.value, qq, rr );
989	}
990	else
991	g.value->divremcoeff( f.value, qq, rr, true );
992	else if ( (what=is_imm( g.value )) )
993	f.value->divremcoeff( g.value, qq, rr, false );
994	else if ( f.value->level() == g.value->level() )
995	if ( f.value->levelcoeff() == g.value->levelcoeff() )
996	f.value->divremsame( g.value, qq, rr );
997	else if ( f.value->levelcoeff() > g.value->levelcoeff() )
998	f.value->divremcoeff( g.value, qq, rr, false );
999	else
1000	g.value->divremcoeff( f.value, qq, rr, true );
1001	else if ( f.value->level() > g.value->level() )
1002	f.value->divremcoeff( g.value, qq, rr, false );
1003	else
1004	g.value->divremcoeff( f.value, qq, rr, true );
1005	ASSERT( qq != 0 && rr != 0, "error in divrem" );
1006	q = CanonicalForm( qq );
1007	r = CanonicalForm( rr );
1008	}
1009
1010	bool
1011	divremt ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r )
1012	{
1013	InternalCF * qq = 0, * rr = 0;
1014	int what = is_imm( f.value );
1015	bool result = true;
1016	if ( what )
1017	if ( is_imm( g.value ) ) {
1018	if ( what == FFMARK )
1019	imm_divrem_p( f.value, g.value, qq, rr );
1020	else if ( what == GFMARK )
1021	imm_divrem_gf( f.value, g.value, qq, rr );
1022	else
1023	imm_divrem( f.value, g.value, qq, rr );
1024	}
1025	else
1026	result = g.value->divremcoefft( f.value, qq, rr, true );
1027	else if ( (what=is_imm( g.value )) )
1028	result = f.value->divremcoefft( g.value, qq, rr, false );
1029	else if ( f.value->level() == g.value->level() )
1030	if ( f.value->levelcoeff() == g.value->levelcoeff() )
1031	result = f.value->divremsamet( g.value, qq, rr );
1032	else if ( f.value->levelcoeff() > g.value->levelcoeff() )
1033	result = f.value->divremcoefft( g.value, qq, rr, false );
1034	else
1035	result = g.value->divremcoefft( f.value, qq, rr, true );
1036	else if ( f.value->level() > g.value->level() )
1037	result = f.value->divremcoefft( g.value, qq, rr, false );
1038	else
1039	result = g.value->divremcoefft( f.value, qq, rr, true );
1040	if ( result ) {
1041	ASSERT( qq != 0 && rr != 0, "error in divrem" );
1042	q = CanonicalForm( qq );
1043	r = CanonicalForm( rr );
1044	}
1045	else {
1046	q = 0; r = 0;
1047	}
1048	return result;
1049	}
1050
1051	#ifndef NOSTREAMIO
1052	ostream&
1053	operator << ( ostream & os, const CanonicalForm & cf )
1054	{
1055	cf.print( os, "" );
1056	return os;
1057	}
1058	#endif /* NOSTREAMIO */
1059
1060	#ifndef NOSTREAMIO
1061	istream&
1062	operator >> ( istream & is, CanonicalForm & cf )
1063	{
1064	#ifndef SINGULAR
1065	cf = readCF( is );
1066	return is;
1067	#else /* SINGULAR */
1068	return 0;
1069	#endif /* SINGULAR */
1070	}
1071	#endif /* NOSTREAMIO */
1072
1073	CanonicalForm
1074	CanonicalForm::operator () ( const CanonicalForm & f ) const
1075	{
1076	if ( inBaseDomain() )
1077	return *this;
1078	else {
1079	CanonicalForm result = 0;
1080	for ( CFIterator i = *this; i.hasTerms(); i++ )
1081	if ( i.exp() == 0 )
1082	result += i.coeff();
1083	else
1084	result += power( f, i.exp() ) * i.coeff();
1085	return result;
1086	}
1087	}
1088
1089	CanonicalForm
1090	CanonicalForm::operator () ( const CanonicalForm & f, const Variable & v ) const
1091	{
1092	if ( inBaseDomain() \|\| v > mvar() )
1093	return *this;
1094	else if ( v == mvar() ) {
1095	CanonicalForm result = 0;
1096	for ( CFIterator i = *this; i.hasTerms(); i++ )
1097	if ( i.exp() == 0 )
1098	result += i.coeff();
1099	else
1100	result += power( f, i.exp() ) * i.coeff();
1101	return result;
1102	}
1103	else {
1104	CanonicalForm G = swapvar( *this, v, Variable::highest() );
1105	if ( G.mvar() != Variable::highest() )
1106	return *this;
1107	CanonicalForm result = 0;
1108	for ( CFIterator i = G; i.hasTerms(); ++i )
1109	if ( i.exp() == 0 )
1110	result += i.coeff();
1111	else
1112	result += power( f, i.exp() ) * i.coeff();
1113	return result;
1114	}
1115	}
1116
1117	CanonicalForm
1118	CanonicalForm::operator[] ( int i ) const
1119	{
1120	return value->coeff( i );
1121	}
1122
1123	//{{{ int CanonicalForm::sign () const
1124	//{{{ docu
1125	//
1126	// sign() - return sign of CO.
1127	//
1128	// If CO is an integer or a rational number, the sign is defined
1129	// as usual. If CO is an element of a prime power domain or in a
1130	// finite field and SW_SYMMETRIC_FF is on the sign of CO is the
1131	// sign of the symmetric representation of CO. If CO is in GF(q)
1132	// or in a finite field and SW_SYMMETRIC_FF is off, the sign of
1133	// CO is zero iff CO is zero, otherwise the sign is one.
1134	//
1135	// If CO is a polynomial or in an extension of one of the base
1136	// domains, the sign of CO is the sign of its leading
1137	// coefficient.
1138	//
1139	// See also: InternalCF::sign(), InternalInteger::sign(),
1140	// InternalPrimePower::sign(), InternalRational::sign(),
1141	// InternalPoly::sign(), imm_sign(), gf_sign()
1142	//
1143	//}}}
1144	int
1145	CanonicalForm::sign () const
1146	{
1147	if ( is_imm( value ) )
1148	return imm_sign( value );
1149	else
1150	return value->sign();
1151	}
1152	//}}}
1153
1154	CanonicalForm
1155	power ( const CanonicalForm & f, int n )
1156	{
1157	ASSERT( n >= 0, "illegal exponent" );
1158	if ( f == 0 )
1159	return 0;
1160	else if ( f == 1 )
1161	return f;
1162	else if ( f == -1 ) {
1163	if ( n % 2 == 0 )
1164	return 1;
1165	else
1166	return -1;
1167	}
1168	else if ( n == 0 )
1169	return 1;
1170	else {
1171	CanonicalForm result = f;
1172	for ( int i = 1; i < n; i++ )
1173	result *= f;
1174	return result;
1175	}
1176	}
1177
1178	CanonicalForm
1179	power ( const Variable & v, int n )
1180	{
1181	ASSERT( n >= 0, "illegal exponent" );
1182	if ( n == 0 )
1183	return 1;
1184	else if ( n == 1 )
1185	return v;
1186	else if ( v.level() < 0 ) {
1187	CanonicalForm result( v, n-1 );
1188	return result * v;
1189	}
1190	else
1191	return CanonicalForm( v, n );
1192	}
1193
1194
1195	int initializeGMP();
1196	int initializeCharacteristic();
1197	#ifdef SINGULAR
1198	int mmInit(void);
1199	#endif
1200
1201	int
1202	initCanonicalForm( void )
1203	{
1204	static bool initialized = false;
1205	if ( ! initialized ) {
1206	#if (defined (USE_MEMUTIL) && ! defined (USE_OLD_MEMMAN)) \|\| defined (SINGULAR)
1207	(void)mmInit();
1208	#endif
1209
1210	(void)initializeCharacteristic();
1211	(void)initializeGMP();
1212	initPT();
1213	initialized = true;
1214	}
1215	return 1;
1216	}
1217
1218
1219	CanonicalForm
1220	CanonicalForm::mapinto () const
1221	{
1222	ASSERT( is_imm( value ) \|\| ! value->inExtension(), "cannot map into different Extension" );
1223	if ( is_imm( value ) )
1224	if ( getCharacteristic() == 0 )
1225	if ( is_imm( value ) == FFMARK )
1226	return CanonicalForm( int2imm( ff_symmetric( imm2int( value ) ) ) );
1227	else if ( is_imm( value ) == GFMARK )
1228	return CanonicalForm( int2imm( ff_symmetric( gf_gf2ff( imm2int( value ) ) ) ) );
1229	else
1230	return *this;
1231	else if ( CFFactory::gettype() == PrimePowerDomain )
1232	return CanonicalForm( CFFactory::basic( imm2int( value ) ) );
1233	else if ( getGFDegree() == 1 )
1234	return CanonicalForm( int2imm_p( ff_norm( imm2int( value ) ) ) );
1235	else
1236	return CanonicalForm( int2imm_gf( gf_int2gf( imm2int( value ) ) ) );
1237	else if ( value->inBaseDomain() )
1238	if ( getCharacteristic() == 0 )
1239	if ( value->levelcoeff() == PrimePowerDomain )
1240	return CFFactory::basic( getmpi( value, true ) );
1241	else
1242	return *this;
1243	else if ( CFFactory::gettype() == PrimePowerDomain ) {
1244	ASSERT( value->levelcoeff() == PrimePowerDomain \|\| value->levelcoeff() == IntegerDomain, "no proper map defined" );
1245	if ( value->levelcoeff() == PrimePowerDomain )
1246	return *this;
1247	else
1248	return CFFactory::basic( getmpi( value ) );
1249	}
1250	else {
1251	int val;
1252	if ( value->levelcoeff() == IntegerDomain )
1253	val = value->intmod( ff_prime );
1254	else if ( value->levelcoeff() == RationalDomain )
1255	return num().mapinto() / den().mapinto();
1256	else {
1257	ASSERT( 0, "illegal domain" );
1258	return 0;
1259	}
1260	if ( getGFDegree() > 1 )
1261	return CanonicalForm( int2imm_gf( gf_int2gf( val ) ) );
1262	else
1263	return CanonicalForm( int2imm_p( val ) );
1264	}
1265	else {
1266	Variable x = value->variable();
1267	CanonicalForm result;
1268	for ( CFIterator i = *this; i.hasTerms(); i++ )
1269	result += power( x, i.exp() ) * i.coeff().mapinto();
1270	return result;
1271	}
1272	}
1273
1274	void
1275	On( int sw )
1276	{
1277	cf_glob_switches.On( sw );
1278	}
1279
1280	void
1281	Off( int sw )
1282	{
1283	cf_glob_switches.Off( sw );
1284	}
1285
1286	bool
1287	isOn( int sw )
1288	{
1289	return cf_glob_switches.isOn( sw );
1290	}
1291
1292	bool
1293	CanonicalForm::isFFinGF() const
1294	{
1295	return is_imm( value ) == GFMARK && gf_isff( imm2int( value ) );
1296	}
1297
1298	//{{{ CanonicalForm CanonicalForm::sqrt() const
1299	//{{{ docu
1300	//
1301	// sqrt() - calculate integer square root.
1302	//
1303	// CO has to be an integer greater or equal zero. Returns the
1304	// largest integer less or equal sqrt(CO).
1305	//
1306	// In the immediate case, we use the newton method to find the
1307	// root. The algorithm is from H. Cohen - 'A Course in
1308	// Computational Algebraic Number Theory', ch. 1.7.1.
1309	//
1310	// See also: InternalCF::sqrt(), InternalInteger::sqrt()
1311	//
1312	//}}}
1313	CanonicalForm
1314	CanonicalForm::sqrt() const
1315	{
1316	if ( is_imm( value ) ) {
1317	ASSERT( is_imm( value ) == INTMARK, "sqrt() not implemented" );
1318	int n = imm2int( value );
1319	ASSERT( n >= 0, "arg to sqrt() less than zero" );
1320	if ( n == 0 \|\| n == 1 )
1321	return CanonicalForm( CFFactory::basic( n ) );
1322	else {
1323	int x, y = n;
1324	do {
1325	x = y;
1326	// the intermediate result may not fit into an
1327	// integer, but the result does
1328	y = (unsigned int)(x + n/x)/2;
1329	} while ( y < x );
1330	return CanonicalForm( CFFactory::basic( x ) );
1331	}
1332	}
1333	else
1334	return CanonicalForm( value->sqrt() );
1335	}
1336	//}}}
1337
1338	//{{{ int CanonicalForm::ilog2 () const
1339	//{{{ docu
1340	//
1341	// ilog2() - integer logarithm to base 2.
1342	//
1343	// Returns the largest integer less or equal logarithm of CO to
1344	// base 2. CO should be a positive integer.
1345	//
1346	// See also: InternalCF::ilog2(), InternalInteger::ilog2()
1347	//
1348	//}}}
1349	int
1350	CanonicalForm::ilog2 () const
1351	{
1352	if ( is_imm( value ) ) {
1353	ASSERT( is_imm( value ) == INTMARK, "ilog2() not implemented" );
1354	int a = imm2int( value );
1355	ASSERT( a > 0, "arg to ilog2() less or equal zero" );
1356	int n = -1;
1357	while ( a != 0 ) {
1358	n++;
1359	a /= 2;
1360	}
1361	return n;
1362	}
1363	else
1364	return value->ilog2();
1365	}
1366	//}}}
1367
1368	bool
1369	divides ( const CanonicalForm & f, const CanonicalForm & g )
1370	{
1371	if ( g.level() > 0 && g.level() == f.level() )
1372	if ( divides( f.tailcoeff(), g.tailcoeff() ) && divides( f.LC(), g.LC() ) ) {
1373	CanonicalForm q, r;
1374	bool ok = divremt( g, f, q, r );
1375	return ok && r == 0;
1376	}
1377	else
1378	return false;
1379	else {
1380	CanonicalForm q, r;
1381	bool ok = divremt( g, f, q, r );
1382	return ok && r == 0;
1383	}
1384	}

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

Download in other formats: