My Project
imm.h
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file imm.h
5  *
6  * operations on immediates, that is elements of F_p, GF, Z, Q
7  * that fit into intrinsic int, long
8 **/
9 
10 #ifndef INCL_IMM_H
11 #define INCL_IMM_H
12 
13 #include <stdint.h>
14 
15 // #include "config.h"
16 
17 #ifndef NOSTREAMIO
18 #ifdef HAVE_IOSTREAM
19 #include <iostream>
20 #define OSTREAM std::ostream
21 #elif defined(HAVE_IOSTREAM_H)
22 #include <iostream.h>
23 #define OSTREAM ostream
24 #endif
25 #endif /* NOSTREAMIO */
26 
27 #include "cf_assert.h"
28 
29 #include "cf_defs.h"
30 #include "cf_globals.h"
31 #include "ffops.h"
32 #include "gfops.h"
33 #include "cf_factory.h"
34 #include "canonicalform.h"
35 #include "int_cf.h"
36 
37 const long INTMARK = 1;
38 const long FFMARK = 2;
39 const long GFMARK = 3;
40 
41 /* define type of your compilers 64 bit integer type */
42 #ifndef FACTORY_INT64
43 #if SIZEOF_LONG == 8
44 #define FACTORY_INT64 long int
45 #else
46 #define FACTORY_INT64 long long int
47 #endif
48 #endif
49 
50 #if SIZEOF_LONG == 4
51 const long MINIMMEDIATE = -268435454; // -2^28+2
52 const long MAXIMMEDIATE = 268435454; // 2^28-2
53 #else
54 const long MINIMMEDIATE = -(1L<<60)+2L; // -2^60+2
55 const long MAXIMMEDIATE = (1L<<60)-2L; // 2^60-2
56 #endif
57 
58 #if defined(WINNT) && ! defined(__GNUC__)
59 const FACTORY_INT64 MINIMMEDIATELL = -268435454i64;
60 const FACTORY_INT64 MAXIMMEDIATELL = 268435454i64;
61 #else
62 const FACTORY_INT64 MINIMMEDIATELL = -268435454LL;
63 const FACTORY_INT64 MAXIMMEDIATELL = 268435454LL;
64 #endif
65 
66 //{{{ conversion functions
67 //#ifdef HAS_ARITHMETIC_SHIFT
68 #if 1
69 
70 static inline long imm2int ( const InternalCF * const imm )
71 {
72  return ((intptr_t)imm) >> 2;
73 }
74 
75 static inline InternalCF * int2imm ( long i )
76 {
77  return (InternalCF*)((i << 2) | INTMARK );
78 }
79 
80 #else
81 
82 static inline long imm2int ( const InternalCF * const imm )
83 {
84  // this could be better done by masking the sign bit
85  if ( ((long)(intptr_t)imm)) < 0 )
86  return -((-(long)(intptr_t)imm) >> 2);
87  else
88  return (long)(intptr_t)imm >> 2;
89 }
90 
91 static inline InternalCF * int2imm ( long i )
92 {
93  if ( i < 0 )
94  return (InternalCF*)(-(((-i) << 2) | INTMARK));
95  else
96  return (InternalCF*)((i << 2) | INTMARK );
97 }
98 
99 #endif
100 
101 inline InternalCF * int2imm_p ( long i )
102 {
103  return (InternalCF*)((i << 2) | FFMARK );
104 }
105 
106 inline InternalCF * int2imm_gf ( long i )
107 {
108  return (InternalCF*)((i << 2) | GFMARK );
109 }
110 //}}}
111 
112 // predicates
113 #if 0
114 inline int is_imm ( const InternalCF * const ptr )
115 {
116  // returns 0 if ptr is not immediate
117  return ( (intptr_t)ptr & 3 );
118 }
119 #endif
120 
121 //{{{ inline int imm_isone, imm_isone_p, imm_isone_gf ( const InternalCF * const ptr )
122 // docu: see CanonicalForm::isOne()
123 inline int
124 imm_isone ( const InternalCF * const ptr )
125 {
126  return imm2int( ptr ) == 1;
127 }
128 
129 inline int
130 imm_isone_p ( const InternalCF * const ptr )
131 {
132  return imm2int( ptr ) == 1;
133 }
134 
135 inline int
136 imm_isone_gf ( const InternalCF * const ptr )
137 {
138  return gf_isone( imm2int( ptr ) );
139 }
140 //}}}
141 
142 //{{{ inline int imm_iszero, imm_iszero_p, imm_iszero_gf ( const InternalCF * const ptr )
143 // docu: see CanonicalForm::isZero()
144 inline int
145 imm_iszero ( const InternalCF * const ptr )
146 {
147  return imm2int( ptr ) == 0;
148 }
149 
150 inline int
151 imm_iszero_p ( const InternalCF * const ptr )
152 {
153  return imm2int( ptr ) == 0;
154 }
155 
156 inline int
157 imm_iszero_gf ( const InternalCF * const ptr )
158 {
159  return gf_iszero( imm2int( ptr ) );
160 }
161 //}}}
162 
163 //{{{ conversion functions
164 inline long imm_intval ( const InternalCF* const op )
165 {
166  if ( is_imm( op ) == FFMARK )
167  {
169  return ff_symmetric( imm2int( op ) );
170  else
171  return imm2int( op );
172  }
173  else if ( is_imm( op ) == GFMARK )
174  {
175  ASSERT( gf_isff( imm2int( op ) ), "invalid conversion" );
177  return ff_symmetric( gf_gf2ff( imm2int( op ) ) );
178  else
179  return gf_gf2ff( imm2int( op ) );
180  }
181  /*else*/
182  return imm2int( op );
183 }
184 //}}}
185 
186 /**
187  *
188  * imm_sign() - return sign of immediate object.
189  *
190  * If CO is an immediate integer, the sign is defined as usual.
191  * If CO is an element of FF(p) and SW_SYMMETRIC_FF is on the
192  * sign of CO is the sign of the symmetric representation of CO.
193  * If CO is in GF(q) or in FF(p) and SW_SYMMETRIC_FF is off, the
194  * sign of CO is zero iff CO is zero, otherwise the sign is one.
195  *
196  * @sa CanonicalForm::sign(), gf_sign()
197  *
198 **/
199 inline int
200 imm_sign ( const InternalCF * const op )
201 {
202  if ( is_imm( op ) == FFMARK )
203  if ( imm2int( op ) == 0 )
204  return 0;
205  else if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
206  if ( ff_symmetric( imm2int( op ) ) > 0 )
207  return 1;
208  else
209  return -1;
210  else
211  return 1;
212  else if ( is_imm( op ) == GFMARK )
213  return gf_sign( imm2int( op ) );
214  else if ( imm2int( op ) == 0 )
215  return 0;
216  else if ( imm2int( op ) > 0 )
217  return 1;
218  else
219  return -1;
220 }
221 
222 /**
223  *
224  * imm_cmp(), imm_cmp_p(), imm_cmp_gf() - compare immediate objects.
225  *
226  * For immediate integers, it is clear how this should be done.
227  * For objects from finite fields, it is not clear since they
228  * are not ordered fields. However, since we want to have a
229  * total well order on polynomials we have to define a total well
230  * order on all coefficients, too. We decided to use simply the
231  * order on the representation as `int's of such objects.
232  *
233  * @sa CanonicalForm::operator <(), CanonicalForm::operator ==()
234  *
235 **/
236 inline int
237 imm_cmp ( const InternalCF * const lhs, const InternalCF * const rhs )
238 {
239  if ( imm2int( lhs ) == imm2int( rhs ) )
240  return 0;
241  else if ( imm2int( lhs ) > imm2int( rhs ) )
242  return 1;
243  else
244  return -1;
245 }
246 
247 inline int
248 imm_cmp_p ( const InternalCF * const lhs, const InternalCF * const rhs )
249 {
250  if ( imm2int( lhs ) == imm2int( rhs ) )
251  return 0;
252  else if ( imm2int( lhs ) > imm2int( rhs ) )
253  return 1;
254  else
255  return -1;
256 }
257 
258 inline int
259 imm_cmp_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
260 {
261  if ( imm2int( lhs ) == imm2int( rhs ) )
262  return 0;
263  // check is done in this way because zero should be minimal
264  else if ( imm2int( lhs ) > imm2int( rhs ) )
265  return -1;
266  else
267  return 1;
268 }
269 //}}}
270 
271 //{{{ arithmetic operators
272 inline InternalCF * imm_add ( const InternalCF * const lhs, const InternalCF * const rhs )
273 {
274  long result = imm2int( lhs ) + imm2int( rhs );
275  if ( ( result > MAXIMMEDIATE ) || ( result < MINIMMEDIATE ) )
276  return CFFactory::basic( result );
277  else
278  return int2imm( result );
279 }
280 
281 inline InternalCF * imm_add_p ( const InternalCF * const lhs, const InternalCF * const rhs )
282 {
283  return int2imm_p( ff_add( imm2int( lhs ), imm2int( rhs ) ) );
284 }
285 
286 inline InternalCF * imm_add_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
287 {
288  return int2imm_gf( gf_add( imm2int( lhs ), imm2int( rhs ) ) );
289 }
290 
291 inline InternalCF * imm_sub ( const InternalCF * const lhs, const InternalCF * const rhs )
292 {
293  long result = imm2int( lhs ) - imm2int( rhs );
294  if ( ( result > MAXIMMEDIATE ) || ( result < MINIMMEDIATE ) )
295  return CFFactory::basic( result );
296  else
297  return int2imm( result );
298 }
299 
300 inline InternalCF * imm_sub_p ( const InternalCF * const lhs, const InternalCF * const rhs )
301 {
302  return int2imm_p( ff_sub( imm2int( lhs ), imm2int( rhs ) ) );
303 }
304 
305 inline InternalCF * imm_sub_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
306 {
307  return int2imm_gf( gf_sub( imm2int( lhs ), imm2int( rhs ) ) );
308 }
309 
310 inline InternalCF *
311 imm_mul ( InternalCF * lhs, InternalCF * rhs )
312 {
313  long a = imm2int( lhs );
314  if (a == 0L)
315  return int2imm(0);
316  long b = imm2int( rhs );
317  int sa= 1;
318  unsigned FACTORY_INT64 aa, bb;
319  if (a < 0)
320  {
321  sa= -1;
322  aa= (unsigned FACTORY_INT64) (-a);
323  }
324  else
325  aa= (unsigned FACTORY_INT64) a;
326  if (b < 0)
327  {
328  sa= -sa;
329  bb= (unsigned FACTORY_INT64) (-b);
330  }
331  else
332  bb= (unsigned FACTORY_INT64) b;
333  unsigned FACTORY_INT64 result = aa*bb;
334  #if SIZEOF_LONG == 4
335  if (result>(unsigned FACTORY_INT64)MAXIMMEDIATE)
336  {
338  return res->mulcoeff( rhs );
339  }
340  #else
341  if ( ((result/aa!=bb) || (result>(unsigned FACTORY_INT64) MAXIMMEDIATE) ))
342  {
344  return res->mulcoeff( rhs );
345  }
346  #endif
347  else
348  return int2imm( sa*result );
349 }
350 
351 inline InternalCF * imm_mul_p ( const InternalCF * const lhs, const InternalCF * const rhs )
352 {
353  return int2imm_p( ff_mul( imm2int( lhs ), imm2int( rhs ) ) );
354 }
355 
356 inline InternalCF * imm_mul_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
357 {
358  return int2imm_gf( gf_mul( imm2int( lhs ), imm2int( rhs ) ) );
359 }
360 
361 inline InternalCF * imm_div ( const InternalCF * const lhs, const InternalCF * const rhs )
362 {
363  long a = imm2int( lhs );
364  long b = imm2int( rhs );
365  if ( a > 0 )
366  return int2imm( a / b );
367  else if ( b > 0 )
368  return int2imm( -((b-a-1)/b) );
369  else
370  return int2imm( (-a-b-1)/(-b) );
371 }
372 
373 inline InternalCF * imm_divrat ( const InternalCF * const lhs, const InternalCF * const rhs )
374 {
376  return CFFactory::rational( imm2int( lhs ), imm2int( rhs ) );
377  else {
378  long a = imm2int( lhs );
379  long b = imm2int( rhs );
380  if ( a > 0 )
381  return int2imm( a / b );
382  else if ( b > 0 )
383  return int2imm( -((b-a-1)/b) );
384  else
385  return int2imm( (-a-b-1)/(-b) );
386  }
387 }
388 
389 inline InternalCF * imm_div_p ( const InternalCF * const lhs, const InternalCF * const rhs )
390 {
391  return int2imm_p( ff_div( imm2int( lhs ), imm2int( rhs ) ) );
392 }
393 
394 inline InternalCF * imm_div_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
395 {
396  return int2imm_gf( gf_div( imm2int( lhs ), imm2int( rhs ) ) );
397 }
398 
399 inline InternalCF * imm_mod ( const InternalCF * const lhs, const InternalCF * const rhs )
400 {
402  return int2imm( 0 );
403  else {
404  long a = imm2int( lhs );
405  long b = imm2int( rhs );
406  if ( a > 0 )
407  if ( b > 0 )
408  return int2imm( a % b );
409  else
410  return int2imm( a % (-b) );
411  else
412  if ( b > 0 ) {
413  long r = (-a) % b;
414  return int2imm( (r==0) ? r : b-r );
415  }
416  else {
417  long r = (-a) % (-b);
418  return int2imm( (r==0) ? r : -b-r );
419  }
420  }
421 }
422 
423 inline InternalCF * imm_mod_p ( const InternalCF * const, const InternalCF * const )
424 {
425  return int2imm_p( 0 );
426 }
427 
428 inline InternalCF * imm_mod_gf ( const InternalCF * const, const InternalCF * const )
429 {
430  return int2imm_gf( gf_q );
431 }
432 
433 inline void imm_divrem ( const InternalCF * const lhs, const InternalCF * const rhs, InternalCF * & q, InternalCF * & r )
434 {
435  if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
436  q = imm_divrat( lhs, rhs );
437  r = CFFactory::basic( 0L );
438  }
439  else {
440  q = imm_div( lhs, rhs );
441  r = imm_mod( lhs, rhs );
442  }
443 }
444 
445 inline void imm_divrem_p ( const InternalCF * const lhs, const InternalCF * const rhs, InternalCF * & q, InternalCF * & r )
446 {
447  q = int2imm_p( ff_div( imm2int( lhs ), imm2int( rhs ) ) );
448  r = int2imm_p( 0 );
449 }
450 
451 inline void imm_divrem_gf ( const InternalCF * const lhs, const InternalCF * const rhs, InternalCF * & q, InternalCF * & r )
452 {
453  q = int2imm_gf( gf_div( imm2int( lhs ), imm2int( rhs ) ) );
454  r = int2imm_gf( gf_q );
455 }
456 
457 //{{{ inline InternalCF * imm_neg, imm_neg_p, imm_neg_gf ( const InternalCF * const op )
458 // docu: see CanonicalForm::operator -()
459 inline InternalCF *
460 imm_neg ( const InternalCF * const op )
461 {
462  return int2imm( -imm2int( op ) );
463 }
464 
465 inline InternalCF *
466 imm_neg_p ( const InternalCF * const op )
467 {
468  return int2imm_p( ff_neg( imm2int( op ) ) );
469 }
470 
471 inline InternalCF *
472 imm_neg_gf ( const InternalCF * const op )
473 {
474  return int2imm_gf( gf_neg( imm2int( op ) ) );
475 }
476 //}}}
477 //}}}
478 
479 //{{{ input/output
480 #ifndef NOSTREAMIO
481 inline void imm_print ( OSTREAM & os, const InternalCF * const op, const char * const str )
482 {
483  if ( is_imm( op ) == FFMARK )
485  os << ff_symmetric( imm2int( op ) ) << str;
486  else
487  os << imm2int( op ) << str;
488  else if ( is_imm( op ) == GFMARK ) {
489  gf_print( os, imm2int( op ) );
490  os << str;
491  }
492  else
493  os << imm2int( op ) << str;
494 }
495 #endif /* NOSTREAMIO */
496 //}}}
497 
498 #endif /* ! INCL_IMM_H */
Header for factory's main class CanonicalForm.
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:65
int i
Definition: cfEzgcd.cc:132
CanonicalForm b
Definition: cfModGcd.cc:4105
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
factory switches.
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:32
#define IntegerDomain
Definition: cf_defs.h:27
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
INST_VAR CFSwitches cf_glob_switches
Definition: cf_switches.cc:47
static InternalCF * basic(int value)
Definition: cf_factory.cc:61
static InternalCF * rational(long num, long den)
Definition: cf_factory.cc:268
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
return result
Definition: facAbsBiFact.cc:75
CanonicalForm res
Definition: facAbsFact.cc:60
long gf_gf2ff(long a)
Definition: gfops.cc:209
bool gf_isff(long a)
Definition: gfops.cc:253
operations in a finite prime field F_p.
#define FACTORY_INT64
Definition: ffops.h:24
int ff_symmetric(const int a)
Definition: ffops.h:67
int ff_add(const int a, const int b)
Definition: ffops.h:97
int ff_div(const int a, const int b)
Definition: ffops.h:163
int ff_mul(const int a, const int b)
Definition: ffops.h:139
int ff_neg(const int a)
Definition: ffops.h:126
int ff_sub(const int a, const int b)
Definition: ffops.h:112
VAR int gf_q
Definition: gfops.cc:47
Operations in GF, where GF is a finite field of size less than 2^16 represented by a root of Conway p...
int gf_sub(int a, int b)
Definition: gfops.h:158
void gf_print(OSTREAM &os, int a)
Definition: gfops.h:207
int gf_neg(int a)
Definition: gfops.h:123
bool gf_isone(int a)
Definition: gfops.h:53
bool gf_iszero(int a)
Definition: gfops.h:43
int gf_mul(int a, int b)
Definition: gfops.h:163
int gf_div(int a, int b)
Definition: gfops.h:185
int gf_sign(int a)
Definition: gfops.h:113
int gf_add(int a, int b)
Definition: gfops.h:133
InternalCF * int2imm_p(long i)
Definition: imm.h:101
int imm_isone_p(const InternalCF *const ptr)
Definition: imm.h:130
void imm_divrem_gf(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:451
InternalCF * imm_sub_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:300
InternalCF * imm_mul_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:351
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
InternalCF * imm_add(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:272
InternalCF * imm_mod_p(const InternalCF *const, const InternalCF *const)
Definition: imm.h:423
const long MAXIMMEDIATE
Definition: imm.h:55
int imm_isone(const InternalCF *const ptr)
Definition: imm.h:124
const FACTORY_INT64 MAXIMMEDIATELL
Definition: imm.h:63
InternalCF * imm_div(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:361
InternalCF * imm_sub(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:291
#define OSTREAM
Definition: imm.h:20
int imm_sign(const InternalCF *const op)
imm_sign() - return sign of immediate object.
Definition: imm.h:200
InternalCF * imm_add_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:286
int imm_cmp_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:248
InternalCF * imm_divrat(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:373
InternalCF * imm_neg_p(const InternalCF *const op)
Definition: imm.h:466
InternalCF * imm_div_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:389
int imm_cmp_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:259
InternalCF * imm_div_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:394
int imm_iszero(const InternalCF *const ptr)
Definition: imm.h:145
int imm_iszero_gf(const InternalCF *const ptr)
Definition: imm.h:157
void imm_print(OSTREAM &os, const InternalCF *const op, const char *const str)
Definition: imm.h:481
long imm_intval(const InternalCF *const op)
Definition: imm.h:164
InternalCF * imm_neg(const InternalCF *const op)
Definition: imm.h:460
static InternalCF * int2imm(long i)
Definition: imm.h:75
const FACTORY_INT64 MINIMMEDIATELL
Definition: imm.h:62
const long FFMARK
Definition: imm.h:38
const long MINIMMEDIATE
Definition: imm.h:54
int imm_iszero_p(const InternalCF *const ptr)
Definition: imm.h:151
const long INTMARK
Definition: imm.h:37
InternalCF * imm_mul_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:356
int imm_isone_gf(const InternalCF *const ptr)
Definition: imm.h:136
InternalCF * imm_mod_gf(const InternalCF *const, const InternalCF *const)
Definition: imm.h:428
InternalCF * imm_mod(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:399
int imm_cmp(const InternalCF *const lhs, const InternalCF *const rhs)
imm_cmp(), imm_cmp_p(), imm_cmp_gf() - compare immediate objects.
Definition: imm.h:237
InternalCF * imm_neg_gf(const InternalCF *const op)
Definition: imm.h:472
InternalCF * int2imm_gf(long i)
Definition: imm.h:106
void imm_divrem_p(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:445
const long GFMARK
Definition: imm.h:39
InternalCF * imm_add_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:281
InternalCF * imm_mul(InternalCF *lhs, InternalCF *rhs)
Definition: imm.h:311
void imm_divrem(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:433
InternalCF * imm_sub_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:305
Factory's internal CanonicalForm's.
char * str(leftv arg)
Definition: shared.cc:704