My Project  debian-1:4.1.1-p2+ds-4build3
int_intdiv.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  *
5  * @file int_intdiv.cc
6  *
7  * 'InternalInteger' division algorithms.
8  *
9 **/
10 
11 
12 #include "config.h"
13 
14 
15 #include "canonicalform.h"
16 #include "imm.h"
17 #include "int_cf.h"
18 #include "int_int.h"
19 #include "int_rat.h"
20 #include "factory/cf_gmp.h"
21 #include "gmpext.h"
23 
24 /**
25  * @sa CanonicalForm::operator /(), InternalInteger::dividecoeff()
26 **/
27 InternalCF *
29 {
30  ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
31  "type error: InternalInteger expected" );
32 
33  if ( c == this ) {
34  if ( deleteObject() ) delete this;
35  return int2imm( 1 );
36  }
37 
39  mpz_t n, d;
40  mpz_init_set( n, thempi );
41  mpz_init_set( d, MPI( c ) );
42  if ( deleteObject() ) delete this;
44  return result->normalize_myself();
45  }
46 
47  if ( getRefCount() > 1 ) {
48  decRefCount();
49  mpz_t mpiResult;
50  mpz_init( mpiResult );
51  if ( mpz_sgn( MPI( c ) ) > 0 )
52  mpz_fdiv_q( mpiResult, thempi, MPI( c ) );
53  else
54  mpz_cdiv_q( mpiResult, thempi, MPI( c ) );
55  return normalizeMPI( mpiResult );
56  } else {
57  if ( mpz_sgn( MPI( c ) ) > 0 )
58  mpz_fdiv_q( thempi, thempi, MPI( c ) );
59  else
60  mpz_cdiv_q( thempi, thempi, MPI( c ) );
61  return normalizeMyself();
62  }
63 }
64 
65 /**
66  * @sa CanonicalForm::operator /(), InternalInteger::dividesame()
67 **/
68 InternalCF *
70 {
71  ASSERT( ::is_imm( c ) == INTMARK,
72  "type error: immediate integer expected" );
73  ASSERT( invert || imm2int( c ) != 0,
74  "math error: divide by zero" );
75 
76  long intC = imm2int( c );
77 
79  mpz_t n, d;
80  if ( invert ) {
81  mpz_init_set_si( n, intC );
82  mpz_init_set( d, thempi );
83  } else {
84  mpz_init_set( n, thempi );
85  mpz_init_set_si( d, intC );
86  }
87  if ( deleteObject() ) delete this;
89  return result->normalize_myself();
90  }
91 
92  if ( invert ) {
93  int mpiSign = mpz_sgn( thempi );
94  if ( deleteObject() ) delete this;
95  if ( intC >= 0 )
96  return int2imm( 0 );
97  else
98  return int2imm( -mpiSign );
99  } else if ( getRefCount() > 1 ) {
100  decRefCount();
101  mpz_t mpiResult;
102  mpz_init( mpiResult );
103  if ( intC > 0 )
104  mpz_fdiv_q_ui( mpiResult, thempi, intC );
105  else {
106  mpz_fdiv_q_ui( mpiResult, thempi, -intC );
107  mpz_neg( mpiResult, mpiResult );
108  }
109  return normalizeMPI( mpiResult );
110  } else {
111  if ( intC > 0 )
112  mpz_fdiv_q_ui( thempi, thempi, intC );
113  else {
114  mpz_fdiv_q_ui( thempi, thempi, -intC );
115  mpz_neg( thempi, thempi );
116  }
117  return normalizeMyself();
118  }
119 }
120 
121 /**
122  * @sa CanonicalForm::div(), InternalInteger::divcoeff()
123 **/
124 InternalCF *
126 {
127  ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
128  "type error: InternalInteger expected" );
129 
130  if ( c == this ) {
131  if ( deleteObject() ) delete this;
132  return int2imm( 1 );
133  }
134 
135  if ( getRefCount() > 1 ) {
136  deleteObject();
137  mpz_t mpiResult;
138  mpz_init( mpiResult );
139  mpz_divexact( mpiResult, thempi, MPI( c ) );
140  return normalizeMPI( mpiResult );
141  } else {
142  mpz_divexact( thempi, thempi, MPI( c ) );
143  return normalizeMyself();
144  }
145 }
146 
147 /**
148  * @sa CanonicalForm::div(), InternalInteger::divsame()
149 **/
150 InternalCF *
152 {
153  ASSERT( ::is_imm( c ) == INTMARK,
154  "type error: immediate integer expected" );
155  ASSERT( invert || imm2int( c ) != 0,
156  "math error: divide by zero" );
157  ASSERT( ! invert || imm2int( c ) == 0,
158  "math error: c does not divide CO" );
159 
160  if ( invert ) {
161  if ( deleteObject() ) delete this;
162  // this may happen iff `c' == 0
163  return int2imm( 0 );
164  } else if ( getRefCount() > 1 ) {
165  deleteObject();
166  mpz_t mpiC;
167  mpz_t mpiResult;
168  mpz_init_set_si( mpiC, imm2int( c ) );
169  mpz_init( mpiResult );
170  mpz_divexact( mpiResult, thempi, mpiC );
171  mpz_clear( mpiC );
172  return normalizeMPI( mpiResult );
173  } else {
174  mpz_t mpiC;
175  mpz_init_set_si( mpiC, imm2int( c ) );
176  mpz_divexact( thempi, thempi, mpiC );
177  mpz_clear( mpiC );
178  return normalizeMyself();
179  }
180 }
181 
182 /**
183  * @sa CanonicalForm::operator %(), InternalInteger::modulocoeff()
184 **/
185 InternalCF *
187 {
188  ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
189  "type error: InternalInteger expected" );
190 
191  if ( (c == this) || cf_glob_switches.isOn( SW_RATIONAL ) ) {
192  if ( deleteObject() ) delete this;
193  return int2imm( 0 );
194  }
195 
196  if ( getRefCount() > 1 ) {
197  decRefCount();
198  mpz_t mpiResult;
199  mpz_init( mpiResult );
200  mpz_mod( mpiResult, thempi, MPI( c ) );
201  return uiNormalizeMPI( mpiResult );
202  } else {
203  mpz_mod( thempi, thempi, MPI( c ) );
204  return uiNormalizeMyself();
205  }
206 }
207 
208 /**
209  * @sa CanonicalForm::operator %(), InternalInteger::modulosame()
210 **/
211 InternalCF *
213 {
214  ASSERT( ::is_imm( c ) == INTMARK,
215  "type error: immediate integer expected" );
216  ASSERT( invert || imm2int( c ) != 0,
217  "math error: divide by zero" );
218 
219  if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
220  if ( deleteObject() ) delete this;
221  return int2imm( 0 );
222  }
223 
224  long intC = imm2int( c );
225 
226  if ( invert ) {
227  if ( intC >= 0 ) {
228  if ( deleteObject() ) delete this;
229  return c;
230  } else {
231  // no checks for refCount == 1 are done. It is not worth ...
232  mpz_t mpiResult;
233  mpz_init_set( mpiResult, thempi );
234  mpz_abs( mpiResult, mpiResult );
235  mpz_sub_ui( mpiResult, mpiResult, -intC );
236  if ( deleteObject() ) delete this;
237  return uiNormalizeMPI( mpiResult );
238  }
239  } else {
240  mpz_t dummy;
241  mpz_init( dummy );
242  InternalCF * result = int2imm( mpz_mod_ui( dummy, thempi, tabs( intC ) ) );
243  mpz_clear( dummy );
244  if ( deleteObject() ) delete this;
245  return result;
246  }
247 }
248 
249 /**
250  * @sa see CanonicalForm::mod(), InternalInteger::modcoeff()
251 **/
252 InternalCF *
254 {
255  return modulosame( c );
256 }
257 
258 /**
259  * @sa see CanonicalForm::mod(), InternalInteger::modsame()
260 **/
261 InternalCF *
263 {
264  return modulocoeff( c, invert );
265 }
266 
267 /**
268  * @sa CanonicalForm::divrem(), InternalInteger::divremcoeff()
269 **/
270 void
272 {
273  ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
274  "type error: InternalInteger expected" );
275 
276  if ( c == this ) {
277  quot = int2imm( 1 );
278  rem = int2imm( 0 );
279  return;
280  }
281 
282  if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
283  mpz_t n, d;
284  mpz_init_set( n, thempi );
285  mpz_init_set( d, MPI( c ) );
286  InternalRational * result = new InternalRational( n, d );
287  quot = result->normalize_myself();
288  rem = int2imm( 0 );
289  return;
290  }
291 
292  mpz_t q;
293  mpz_t r;
294  mpz_init( q ); mpz_init( r );
295  if ( mpz_sgn( MPI( c ) ) > 0 )
296  mpz_fdiv_qr( q, r, thempi, MPI( c ) );
297  else
298  mpz_cdiv_qr( q, r, thempi, MPI( c ) );
299 
300  quot = normalizeMPI( q );
301  rem = uiNormalizeMPI( r );
302 }
303 
304 /**
305  * @sa CanonicalForm::divrem(), InternalInteger::divremsame()
306 **/
307 void
309 {
310  ASSERT( ::is_imm( c ) == INTMARK,
311  "type error: immediate integer expected" );
312  ASSERT( invert || imm2int( c ) != 0,
313  "math error: divide by zero" );
314 
315  long intC = imm2int( c );
316 
317  if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
318  mpz_t n, d;
319  if ( invert ) {
320  mpz_init_set_si( n, intC );
321  mpz_init_set( d, thempi );
322  } else {
323  mpz_init_set( n, thempi );
324  mpz_init_set_si( d, intC );
325  }
326  InternalRational * result = new InternalRational( n, d );
327  quot = result->normalize_myself();
328  rem = int2imm( 0 );
329  return;
330  }
331 
332  if ( invert ) {
333  if ( intC >= 0 ) {
334  rem = c;
335  quot = int2imm( 0 );
336  } else {
337  mpz_t mpiResult;
338  mpz_init_set( mpiResult, thempi );
339  mpz_abs( mpiResult, mpiResult );
340  mpz_sub_ui( mpiResult, mpiResult, -intC );
341  rem = uiNormalizeMPI( mpiResult );
342  quot = int2imm( -mpz_sgn( thempi ) );
343  }
344  } else {
345  mpz_t q;
346  mpz_t dummy;
347  mpz_init( q ); mpz_init( dummy );
348  if ( intC > 0 ) {
349  rem = int2imm( mpz_fdiv_qr_ui( q, dummy, thempi, intC ) );
350  quot = normalizeMPI( q );
351  } else {
352  rem = int2imm( mpz_fdiv_qr_ui( q, dummy, thempi, -intC ) );
353  mpz_neg( q, q );
354  quot = normalizeMPI( q );
355  }
356  mpz_clear( dummy );
357  }
358 }
359 
360 /**
361  * @sa CanonicalForm::divremt(), InternalInteger::divremcoefft()
362 **/
363 bool
365 {
366  divremsame( c, quot, rem );
367  return true;
368 }
369 
370 /**
371  * @sa CanonicalForm::divremt(), InternalInteger::divremsamet()
372 **/
373 bool
375 {
376  divremcoeff( c, quot, rem, invert );
377  return true;
378 }
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
InternalCF::invert
virtual InternalCF * invert()
Definition: int_cf.cc:172
InternalInteger::is_imm
bool is_imm() const
Definition: int_int.cc:41
canonicalform.h
InternalInteger::modulocoeff
InternalCF * modulocoeff(InternalCF *, bool)
Definition: int_intdiv.cc:212
result
return result
Definition: facAbsBiFact.cc:76
InternalInteger::modsame
InternalCF * modsame(InternalCF *)
Definition: int_intdiv.cc:253
cf_gmp.h
InternalInteger::normalizeMPI
static InternalCF * normalizeMPI(mpz_ptr)
normalizeMPI(), uiNormalizeMPI() - normalize a mpi.
Definition: int_int.h:196
InternalInteger::dividesame
InternalCF * dividesame(InternalCF *)
Definition: int_intdiv.cc:28
InternalInteger::thempi
mpz_t thempi
Definition: int_int.h:43
int_int.h
InternalInteger::normalizeMyself
InternalCF * normalizeMyself()
normalizeMyself(), uiNormalizeMyself() - normalize CO.
Definition: int_int.h:152
InternalCF
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
ftmpl_functions.h
InternalInteger::InternalRational
friend class InternalRational
Definition: int_int.h:134
InternalCF::levelcoeff
virtual int levelcoeff() const
Definition: int_cf.h:68
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
INTMARK
const long INTMARK
Definition: imm.h:37
int2imm
static InternalCF * int2imm(long i)
Definition: imm.h:75
InternalInteger::uiNormalizeMyself
InternalCF * uiNormalizeMyself()
‘uiNormalizeMyself()’ is the same as ‘normalizeMyself()’ except that CO is expected to be non-negativ...
Definition: int_int.h:174
int_cf.h
gmpext.h
InternalInteger::dividecoeff
InternalCF * dividecoeff(InternalCF *, bool)
Definition: int_intdiv.cc:69
tabs
int tabs
Definition: checklibs.c:11
imm.h
InternalInteger::uiNormalizeMPI
static InternalCF * uiNormalizeMPI(mpz_ptr)
‘uiNormalizeMPI()’ is the same as ‘normalizeMPI()’ except that ‘aMpi’ is expected to be non-begative.
Definition: int_int.h:213
InternalInteger::divremsame
void divremsame(InternalCF *, InternalCF *&, InternalCF *&)
Definition: int_intdiv.cc:271
InternalRational
factory's class for rationals
Definition: int_rat.h:39
InternalCF::deleteObject
int deleteObject()
Definition: int_cf.h:61
InternalCF::decRefCount
int decRefCount()
Definition: int_cf.h:53
InternalInteger::modcoeff
InternalCF * modcoeff(InternalCF *, bool)
Definition: int_intdiv.cc:262
InternalInteger::MPI
static mpz_ptr MPI(const InternalCF *const c)
MPI() - return underlying mpz_t of ‘c’.
Definition: int_int.h:232
InternalInteger::divremcoefft
bool divremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition: int_intdiv.cc:374
imm2int
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
InternalInteger::divremcoeff
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition: int_intdiv.cc:308
cf_glob_switches
CFSwitches cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.cc:41
InternalInteger::divcoeff
InternalCF * divcoeff(InternalCF *, bool)
Definition: int_intdiv.cc:151
InternalInteger::divsame
InternalCF * divsame(InternalCF *)
Definition: int_intdiv.cc:125
int_rat.h
InternalInteger::divremsamet
bool divremsamet(InternalCF *, InternalCF *&, InternalCF *&)
Definition: int_intdiv.cc:364
IntegerDomain
#define IntegerDomain
Definition: cf_defs.h:25
InternalInteger::modulosame
InternalCF * modulosame(InternalCF *)
Definition: int_intdiv.cc:186
rem
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572
InternalCF::getRefCount
int getRefCount()
Definition: int_cf.h:51
CFSwitches::isOn
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55