My Project
modulop.h
Go to the documentation of this file.
1#ifndef MODULOP_H
2#define MODULOP_H
3/****************************************
4* Computer Algebra System SINGULAR *
5****************************************/
6/*
7* ABSTRACT: numbers modulo p (<=32749)
8*/
9#include "misc/auxiliary.h"
10
11
12// define if a*b is with mod instead of tables
13//#define HAVE_GENERIC_MULT
14// define if 1/b is from tables
15//#define HAVE_INVTABLE
16// define if an if should be used
17//#define HAVE_GENERIC_ADD
18
19//#undef HAVE_GENERIC_ADD
20//#undef HAVE_GENERIC_MULT
21//#undef HAVE_INVTABLE
22
23//#define HAVE_GENERIC_ADD 1
24//#define HAVE_GENERIC_MULT 1
25//#define HAVE_INVTABLE 1
26
27// enable large primes (32749 < p < 2^31-)
28#define NV_OPS
29#define NV_MAX_PRIME 32749
30#define FACTORY_MAX_PRIME 536870909
31
32struct n_Procs_s; typedef struct n_Procs_s *coeffs;
33struct snumber; typedef struct snumber * number;
34
35BOOLEAN npInitChar(coeffs r, void* p);
36
37// inline number npMultM(number a, number b, int npPrimeM)
38// // return (a*b)%n
39// {
40// double ab;
41// long q, res;
42//
43// ab = ((double) ((int)a)) * ((double) ((int)b));
44// q = (long) (ab/((double) npPrimeM)); // q could be off by (+/-) 1
45// res = (long) (ab - ((double) q)*((double) npPrimeM));
46// res += (res >> 31) & npPrimeM;
47// res -= npPrimeM;
48// res += (res >> 31) & npPrimeM;
49// return (number)res;
50// }
51#ifdef HAVE_GENERIC_MULT
52static inline number npMultM(number a, number b, const coeffs r)
53{
54 return (number)
55 ((((unsigned long) a)*((unsigned long) b)) % ((unsigned long) r->ch));
56}
57static inline void npInpMultM(number &a, number b, const coeffs r)
58{
59 a=(number)
60 ((((unsigned long) a)*((unsigned long) b)) % ((unsigned long) r->ch));
61}
62#else
63static inline number npMultM(number a, number b, const coeffs r)
64{
65 long x = (long)r->npLogTable[(long)a]+ r->npLogTable[(long)b];
66 #ifdef HAVE_GENERIC_ADD
67 if (x>=r->npPminus1M) x-=r->npPminus1M;
68 #else
69 x-=r->npPminus1M;
70 #if SIZEOF_LONG == 8
71 x += (x >> 63) & r->npPminus1M;
72 #else
73 x += (x >> 31) & r->npPminus1M;
74 #endif
75 #endif
76 return (number)(long)r->npExpTable[x];
77}
78static inline void npInpMultM(number &a, number b, const coeffs r)
79{
80 long x = (long)r->npLogTable[(long)a]+ r->npLogTable[(long)b];
81 #ifdef HAVE_GENERIC_ADD
82 if (x>=r->npPminus1M) x-=r->npPminus1M;
83 #else
84 x-=r->npPminus1M;
85 #if SIZEOF_LONG == 8
86 x += (x >> 63) & r->npPminus1M;
87 #else
88 x += (x >> 31) & r->npPminus1M;
89 #endif
90 #endif
91 a=(number)(long)r->npExpTable[x];
92}
93#endif
94
95#if 0
96inline number npAddAsm(number a, number b, int m)
97{
98 number r;
99 asm ("addl %2, %1; cmpl %3, %1; jb 0f; subl %3, %1; 0:"
100 : "=&r" (r)
101 : "%0" (a), "g" (b), "g" (m)
102 : "cc");
103 return r;
104}
105inline number npSubAsm(number a, number b, int m)
106{
107 number r;
108 asm ("subl %2, %1; jnc 0f; addl %3, %1; 0:"
109 : "=&r" (r)
110 : "%0" (a), "g" (b), "g" (m)
111 : "cc");
112 return r;
113}
114#endif
115#ifdef HAVE_GENERIC_ADD
116static inline number npAddM(number a, number b, const coeffs r)
117{
118 unsigned long R = (unsigned long)a + (unsigned long)b;
119 return (number)(R >= (unsigned long)r->ch ? R - (unsigned long)r->ch : R);
120}
121static inline void npInpAddM(number &a, number b, const coeffs r)
122{
123 unsigned long R = (unsigned long)a + (unsigned long)b;
124 a=(number)(R >= (unsigned long)r->ch ? R - (unsigned long)r->ch : R);
125}
126static inline number npSubM(number a, number b, const coeffs r)
127{
128 return (number)((long)a<(long)b ?
129 r->ch-(long)b+(long)a : (long)a-(long)b);
130}
131#else
132static inline number npAddM(number a, number b, const coeffs r)
133{
134 unsigned long res = ((unsigned long)a + (unsigned long)b);
135 res -= r->ch;
136#if SIZEOF_LONG == 8
137 res += ((long)res >> 63) & r->ch;
138#else
139 res += ((long)res >> 31) & r->ch;
140#endif
141 return (number)res;
142}
143static inline void npInpAddM(number &a, number b, const coeffs r)
144{
145 unsigned long res = ((unsigned long)a + (unsigned long)b);
146 res -= r->ch;
147#if SIZEOF_LONG == 8
148 res += ((long)res >> 63) & r->ch;
149#else
150 res += ((long)res >> 31) & r->ch;
151#endif
152 a=(number)res;
153}
154static inline number npSubM(number a, number b, const coeffs r)
155{
156 long res = ((long)a - (long)b);
157#if SIZEOF_LONG == 8
158 res += (res >> 63) & r->ch;
159#else
160 res += (res >> 31) & r->ch;
161#endif
162 return (number)res;
163}
164#endif
165
166static inline number npNegM(number a, const coeffs r)
167{
168 return (number)((long)(r->ch)-(long)(a));
169}
170
171static inline BOOLEAN npIsOne (number a, const coeffs)
172{
173 return 1 == (long)a;
174}
175
176static inline long npInvMod(long a, const coeffs R)
177{
178 long s;
179
180 long u, v, u0, u1, u2, q, r;
181
182 assume(a>0);
183 u1=1; u2=0;
184 u = a; v = R->ch;
185
186 do
187 {
188 q = u / v;
189 //r = u % v;
190 r = u - q*v;
191 u = v;
192 v = r;
193 u0 = u2;
194 u2 = u1 - q*u2;
195 u1 = u0;
196 } while (v != 0);
197
198 assume(u==1);
199 s = u1;
200#ifdef HAVE_GENERIC_ADD
201 if (s < 0)
202 return s + R->ch;
203 else
204 return s;
205#else
206 #if SIZEOF_LONG == 8
207 s += (s >> 63) & R->ch;
208 #else
209 s += (s >> 31) & R->ch;
210 #endif
211 return s;
212#endif
213}
214
215static inline number npInversM (number c, const coeffs r)
216{
217 n_Test(c, r);
218#ifndef HAVE_GENERIC_MULT
219 #ifndef HAVE_INVTABLE
220 number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
221 #else
222 long inv=(long)r->npInvTable[(long)c];
223 if (inv==0)
224 {
225 inv = (long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
226 r->npInvTable[(long)c]=inv;
227 }
228 number d = (number)inv;
229 #endif
230#else
231 #ifdef HAVE_INVTABLE
232 long inv=(long)r->npInvTable[(long)c];
233 if (inv==0)
234 {
235 inv=npInvMod((long)c,r);
236 r->npInvTable[(long)c]=inv;
237 }
238 #else
239 long inv=npInvMod((long)c,r);
240 #endif
241 number d = (number)inv;
242#endif
243 n_Test(d, r);
244 return d;
245}
246
247
248// The folloing is reused inside gnumpc.cc, gnumpfl.cc and longrat.cc
249long npInt (number &n, const coeffs r);
250
251#define npEqualM(A,B,r) ((A)==(B))
252
253#endif
All the auxiliary stuff.
int BOOLEAN
Definition: auxiliary.h:87
int m
Definition: cfEzgcd.cc:128
Variable x
Definition: cfModGcd.cc:4084
int p
Definition: cfModGcd.cc:4080
CanonicalForm b
Definition: cfModGcd.cc:4105
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:736
const CanonicalForm int s
Definition: facAbsFact.cc:51
CanonicalForm res
Definition: facAbsFact.cc:60
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
mpz_t n
Definition: longrat.h:51
'SR_INT' is the type of those integers small enough to fit into 29 bits.
Definition: longrat.h:49
#define assume(x)
Definition: mod2.h:387
static BOOLEAN npIsOne(number a, const coeffs)
Definition: modulop.h:171
static number npAddM(number a, number b, const coeffs r)
Definition: modulop.h:116
static number npMultM(number a, number b, const coeffs r)
Definition: modulop.h:63
BOOLEAN npInitChar(coeffs r, void *p)
Definition: modulop.cc:340
static number npNegM(number a, const coeffs r)
Definition: modulop.h:166
static void npInpMultM(number &a, number b, const coeffs r)
Definition: modulop.h:78
static long npInvMod(long a, const coeffs R)
Definition: modulop.h:176
static number npInversM(number c, const coeffs r)
Definition: modulop.h:215
long npInt(number &n, const coeffs r)
Definition: modulop.cc:85
static void npInpAddM(number &a, number b, const coeffs r)
Definition: modulop.h:121
static number npSubM(number a, number b, const coeffs r)
Definition: modulop.h:126
The main handler for Singular numbers which are suitable for Singular polynomials.
#define R
Definition: sirandom.c:27