My Project  debian-1:4.1.1-p2+ds-4
gfops.h
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file gfops.h
5  *
6  * Operations in GF, where GF is a finite field of size less than 2^16
7  * represented by a root of Conway polynomial. Uses look up tables for addition.
8  *
9  * @sa gf_tabutil.h
10 **/
11 #ifndef INCL_GFOPS_H
12 #define INCL_GFOPS_H
13 
14 // #include "config.h"
15 
16 #ifndef NOSTREAMIO
17 #ifdef HAVE_IOSTREAM
18 #include <iostream>
19 #define OSTREAM std::ostream
20 #elif defined(HAVE_IOSTREAM_H)
21 #include <iostream.h>
22 #define OSTREAM ostream
23 #endif
24 #endif /* NOSTREAMIO */
25 
26 #include "cf_assert.h"
27 
28 #include "cf_defs.h"
29 #include "canonicalform.h"
30 
31 extern int gf_q;
32 extern int gf_p;
33 extern int gf_n;
34 extern int gf_q1;
35 extern int gf_m1;
36 extern char gf_name;
37 
38 extern unsigned short * gf_table;
39 
40 extern CanonicalForm gf_mipo;
41 
42 //{{{ predicates
43 inline bool gf_iszero ( int a )
44 {
45  return gf_q == a;
46 }
47 
48 inline bool gf_iszero ( long a )
49 {
50  return gf_q == a;
51 }
52 
53 inline bool gf_isone ( int a )
54 {
55  return 0 == a;
56 }
57 
58 inline bool gf_isone ( long a )
59 {
60  return 0 == a;
61 }
62 //}}}
63 
64 //{{{ conversion functions
65 inline int gf_int2gf ( int i )
66 {
67  while ( i < 0 )
68  i += gf_p;
69  while ( i >= gf_p )
70  i -= gf_p;
71  if ( i == 0 )
72  return gf_q;
73  int c = 0;
74  while ( i > 1 ) {
75  c = gf_table[c];
76  i--;
77  }
78  return c;
79 }
80 
81 inline long gf_int2gf ( long i )
82 {
83  while ( i < 0 )
84  i += gf_p;
85  while ( i >= gf_p )
86  i -= gf_p;
87  if ( i == 0 )
88  return gf_q;
89  long c = 0;
90  while ( i > 1 ) {
91  c = gf_table[c];
92  i--;
93  }
94  return c;
95 }
96 //}}}
97 
98 //{{{ zero and one
99 inline int gf_zero()
100 {
101  return gf_q;
102 }
103 
104 inline int gf_one()
105 {
106  return 0;
107 }
108 //}}}
109 
110 //{{{ inline int gf_sign ( int a )
111 // docu: see imm_sign()
112 inline
113 int gf_sign ( int a )
114 {
115  if ( gf_iszero( a ) )
116  return 0;
117  else
118  return 1;
119 }
120 //}}}
121 
122 //{{{ arithmetic operators
123 inline int gf_neg ( int a )
124 {
125  // -z^a=z^a*(-1)=z^a*gf_m1;
126  if ( a == gf_q ) return a;
127  int i = a + gf_m1;
128  if ( i >= gf_q1 )
129  i -= gf_q1;
130  return i;
131 }
132 
133 inline int gf_add ( int a, int b )
134 {
135  // z^a+z^b=z^b*(z^(a-b)+1), if a>=b;
136  // =z^a*(z^(b-a)+1), if a<b;
137  if ( a == gf_q ) return b;
138  if ( b == gf_q ) return a;
139  int zb, zab, r;
140  if ( a >= b ) {
141  zb = b;
142  zab = a - b;
143  }
144  else {
145  zb = a;
146  zab = b - a;
147  }
148  if ( gf_table[zab] == gf_q )
149  r = gf_q; /*if z^(a-b)+1 =0*/
150  else {
151  r= zb + gf_table[zab];
152  if ( r >= gf_q1 )
153  r -= gf_q1;
154  }
155  return r;
156 }
157 
158 inline int gf_sub ( int a, int b )
159 {
160  return gf_add( a, gf_neg( b ) );
161 }
162 
163 inline int gf_mul ( int a, int b )
164 {
165  if ( a == gf_q || b == gf_q )
166  return gf_q;
167  else {
168  int i = a + b;
169  if ( i >= gf_q1 ) i -= gf_q1;
170  return i;
171  }
172 }
173 
174 inline long gf_mul ( long a, int b )
175 {
176  if ( a == gf_q || b == gf_q )
177  return gf_q;
178  else {
179  long i = a + b;
180  if ( i >= gf_q1 ) i -= gf_q1;
181  return i;
182  }
183 }
184 
185 inline int gf_div ( int a, int b )
186 {
187  ASSERT( b != gf_q, "divide by zero" );
188  if ( a == gf_q )
189  return gf_q;
190  else {
191  int s = a - b;
192  if (s < 0)
193  s += gf_q1;
194  return s;
195  }
196 }
197 
198 inline int gf_inv ( int a )
199 {
200  ASSERT( a != gf_q, "divide by zero" );
201  return gf_q1 - a;
202 }
203 //}}}
204 
205 //{{{ input/output
206 #ifndef NOSTREAMIO
207 inline void gf_print ( OSTREAM & os, int a )
208 {
209  if ( a == gf_q )
210  os << "0";
211  else if ( a == 0 )
212  os << "1";
213  else if ( a == 1 )
214  os << gf_name;
215  else
216  os << gf_name << "^" << a;
217 }
218 #endif /* NOSTREAMIO */
219 //}}}
220 
221 //{{{ exponentation
222 inline int gf_power ( int a, int n )
223 {
224  if ( n == 0 )
225  return 0;
226  else if ( n == 1 )
227  return a;
228  else
229  return gf_mul( a, gf_power( a, n-1 ) );
230 }
231 
232 inline long gf_power ( long a, int n )
233 {
234  if ( n == 0 )
235  return 0;
236  else if ( n == 1 )
237  return a;
238  else
239  return gf_mul( a, gf_power( a, n-1 ) );
240 }
241 //}}}
242 
243 void gf_setcharacteristic ( int p, int n, char name );
244 
245 // Singular needs this
246 /*BEGINPUBLIC*/
247 
248 long gf_gf2ff ( long a );
249 int gf_gf2ff ( int a );
250 
251 bool gf_isff ( long a );
252 bool gf_isff ( int a );
253 
254 /*ENDPUBLIC*/
255 
256 #endif /* ! INCL_GFOPS_H */
gf_div
int gf_div(int a, int b)
Definition: gfops.h:185
gf_neg
int gf_neg(int a)
Definition: gfops.h:123
gf_isone
bool gf_isone(int a)
Definition: gfops.h:53
canonicalform.h
gf_power
int gf_power(int a, int n)
Definition: gfops.h:222
gf_one
int gf_one()
Definition: gfops.h:104
gf_zero
int gf_zero()
Definition: gfops.h:99
gf_inv
int gf_inv(int a)
Definition: gfops.h:198
b
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm
factory's main class
Definition: canonicalform.h:77
gf_sign
int gf_sign(int a)
Definition: gfops.h:113
gf_q1
int gf_q1
Definition: gfops.cc:50
gf_add
int gf_add(int a, int b)
Definition: gfops.h:133
i
int i
Definition: cfEzgcd.cc:125
OSTREAM
#define OSTREAM
Definition: gfops.h:19
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
gf_mipo
CanonicalForm gf_mipo
Definition: gfops.cc:56
gf_name
char gf_name
Definition: gfops.cc:52
cf_defs.h
gf_isff
bool gf_isff(long a)
Definition: gfops.cc:270
gf_q
int gf_q
Definition: gfops.cc:47
gf_iszero
bool gf_iszero(int a)
Definition: gfops.h:43
gf_sub
int gf_sub(int a, int b)
Definition: gfops.h:158
gf_n
int gf_n
Definition: gfops.cc:49
name
char name(const Variable &v)
Definition: factory.h:180
gf_print
void gf_print(OSTREAM &os, int a)
Definition: gfops.h:207
gf_mul
int gf_mul(int a, int b)
Definition: gfops.h:163
gf_table
unsigned short * gf_table
Definition: gfops.cc:54
cf_assert.h
p
int p
Definition: cfModGcd.cc:4019
gf_gf2ff
long gf_gf2ff(long a)
Definition: gfops.cc:226
gf_int2gf
int gf_int2gf(int i)
Definition: gfops.h:65
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
gf_p
int gf_p
Definition: gfops.cc:48
gf_m1
int gf_m1
Definition: gfops.cc:51
gf_setcharacteristic
void gf_setcharacteristic(int p, int n, char name)
Definition: gfops.cc:219