My Project
Loading...
Searching...
No Matches
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**/
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 ) {
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**/
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**/
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**/
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**/
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**/
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
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**/
254{
255 return modulosame( c );
256}
257
258/**
259 * @sa see CanonicalForm::mod(), InternalInteger::modsame()
260**/
263{
264 return modulocoeff( c, invert );
265}
266
267/**
268 * @sa CanonicalForm::divrem(), InternalInteger::divremcoeff()
269**/
270void
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
283 mpz_t n, d;
284 mpz_init_set( n, thempi );
285 mpz_init_set( d, MPI( c ) );
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**/
307void
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
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 }
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**/
363bool
365{
366 divremsame( c, quot, rem );
367 return true;
368}
369
370/**
371 * @sa CanonicalForm::divremt(), InternalInteger::divremsamet()
372**/
373bool
375{
376 divremcoeff( c, quot, rem, invert );
377 return true;
378}
Header for factory's main class CanonicalForm.
#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:31
#define IntegerDomain
Definition: cf_defs.h:21
INST_VAR CFSwitches cf_glob_switches
Definition: cf_switches.cc:54
int tabs
Definition: checklibs.c:11
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
int getRefCount()
Definition: int_cf.h:51
virtual int levelcoeff() const
Definition: int_cf.h:68
int decRefCount()
Definition: int_cf.h:53
virtual InternalCF * invert()
Definition: int_cf.cc:172
int deleteObject()
Definition: int_cf.h:61
InternalCF * dividecoeff(InternalCF *, bool)
Definition: int_intdiv.cc:69
InternalCF * normalizeMyself()
normalizeMyself(), uiNormalizeMyself() - normalize CO.
Definition: int_int.h:152
InternalCF * modsame(InternalCF *)
Definition: int_intdiv.cc:253
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
mpz_t thempi
Definition: int_int.h:43
void divremcoeff(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition: int_intdiv.cc:308
friend class InternalRational
Definition: int_int.h:134
InternalCF * modcoeff(InternalCF *, bool)
Definition: int_intdiv.cc:262
InternalCF * modulocoeff(InternalCF *, bool)
Definition: int_intdiv.cc:212
InternalCF * modulosame(InternalCF *)
Definition: int_intdiv.cc:186
InternalCF * divcoeff(InternalCF *, bool)
Definition: int_intdiv.cc:151
void divremsame(InternalCF *, InternalCF *&, InternalCF *&)
Definition: int_intdiv.cc:271
static InternalCF * normalizeMPI(mpz_ptr)
normalizeMPI(), uiNormalizeMPI() - normalize a mpi.
Definition: int_int.h:196
bool divremsamet(InternalCF *, InternalCF *&, InternalCF *&)
Definition: int_intdiv.cc:364
bool is_imm() const
Definition: int_int.cc:41
InternalCF * dividesame(InternalCF *)
Definition: int_intdiv.cc:28
InternalCF * divsame(InternalCF *)
Definition: int_intdiv.cc:125
static mpz_ptr MPI(const InternalCF *const c)
MPI() - return underlying mpz_t of ‘c’.
Definition: int_int.h:232
InternalCF * uiNormalizeMyself()
‘uiNormalizeMyself()’ is the same as ‘normalizeMyself()’ except that CO is expected to be non-negativ...
Definition: int_int.h:174
bool divremcoefft(InternalCF *, InternalCF *&, InternalCF *&, bool)
Definition: int_intdiv.cc:374
factory's class for rationals
Definition: int_rat.h:39
return result
Definition: facAbsBiFact.cc:75
some useful template functions.
utility functions for gmp
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
const long INTMARK
Definition: imm.h:37
static InternalCF * int2imm(long i)
Definition: imm.h:75
Factory's internal CanonicalForm's.
Factory's internal integers.
Factory's internal rationals.
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572