source: git/factory/int_int.cc @ ba5e9e

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