My Project  debian-1:4.1.2-p1+ds-2
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_t dummy;
21  mpz_init_set( dummy, thempi );
22  return new InternalInteger( dummy );
23 }
24 
25 #ifndef NOSTREAMIO
26 void InternalInteger::print( OSTREAM & os, char * c )
27 {
28  if ( *c == '*' && mpz_cmp_si( thempi, 1 ) == 0 )
29  os << c+1;
30  else if ( *c == '*' && mpz_cmp_si( thempi, -1 ) == 0 )
31  os << '-' << c+1;
32  else {
33  char * str = new char[mpz_sizeinbase( thempi, 10 ) + 2];
34  str = mpz_get_str( str, 10, thempi );
35  os << str << c;
36  delete [] str;
37  }
38 }
39 #endif /* NOSTREAMIO */
40 
42 {
43  return mpz_is_imm( thempi );
44 }
45 
47 {
48  if ( isZero() )
49  return copyObject();
50  else
51  return new InternalInteger();
52 }
53 
55 {
56  if ( isOne() )
57  return copyObject();
58  else
59  return new InternalInteger( 1 );
60 }
61 
62 /** InternalCF * InternalInteger::neg ()
63  * @sa CanonicalForm::operator -()
64 **/
65 InternalCF *
67 {
68  if ( getRefCount() > 1 )
69  {
70  decRefCount();
71  mpz_t dummy;
72  mpz_init_set( dummy, thempi );
73  mpz_neg( dummy, dummy );
74  return new InternalInteger( dummy );
75  }
76  else
77  {
78  mpz_neg( thempi, thempi );
79  return this;
80  }
81 }
82 
83 
84 
86 {
87  if ( getRefCount() > 1 )
88  {
89  decRefCount();
90  mpz_t dummy;
91  mpz_init( dummy );
92  mpz_add( dummy, thempi, MPI( c ) );
93  if ( mpz_is_imm( dummy ) )
94  {
95  InternalCF * res = int2imm( mpz_get_si( dummy ) );
96  mpz_clear( dummy );
97  return res;
98  }
99  else
100  return new InternalInteger( dummy );
101  }
102  else
103  {
104  mpz_add( thempi, thempi, MPI( c ) );
105  if ( mpz_is_imm( thempi ) )
106  {
107  InternalCF * res = int2imm( mpz_get_si( thempi ) );
108  delete this;
109  return res;
110  }
111  else
112  return this;
113  }
114 }
115 
117 {
118  if ( getRefCount() > 1 )
119  {
120  decRefCount();
121  mpz_t dummy;
122  mpz_init( dummy );
123  mpz_sub( dummy, thempi, MPI( c ) );
124  if ( mpz_is_imm( dummy ) )
125  {
126  InternalCF * res = int2imm( mpz_get_si( dummy ) );
127  mpz_clear( dummy );
128  return res;
129  }
130  else
131  return new InternalInteger( dummy );
132  }
133  else
134  {
135  mpz_sub( thempi, thempi, MPI( c ) );
136  if ( mpz_is_imm( thempi ) )
137  {
138  InternalCF * res = int2imm( mpz_get_si( thempi ) );
139  delete this;
140  return res;
141  }
142  else
143  return this;
144  }
145 }
146 
148 {
149  if ( getRefCount() > 1 )
150  {
151  decRefCount();
152  mpz_t dummy;
153  mpz_init( dummy );
154  mpz_mul( dummy, thempi, MPI( c ) );
155  #if 0
156  if ( mpz_is_imm( dummy ) )
157  {
158  // can this happen ???
159  InternalCF * res = int2imm( mpz_get_si( dummy ) );
160  mpz_clear( dummy );
161  return res;
162  }
163  else
164  #endif
165  return new InternalInteger( dummy );
166  }
167  else
168  {
169  mpz_mul( thempi, thempi, MPI( c ) );
170  #if 0
171  if ( mpz_is_imm( &thempi ) )
172  {
173  // can this happen ???
174  InternalCF * res = int2imm( mpz_get_si( &thempi ) );
175  delete this;
176  return res;
177  }
178  else
179  #endif
180  return this;
181  }
182 }
183 
184 /**
185  * @sa CanonicalForm::operator <(), CanonicalForm::operator ==(), InternalInteger::comparecoeff()
186 **/
187 int
189 {
190  ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, "incompatible base coefficients" );
191  return mpz_cmp( thempi, MPI( c ) );
192 }
193 
194 /**
195  * @sa CanonicalForm::operator <(), CanonicalForm::operator ==(), InternalInteger::comparesame()
196 **/
197 int
199 {
200  ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
201  return mpz_cmp_si( thempi, imm2int( c ) );
202 }
203 
204 
206 {
207  ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
208  long cc = imm2int( c );
209  if ( getRefCount() > 1 )
210  {
211  decRefCount();
212  mpz_t dummy;
213  mpz_init( dummy );
214  if ( cc < 0 )
215  mpz_sub_ui( dummy, thempi, -cc );
216  else
217  mpz_add_ui( dummy, thempi, cc );
218  if ( mpz_is_imm( dummy ) )
219  {
220  InternalCF * res = int2imm( mpz_get_si( dummy ) );
221  mpz_clear( dummy );
222  return res;
223  }
224  else
225  return new InternalInteger( dummy );
226  }
227  else
228  {
229  if ( cc < 0 )
230  mpz_sub_ui( thempi, thempi, -cc );
231  else
232  mpz_add_ui( thempi, thempi, cc );
233  if ( mpz_is_imm( thempi ) )
234  {
235  InternalCF * res = int2imm( mpz_get_si( thempi ) );
236  delete this;
237  return res;
238  }
239  else
240  return this;
241  }
242 }
243 
245 {
246  ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
247  long cc = imm2int( c );
248  if ( getRefCount() > 1 )
249  {
250  decRefCount();
251  mpz_t dummy;
252  if ( negate )
253  {
254  mpz_init_set_si( dummy, cc );
255  mpz_sub( dummy, dummy, thempi );
256  }
257  else
258  {
259  mpz_init( dummy );
260  if ( cc < 0 )
261  mpz_add_ui( dummy, thempi, -cc );
262  else
263  mpz_sub_ui( dummy, thempi, cc );
264  }
265  if ( mpz_is_imm( dummy ) )
266  {
267  InternalCF * res = int2imm( mpz_get_si( dummy ) );
268  mpz_clear( dummy );
269  return res;
270  }
271  else
272  return new InternalInteger( dummy );
273  }
274  else
275  {
276  if ( negate )
277  {
278  mpz_t dummy;
279  mpz_init_set_si( dummy, cc );
280  mpz_sub( thempi, dummy, thempi );
281  mpz_clear( dummy );
282  }
283  else
284  if ( cc < 0 )
285  mpz_add_ui( thempi, thempi, -cc );
286  else
287  mpz_sub_ui( thempi, thempi, cc );
288  if ( mpz_is_imm( thempi ) )
289  {
290  InternalCF * res = int2imm( mpz_get_si( thempi ) );
291  delete this;
292  return res;
293  }
294  else
295  return this;
296  }
297 }
298 
300 {
301  ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
302  long cc = imm2int( c );
303  if ( getRefCount() > 1 )
304  {
305  decRefCount();
306  mpz_t dummy;
307  mpz_init( dummy );
308  if ( cc < 0 )
309  {
310  mpz_mul_ui( dummy, thempi, -cc );
311  mpz_neg( dummy, dummy );
312  }
313  else
314  mpz_mul_ui( dummy, thempi, cc );
315  if ( mpz_is_imm( dummy ) )
316  {
317  InternalCF * res = int2imm( mpz_get_si( dummy ) );
318  mpz_clear( dummy );
319  return res;
320  }
321  else
322  return new InternalInteger( dummy );
323  }
324  else
325  {
326  if ( cc < 0 )
327  {
328  mpz_mul_ui( thempi, thempi, -cc );
329  mpz_neg( thempi, thempi );
330  }
331  else
332  mpz_mul_ui( thempi, thempi, cc );
333  if ( mpz_is_imm( thempi ) )
334  {
335  InternalCF * res = int2imm( mpz_get_si( thempi ) );
336  delete this;
337  return res;
338  }
339  else
340  return this;
341  }
342 }
343 
344 /**
345  * @sa CanonicalForm::bgcd(), InternalInteger::bgcdcoeff()
346 **/
347 InternalCF *
348 InternalInteger::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
354  return int2imm( 1 );
355 
356  // calculate gcd
357  mpz_t result;
358  mpz_init( result );
359  mpz_gcd( result, thempi, MPI( c ) );
360  mpz_abs( result, result );
361 
362  // check for immediate result
363  if ( mpz_is_imm( result ) )
364  {
365  InternalCF * res = int2imm( mpz_get_si( result ) );
366  mpz_clear( result );
367  return res;
368  }
369  else
370  return new InternalInteger( result );
371 }
372 
373 /**
374  * @sa CanonicalForm::bgcd(), InternalInteger::bgcdsame()
375 **/
376 InternalCF *
378 {
379  ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
380 
381  // simply return 1 if we are calculating over the rationals
383  return int2imm( 1 );
384 
385  long cInt = imm2int( c );
386 
387  // trivial cases
388  if ( cInt == 1 || cInt == -1 )
389  return int2imm( 1 );
390  else if ( cInt == 0 )
391  return copyObject();
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;
396  mpz_t dummy;
397  mpz_init( dummy );
398  // we do not need dummy since we know that cInt != 0
399  cInt = mpz_gcd_ui( dummy, thempi, cInt );
400  mpz_clear( dummy );
401  if ( cInt < 0 ) cInt = -cInt;
402  return int2imm( cInt );
403 }
404 
405 /**
406  * @sa CanonicalForm::bextgcd(), InternalInteger::bextgcdcoeff()
407 **/
408 InternalCF *
410 {
411  ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, "incompatible base coefficients" );
412 
413  // simply return 1 if we are calculating over the rationals
415  {
416  a = 1/CanonicalForm( copyObject() ); b = 0;
417  return int2imm( 1 );
418  }
419 
420  // calculate extended gcd
421  mpz_t result, aMPI, bMPI;
422  mpz_init( result );
423  mpz_init( aMPI );
424  mpz_init( bMPI );
425  mpz_gcdext( result, aMPI, bMPI, thempi, MPI( c ) );
426 
427  // check and modify signs
428  if ( mpz_sgn( result ) < 0 )
429  {
430  mpz_neg( result, result );
431  mpz_neg( aMPI, aMPI );
432  mpz_neg( bMPI, bMPI );
433  }
434 
435  // postconditioning of result
436  if ( mpz_is_imm( aMPI ) )
437  {
438  a = CanonicalForm( int2imm( mpz_get_si( aMPI ) ) );
439  mpz_clear( aMPI );
440  }
441  else
442  a = CanonicalForm( new InternalInteger( aMPI ) );
443  if ( mpz_is_imm( bMPI ) )
444  {
445  b = CanonicalForm( int2imm( mpz_get_si( bMPI ) ) );
446  mpz_clear( bMPI );
447  }
448  else
449  b = CanonicalForm( new InternalInteger( bMPI ) );
450  if ( mpz_is_imm( result ) )
451  {
452  InternalCF * res = int2imm( mpz_get_si( result ) );
453  mpz_clear( result );
454  return res;
455  }
456  else
457  return new InternalInteger( result );
458 }
459 
460 /**
461  * @sa CanonicalForm::bextgcd(), InternalInteger::bextgcdsame()
462 **/
463 InternalCF *
465 {
466  ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
467 
468  // simply return 1 if we are calculating over the rationals
470  {
471  a = 1/CanonicalForm( copyObject() ); b = 0;
472  return int2imm( 1 );
473  }
474 
475  long cInt = imm2int( c );
476 
477  // trivial cases
478  if ( cInt == 1 || cInt == -1 )
479  {
480  a = 0; b = cInt;
481  return int2imm( 1 );
482  }
483  else if ( cInt == 0 )
484  {
485  a = 1; b = 0;
486  return copyObject();
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 
507 {
508  return mpz_get_si( thempi );
509 }
510 
511 int InternalInteger::intmod( int p ) const
512 {
513  return (int)mpz_fdiv_ui( thempi, (unsigned long)p );
514 }
515 
516 /** int InternalInteger::sign () const
517  * @sa CanonicalForm::sign()
518 **/
519 int
521 {
522  return mpz_sgn( thempi );
523 }
524 
525 /** InternalCF * InternalInteger::sqrt ()
526  * @sa CanonicalForm::sqrt()
527 **/
528 InternalCF *
530 {
531  ASSERT( mpz_cmp_si( thempi, 0 ) >= 0, "sqrt() argument < 0" );
532  mpz_t result;
533  mpz_init( result );
534  mpz_sqrt( result, thempi );
535  if ( mpz_is_imm( result ) )
536  {
537  InternalCF * res = int2imm( mpz_get_si( result ) );
538  mpz_clear( result );
539  return res;
540  }
541  else
542  return new InternalInteger( result );
543 }
544 
545 /** int InternalInteger::ilog2 ()
546  * @sa CanonicalForm::ilog2()
547 **/
548 int
550 {
551  ASSERT( mpz_cmp_si( thempi, 0 ) > 0, "log() argument <= 0" );
552  return mpz_sizeinbase( thempi, 2 ) - 1;
553 }
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Header for factory's main class CanonicalForm.
#define OSTREAM
Definition: canonicalform.h:16
int p
Definition: cfModGcd.cc:4019
CanonicalForm b
Definition: cfModGcd.cc:4044
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:29
#define IntegerDomain
Definition: cf_defs.h:26
INST_VAR CFSwitches cf_glob_switches
Definition: cf_switches.cc:41
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55
factory's main class
Definition: canonicalform.h:83
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
virtual bool isZero() const
Definition: int_cf.cc:24
int getRefCount()
Definition: int_cf.h:51
virtual int levelcoeff() const
Definition: int_cf.h:68
int decRefCount()
Definition: int_cf.h:53
InternalCF * copyObject()
Definition: int_cf.h:62
virtual bool isOne() const
bool InternalCF::isOne, isZero () const
Definition: int_cf.cc:18
factory's class for integers
Definition: int_int.h:41
InternalCF * deepCopyObject() const
Definition: int_int.cc:18
InternalCF * sqrt()
InternalCF * InternalInteger::sqrt ()
Definition: int_int.cc:529
mpz_t thempi
Definition: int_int.h:43
static const omBin InternalInteger_bin
Definition: int_int.h:54
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition: int_intdiv.cc:308
long intval() const
Definition: int_int.cc:506
InternalCF * mulsame(InternalCF *)
Definition: int_int.cc:147
int ilog2()
int InternalInteger::ilog2 ()
Definition: int_int.cc:549
InternalCF * bgcdcoeff(const InternalCF *const)
Definition: int_int.cc:377
InternalCF * genOne()
Definition: int_int.cc:54
InternalCF * genZero()
Definition: int_int.cc:46
int sign() const
int InternalInteger::sign () const
Definition: int_int.cc:520
InternalCF * addcoeff(InternalCF *)
Definition: int_int.cc:205
InternalCF * subcoeff(InternalCF *, bool)
Definition: int_int.cc:244
InternalCF * bgcdsame(const InternalCF *const) const
Definition: int_int.cc:348
InternalCF * bextgcdsame(InternalCF *, CanonicalForm &, CanonicalForm &)
Definition: int_int.cc:409
bool is_imm() const
Definition: int_int.cc:41
InternalCF * subsame(InternalCF *)
Definition: int_int.cc:116
InternalCF * bextgcdcoeff(InternalCF *, CanonicalForm &, CanonicalForm &)
Definition: int_int.cc:464
InternalCF * mulcoeff(InternalCF *)
Definition: int_int.cc:299
InternalCF * neg()
InternalCF * InternalInteger::neg ()
Definition: int_int.cc:66
void print(OSTREAM &, char *)
Definition: int_int.cc:26
int comparesame(InternalCF *)
Definition: int_int.cc:188
int comparecoeff(InternalCF *)
Definition: int_int.cc:198
static mpz_ptr MPI(const InternalCF *const c)
MPI() - return underlying mpz_t of ā€˜c’.
Definition: int_int.h:232
InternalCF * addsame(InternalCF *)
Definition: int_int.cc:85
int intmod(int p) const
Definition: int_int.cc:511
return result
Definition: facAbsBiFact.cc:76
CanonicalForm res
Definition: facAbsFact.cc:64
utility functions for gmp
bool mpz_is_imm(const mpz_t mpi)
Definition: gmpext.h:19
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
static InternalCF * int2imm(long i)
Definition: imm.h:75
const long INTMARK
Definition: imm.h:37
Factory's internal integers.
Factory's internal rationals.
#define omGetSpecBin(size)
Definition: omBin.h:11
omBin_t * omBin
Definition: omStructs.h:12