source: git/factory/int_int.cc @ fc732a9

spielwiese
Last change on this file since fc732a9 was fc732a9, checked in by Jens Schmidt <schmidt@…>, 26 years ago
***** merge from branch `factory-gcd' to main trunk git-svn-id: file:///usr/local/Singular/svn/trunk@1251 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 12.0 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id: int_int.cc,v 1.12 1998-03-17 15:56:04 schmidt Exp $ */
3
4#include <config.h>
5
6#include "imm.h"
7#include "int_int.h"
8#include "int_rat.h"
9#include "cf_gmp.h"
10#include "gmpext.h"
11#include "canonicalform.h"
12 
13InternalInteger::InternalInteger()
14{
15    mpz_init( &thempi );
16}
17
18InternalInteger::InternalInteger( const int i )
19{
20    mpz_init_set_si( &thempi, i );
21}
22
23InternalInteger::InternalInteger( const MP_INT & mpi) : thempi( mpi ) {}
24
25InternalInteger::InternalInteger( const char * str )
26{
27    mpz_init_set_str( &thempi, str, 10 );
28}
29
30InternalInteger::~InternalInteger()
31{
32    mpz_clear( &thempi );
33}
34
35InternalCF* InternalInteger::deepCopyObject() const
36{
37    MP_INT dummy;
38    mpz_init_set( &dummy, &thempi );
39    return new InternalInteger( dummy );
40}
41
42#ifndef NOSTREAMIO
43void InternalInteger::print( ostream & os, char * c )
44{
45    if ( *c == '*' && mpz_cmp_si( &thempi, 1 ) == 0 )
46        os << c+1;
47    else if ( *c == '*' && mpz_cmp_si( &thempi, -1 ) == 0 )
48        os << '-' << c+1;
49    else {
50        char * str = new char[mpz_sizeinbase( &thempi, 10 ) + 2];
51        str = mpz_get_str( str, 10, &thempi );
52        os << str << c;
53        delete [] str;
54    }
55}
56#endif /* NOSTREAMIO */
57
58bool InternalInteger::isZero() const
59{
60    return mpz_cmp_si( &thempi, 0 ) == 0;
61}
62
63bool InternalInteger::isOne() const
64{
65    return mpz_cmp_si( &thempi, 1 ) == 0;
66}
67
68bool InternalInteger::is_imm() const
69{
70    return mpz_is_imm( &thempi );
71}
72
73InternalCF* InternalInteger::genZero()
74{
75    if ( isZero() )
76        return copyObject();
77    else
78        return new InternalInteger();
79}
80
81InternalCF* InternalInteger::genOne()
82{
83    if ( isOne() )
84        return copyObject();
85    else
86        return new InternalInteger( 1 );
87}
88
89InternalCF* InternalInteger::neg()
90{
91    if ( getRefCount() > 1 ) {
92        decRefCount();
93        MP_INT dummy;
94        mpz_init( &dummy );
95        mpz_neg( &dummy, &thempi );
96        return new InternalInteger( dummy );
97    }
98    else {
99        mpz_neg( &thempi, &thempi );
100        return this;
101    }
102}
103
104
105InternalCF* InternalInteger::addsame( InternalCF * c )
106{
107    if ( getRefCount() > 1 ) {
108        decRefCount();
109        MP_INT dummy;
110        mpz_init( &dummy );
111        mpz_add( &dummy, &thempi, &MPI( c ) );
112        if ( mpz_is_imm( &dummy ) ) {
113            InternalCF * res = int2imm( mpz_get_si( &dummy ) );
114            mpz_clear( &dummy );
115            return res;
116        }
117        else
118            return new InternalInteger( dummy );
119    }
120    else {
121        mpz_add( &thempi, &thempi, &MPI( c ) );
122        if ( mpz_is_imm( &thempi ) ) {
123            InternalCF * res = int2imm( mpz_get_si( &thempi ) );
124            delete this;
125            return res;
126        }
127        else
128            return this;
129    }
130}
131
132InternalCF* InternalInteger::subsame( InternalCF * c )
133{
134    if ( getRefCount() > 1 ) {
135        decRefCount();
136        MP_INT dummy;
137        mpz_init( &dummy );
138        mpz_sub( &dummy, &thempi, &MPI( c ) );
139        if ( mpz_is_imm( &dummy ) ) {
140            InternalCF * res = int2imm( mpz_get_si( &dummy ) );
141            mpz_clear( &dummy );
142            return res;
143        }
144        else
145            return new InternalInteger( dummy );
146    }
147    else {
148        mpz_sub( &thempi, &thempi, &MPI( c ) );
149        if ( mpz_is_imm( &thempi ) ) {
150            InternalCF * res = int2imm( mpz_get_si( &thempi ) );
151            delete this;
152            return res;
153        }
154        else
155            return this;
156    }
157}
158
159InternalCF* InternalInteger::mulsame( InternalCF * c )
160{
161    if ( getRefCount() > 1 ) {
162        decRefCount();
163        MP_INT dummy;
164        mpz_init( &dummy );
165        mpz_mul( &dummy, &thempi, &MPI( c ) );
166        if ( mpz_is_imm( &dummy ) ) {
167            InternalCF * res = int2imm( mpz_get_si( &dummy ) );
168            mpz_clear( &dummy );
169            return res;
170        }
171        else
172            return new InternalInteger( dummy );
173    }
174    else {
175        mpz_mul( &thempi, &thempi, &MPI( c ) );
176        if ( mpz_is_imm( &thempi ) ) {
177            InternalCF * res = int2imm( mpz_get_si( &thempi ) );
178            delete this;
179            return res;
180        }
181        else
182            return this;
183    }
184}
185
186//{{{ int InternalInteger::comparesame, comparecoeff ( InternalCF * c )
187// docu: see CanonicalForm::operator <(), CanonicalForm::operator ==()
188int
189InternalInteger::comparesame ( InternalCF * c )
190{
191    ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, "incompatible base coefficients" );
192    return mpz_cmp( &thempi, &MPI( c ) );
193}
194
195int
196InternalInteger::comparecoeff ( InternalCF * c )
197{
198    ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
199    return mpz_cmp_si( &thempi, imm2int( c ) );
200}
201//}}}
202
203InternalCF* InternalInteger::addcoeff( InternalCF* c )
204{
205    ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
206    int cc = imm2int( c );
207    if ( getRefCount() > 1 ) {
208        decRefCount();
209        MP_INT dummy;
210        mpz_init( &dummy );
211        if ( cc < 0 )
212            mpz_sub_ui( &dummy, &thempi, -cc );
213        else
214            mpz_add_ui( &dummy, &thempi, cc );
215        if ( mpz_is_imm( &dummy ) ) {
216            InternalCF * res = int2imm( mpz_get_si( &dummy ) );
217            mpz_clear( &dummy );
218            return res;
219        }
220        else
221            return new InternalInteger( dummy );
222    }
223    else {
224        if ( cc < 0 )
225            mpz_sub_ui( &thempi, &thempi, -cc );
226        else
227            mpz_add_ui( &thempi, &thempi, cc );
228        if ( mpz_is_imm( &thempi ) ) {
229            InternalCF * res = int2imm( mpz_get_si( &thempi ) );
230            delete this;
231            return res;
232        }
233        else
234            return this;
235    }
236}
237
238InternalCF* InternalInteger::subcoeff( InternalCF* c, bool negate )
239{
240    ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
241    int cc = imm2int( c );
242    if ( getRefCount() > 1 ) {
243        decRefCount();
244        MP_INT dummy;
245        if ( negate ) {
246            mpz_init_set_si( &dummy, cc );
247            mpz_sub( &dummy, &dummy, &thempi );
248        }
249        else {
250            mpz_init( &dummy );
251            if ( cc < 0 )
252                mpz_add_ui( &dummy, &thempi, -cc );
253            else
254                mpz_sub_ui( &dummy, &thempi, cc );
255        }
256        if ( mpz_is_imm( &dummy ) ) {
257            InternalCF * res = int2imm( mpz_get_si( &dummy ) );
258            mpz_clear( &dummy );
259            return res;
260        }
261        else
262            return new InternalInteger( dummy );
263    }
264    else {
265        if ( negate ) {
266            MP_INT dummy;
267            mpz_init_set_si( &dummy, cc );
268            mpz_sub( &thempi, &dummy, &thempi );
269            mpz_clear( &dummy );
270        }
271        else
272            if ( cc < 0 )
273                mpz_add_ui( &thempi, &thempi, -cc );
274            else
275                mpz_sub_ui( &thempi, &thempi, cc );
276        if ( mpz_is_imm( &thempi ) ) {
277            InternalCF * res = int2imm( mpz_get_si( &thempi ) );
278            delete this;
279            return res;
280        }
281        else
282            return this;
283    }
284}
285
286InternalCF* InternalInteger::mulcoeff( InternalCF* c )
287{
288    ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
289    int cc = imm2int( c );
290    if ( getRefCount() > 1 ) {
291        decRefCount();
292        MP_INT dummy;
293        mpz_init( &dummy );
294        if ( cc < 0 ) {
295            mpz_mul_ui( &dummy, &thempi, -cc );
296            mpz_neg( &dummy, &dummy );
297        }
298        else
299            mpz_mul_ui( &dummy, &thempi, cc );
300        if ( mpz_is_imm( &dummy ) ) {
301            InternalCF * res = int2imm( mpz_get_si( &dummy ) );
302            mpz_clear( &dummy );
303            return res;
304        }
305        else
306            return new InternalInteger( dummy );
307    }
308    else {
309        MP_INT dummy;
310        mpz_init_set_si( &dummy, cc );
311        if ( cc < 0 ) {
312            mpz_mul_ui( &thempi, &thempi, -cc );
313            mpz_neg( &thempi, &thempi );
314        }
315        else
316            mpz_mul_ui( &thempi, &thempi, cc );
317        if ( mpz_is_imm( &thempi ) ) {
318            InternalCF * res = int2imm( mpz_get_si( &thempi ) );
319            delete this;
320            return res;
321        }
322        else
323            return this;
324    }
325}
326
327//{{{ InternalCF * InternalInteger::bgcdsame, bgcdcoeff ( const InternalCF * const c )
328// docu: see CanonicalForm::bgcd()
329InternalCF *
330InternalInteger::bgcdsame ( const InternalCF * const c ) const
331{
332    ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, "incompatible base coefficients" );
333
334    // simply return 1 if we are calculating over the rationals
335    if ( cf_glob_switches.isOn( SW_RATIONAL ) )
336         return int2imm( 1 );
337
338    // calculate gcd
339    MP_INT result;
340    mpz_init( &result );
341    mpz_gcd( &result, &thempi, &MPI( c ) );
342    mpz_abs( &result, &result );
343
344    // check for immediate result
345    if ( mpz_is_imm( &result ) ) {
346        InternalCF * res = int2imm( mpz_get_si( &result ) );
347        mpz_clear( &result );
348        return res;
349    }
350    else
351        return new InternalInteger( result );
352}
353
354InternalCF *
355InternalInteger::bgcdcoeff ( const InternalCF * const c )
356{
357    ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
358
359    // simply return 1 if we are calculating over the rationals
360    if ( cf_glob_switches.isOn( SW_RATIONAL ) )
361         return int2imm( 1 );
362
363    int cInt = imm2int( c );
364
365    // trivial cases
366    if ( cInt == 1 || cInt == -1 )
367        return int2imm( 1 );
368    else if ( cInt == 0 )
369        return copyObject();
370
371    // calculate gcd.  We need a positive operand since
372    // `mpz_gcd_ui()' operates an unsigned int's only.
373    if ( cInt < 0 ) cInt = -cInt;
374    MP_INT dummy;
375    mpz_init( &dummy );
376    // we do not need dummy since we know that cInt != 0
377    cInt = mpz_gcd_ui( &dummy, &thempi, cInt );
378    mpz_clear( &dummy );
379    if ( cInt < 0 ) cInt = -cInt;
380    return int2imm( cInt );
381}
382//}}}
383
384//{{{ InternalCF * InternalInteger::bextgcdsame( InternalCF * c, CanonicalForm & a, CanonicalForm & b )
385InternalCF *
386InternalInteger::bextgcdsame( InternalCF * c, CanonicalForm & a, CanonicalForm & b )
387{
388    ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, "incompatible base coefficients" );
389
390    // simply return 1 if we are calculating over the rationals
391    if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
392        a = 1/CanonicalForm( copyObject() ); b = 0;
393        return int2imm( 1 );
394    }
395
396    // calculate extended gcd
397    MP_INT result;
398    MP_INT aMPI;
399    MP_INT bMPI;
400    mpz_init( &result );
401    mpz_init( &aMPI );
402    mpz_init( &bMPI );
403    mpz_gcdext( &result, &aMPI, &bMPI, &thempi, &MPI( c ) );
404   
405    // check and modify signs
406    if ( mpz_sgn( &result ) < 0 ) {
407        mpz_neg( &result, &result );
408        mpz_neg( &aMPI, &aMPI );
409        mpz_neg( &bMPI, &bMPI );
410    }
411
412    // postconditioning of result
413    if ( mpz_is_imm( &aMPI ) ) {
414        a = CanonicalForm( int2imm( mpz_get_si( &aMPI ) ) );
415        mpz_clear( &aMPI );
416    } else
417        a = CanonicalForm( new InternalInteger( aMPI ) );
418    if ( mpz_is_imm( &bMPI ) ) {
419        b = CanonicalForm( int2imm( mpz_get_si( &bMPI ) ) );
420        mpz_clear( &bMPI );
421    } else
422        b = CanonicalForm( new InternalInteger( bMPI ) );
423    if ( mpz_is_imm( &result ) ) {
424        InternalCF * res = int2imm( mpz_get_si( &result ) );
425        mpz_clear( &result );
426        return res;
427    }
428    else
429        return new InternalInteger( result );
430}
431
432InternalCF *
433InternalInteger::bextgcdcoeff( InternalCF * c, CanonicalForm & a, CanonicalForm & b )
434{
435    ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
436
437    // simply return 1 if we are calculating over the rationals
438    if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
439        a = 1/CanonicalForm( copyObject() ); b = 0;
440        return int2imm( 1 );
441    }
442
443    int cInt = imm2int( c );
444
445    // trivial cases
446    if ( cInt == 1 || cInt == -1 ) {
447        a = 0; b = cInt;
448        return int2imm( 1 );
449    } else if ( cInt == 0 ) {
450        a = 1; b = 0;
451        return copyObject();
452    }
453
454    // calculate q and r such that CO = q*cInt + r
455    InternalCF * q = 0, * r = 0;
456    divremcoeff( c, q, r, false );
457
458    // we do not repeat all the code to calculate the gcd of two
459    // immediates.  Note that r is an immediate since c != 0, so
460    // we do not have to destroy it.  q is destroyed by the
461    // CanonicalForm destructor, hence we do not need to worry
462    // about it, either.
463    CanonicalForm aPrime, bPrime;
464    CanonicalForm result = bextgcd( c, r, aPrime, bPrime );
465    a = bPrime;
466    b = aPrime - CanonicalForm( q ) * bPrime;
467
468    return result.getval();
469}
470//}}}
471
472int InternalInteger::intval() const
473{
474  return (int)mpz_get_si( &thempi );
475}
476
477int InternalInteger::intmod( int p ) const
478{
479  return (int)mpz_mmod_ui( 0, &thempi, (unsigned long)p );
480}
481
482//{{{ int InternalInteger::sign () const
483// docu: see CanonicalForm::sign()
484int
485InternalInteger::sign () const
486{
487    return mpz_sgn( &thempi );
488}
489//}}}
490
491//{{{ InternalCF * InternalInteger::sqrt ()
492// docu: see CanonicalForm::sqrt()
493InternalCF *
494InternalInteger::sqrt ()
495{
496    ASSERT( mpz_cmp_si( &thempi, 0 ) >= 0, "sqrt() argument < 0" );
497    MP_INT result;
498    mpz_init( &result );
499    mpz_sqrt( &result, &thempi );
500    if ( mpz_is_imm( &result ) ) {
501        InternalCF * res = int2imm( mpz_get_si( &result ) );
502        mpz_clear( &result );
503        return res;
504    }
505    else
506        return new InternalInteger( result );
507}
508//}}}
509
510//{{{ int InternalInteger::ilog2 ()
511// docu: see CanonicalForm::ilog2()
512int
513InternalInteger::ilog2 ()
514{
515    ASSERT( mpz_cmp_si( &thempi, 0 ) > 0, "log() argument <= 0" );
516    return mpz_sizeinbase( &thempi, 2 ) - 1;
517}
518//}}}
Note: See TracBrowser for help on using the repository browser.