source: git/factory/int_int.cc

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