source: git/factory/int_int.cc @ 8d1432e

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