int_int.cc
Go to the documentation of this file.
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
16 #endif
17 
19 {
20  mpz_init( thempi );
21 }
22 
24 {
25  mpz_init_set_si( thempi, i );
26 }
27 
29 {
30  mpz_init_set_si( thempi, i );
31 }
32 
33 InternalInteger::InternalInteger( const mpz_ptr mpi) { thempi[0]=*mpi;}
34 
35 InternalInteger::InternalInteger( const char * str, const int base )
36 {
37  mpz_init_set_str( thempi, str, base );
38 }
39 
41 {
42  mpz_clear( thempi );
43 }
44 
46 {
47  mpz_t dummy;
48  mpz_init_set( dummy, thempi );
49  return new InternalInteger( dummy );
50 }
51 
52 #ifndef NOSTREAMIO
53 void 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 
69 {
70  return mpz_is_imm( thempi );
71 }
72 
74 {
75  if ( isZero() )
76  return copyObject();
77  else
78  return new InternalInteger();
79 }
80 
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 **/
92 InternalCF *
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 
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 
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 
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 **/
214 int
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 **/
224 int
226 {
227  ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
228  return mpz_cmp_si( thempi, imm2int( c ) );
229 }
230 
231 
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 
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 
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 **/
374 InternalCF *
375 InternalInteger::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 **/
403 InternalCF *
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 **/
435 InternalCF *
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 **/
490 InternalCF *
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 
534 {
535  return mpz_get_si( thempi );
536 }
537 
538 int 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 **/
546 int
548 {
549  return mpz_sgn( thempi );
550 }
551 
552 /** InternalCF * InternalInteger::sqrt ()
553  * @sa CanonicalForm::sqrt()
554 **/
555 InternalCF *
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 **/
575 int
577 {
578  ASSERT( mpz_cmp_si( thempi, 0 ) > 0, "log() argument <= 0" );
579  return mpz_sizeinbase( thempi, 2 ) - 1;
580 }
Factory's internal rationals.
int comparecoeff(InternalCF *)
Definition: int_int.cc:225
int decRefCount()
Definition: int_cf.h:49
const poly a
Definition: syzextra.cc:212
omBin_t * omBin
Definition: omStructs.h:12
bool is_imm() const
Definition: int_int.cc:68
InternalCF * bgcdcoeff(const InternalCF *const )
Definition: int_int.cc:404
InternalCF * neg()
InternalCF * InternalInteger::neg ()
Definition: int_int.cc:93
mpz_t thempi
Definition: int_int.h:47
InternalCF * int2imm(long i)
Definition: imm.h:71
return P p
Definition: myNF.cc:203
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
char N base
Definition: ValueTraits.h:144
InternalCF * copyObject()
Definition: int_cf.h:58
factory's main class
Definition: canonicalform.h:75
InternalCF * bgcdsame(const InternalCF *const ) const
Definition: int_int.cc:375
InternalCF * bextgcdsame(InternalCF *, CanonicalForm &, CanonicalForm &)
Definition: int_int.cc:436
void print(OSTREAM &, char *)
Definition: int_int.cc:53
int sign() const
int InternalInteger::sign () const
Definition: int_int.cc:547
int comparesame(InternalCF *)
Definition: int_int.cc:215
virtual class for internal CanonicalForm's
Definition: int_cf.h:39
#define IntegerDomain
Definition: cf_defs.h:25
InternalCF * bextgcdcoeff(InternalCF *, CanonicalForm &, CanonicalForm &)
Definition: int_int.cc:491
virtual bool isZero() const
Definition: int_cf.cc:24
InternalCF * deepCopyObject() const
Definition: int_int.cc:45
poly res
Definition: myNF.cc:322
virtual bool isOne() const
bool InternalCF::isOne, isZero () const
Definition: int_cf.cc:18
virtual int levelcoeff() const
Definition: int_cf.h:64
const ring r
Definition: syzextra.cc:208
InternalCF * subsame(InternalCF *)
Definition: int_int.cc:143
InternalCF * genZero()
Definition: int_int.cc:73
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
int i
Definition: cfEzgcd.cc:123
InternalCF * addcoeff(InternalCF *)
Definition: int_int.cc:232
InternalCF * subcoeff(InternalCF *, bool)
Definition: int_int.cc:271
static mpz_ptr MPI(const InternalCF *const c)
MPI() - return underlying mpz_t of `c'.
Definition: int_int.h:235
InternalCF * sqrt()
InternalCF * InternalInteger::sqrt ()
Definition: int_int.cc:556
InternalCF * mulsame(InternalCF *)
Definition: int_int.cc:174
#define omGetSpecBin(size)
Definition: omBin.h:11
long intval() const
Definition: int_int.cc:533
long imm2int(const InternalCF *const imm)
Definition: imm.h:66
utility functions for gmp
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition: int_intdiv.cc:308
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int...
#define OSTREAM
Definition: canonicalform.h:16
const long INTMARK
Definition: imm.h:37
InternalCF * addsame(InternalCF *)
Definition: int_int.cc:112
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75
InternalCF * getval() const
#define ASSERT(expression, message)
Definition: cf_assert.h:99
InternalCF * mulcoeff(InternalCF *)
Definition: int_int.cc:326
int ilog2()
int InternalInteger::ilog2 ()
Definition: int_int.cc:576
bool mpz_is_imm(const mpz_t mpi)
Definition: gmpext.h:20
factory's class for integers
Definition: int_int.h:44
static const omBin InternalInteger_bin
Definition: int_int.h:58
const poly b
Definition: syzextra.cc:213
int intmod(int p) const
Definition: int_int.cc:538
InternalCF * genOne()
Definition: int_int.cc:81
return result
Definition: facAbsBiFact.cc:76
Header for factory's main class CanonicalForm.
Factory's internal integers.
int getRefCount()
Definition: int_cf.h:47