source: git/factory/int_int.cc @ 16055bd

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