My Project
Loading...
Searching...
No Matches
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
37
38EXTERN_VAR unsigned short * gf_table;
39
41
42//{{{ predicates
43inline bool gf_iszero ( int a )
44{
45 return gf_q == a;
46}
47
48inline bool gf_iszero ( long a )
49{
50 return gf_q == a;
51}
52
53inline bool gf_isone ( int a )
54{
55 return 0 == a;
56}
57
58inline bool gf_isone ( long a )
59{
60 return 0 == a;
61}
62//}}}
63
64//{{{ conversion functions
65inline 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
81inline 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
99inline int gf_zero()
100{
101 return gf_q;
102}
103
104inline int gf_one()
105{
106 return 0;
107}
108//}}}
109
110//{{{ inline int gf_sign ( int a )
111// docu: see imm_sign()
112inline
113int gf_sign ( int a )
114{
115 if ( gf_iszero( a ) )
116 return 0;
117 else
118 return 1;
119}
120//}}}
121
122//{{{ arithmetic operators
123inline 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
133inline 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
158inline int gf_sub ( int a, int b )
159{
160 return gf_add( a, gf_neg( b ) );
161}
162
163inline 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
174inline 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
185inline 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
198inline 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
207inline 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
222inline 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
232inline 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
243void gf_setcharacteristic ( int p, int n, char name );
244
245// Singular needs this
246/*BEGINPUBLIC*/
247
248long gf_gf2ff ( long a );
249int gf_gf2ff ( int a );
250
251bool gf_isff ( long a );
252bool gf_isff ( int a );
253
254/*ENDPUBLIC*/
255
256#endif /* ! INCL_GFOPS_H */
Header for factory's main class CanonicalForm.
int i
Definition: cfEzgcd.cc:132
int p
Definition: cfModGcd.cc:4078
CanonicalForm b
Definition: cfModGcd.cc:4103
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
factory switches.
factory's main class
Definition: canonicalform.h:86
const CanonicalForm int s
Definition: facAbsFact.cc:51
EXTERN_VAR int gf_q
Definition: gfops.h:31
EXTERN_VAR unsigned short * gf_table
Definition: gfops.h:38
int gf_sub(int a, int b)
Definition: gfops.h:158
int gf_int2gf(int i)
Definition: gfops.h:65
void gf_setcharacteristic(int p, int n, char name)
Definition: gfops.cc:202
EXTERN_VAR int gf_m1
Definition: gfops.h:35
#define OSTREAM
Definition: gfops.h:19
int gf_neg(int a)
Definition: gfops.h:123
bool gf_isone(int a)
Definition: gfops.h:53
int gf_inv(int a)
Definition: gfops.h:198
int gf_power(int a, int n)
Definition: gfops.h:222
int gf_zero()
Definition: gfops.h:99
bool gf_iszero(int a)
Definition: gfops.h:43
int gf_one()
Definition: gfops.h:104
int gf_mul(int a, int b)
Definition: gfops.h:163
int gf_div(int a, int b)
Definition: gfops.h:185
EXTERN_INST_VAR CanonicalForm gf_mipo
Definition: gfops.h:40
int gf_sign(int a)
Definition: gfops.h:113
EXTERN_VAR int gf_q1
Definition: gfops.h:34
long gf_gf2ff(long a)
Definition: gfops.cc:209
EXTERN_VAR char gf_name
Definition: gfops.h:36
bool gf_isff(long a)
Definition: gfops.cc:253
EXTERN_VAR int gf_n
Definition: gfops.h:33
int gf_add(int a, int b)
Definition: gfops.h:133
EXTERN_VAR int gf_p
Definition: gfops.h:32
#define EXTERN_INST_VAR
Definition: globaldefs.h:9
#define EXTERN_VAR
Definition: globaldefs.h:6
int name
New type name for int.
Definition: templateForC.h:21