modulop.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: numbers modulo p (<=32749)
6 */
7 
8 #include <misc/auxiliary.h>
9 #include <omalloc/omalloc.h>
10 
11 #include <factory/factory.h>
12 
13 #include <misc/mylimits.h>
14 #include <misc/sirandom.h>
15 
16 #include <reporter/reporter.h>
17 
18 #include <coeffs/coeffs.h>
19 #include <coeffs/numbers.h>
20 #include <coeffs/mpr_complex.h>
21 
22 #include "longrat.h"
23 #include "modulop.h"
24 
25 #include <string.h>
26 
27 BOOLEAN npGreaterZero (number k, const coeffs r);
28 number npMult (number a, number b, const coeffs r);
29 number npInit (long i, const coeffs r);
30 long npInt (number &n, const coeffs r);
31 number npAdd (number a, number b,const coeffs r);
32 number npSub (number a, number b,const coeffs r);
33 void npPower (number a, int i, number * result,const coeffs r);
34 BOOLEAN npIsZero (number a,const coeffs r);
35 BOOLEAN npIsOne (number a,const coeffs r);
36 BOOLEAN npIsMOne (number a,const coeffs r);
37 number npDiv (number a, number b,const coeffs r);
38 number npNeg (number c,const coeffs r);
39 number npInvers (number c,const coeffs r);
40 BOOLEAN npGreater (number a, number b,const coeffs r);
41 BOOLEAN npEqual (number a, number b,const coeffs r);
42 void npWrite (number a, const coeffs r);
43 void npCoeffWrite (const coeffs r, BOOLEAN details);
44 const char * npRead (const char *s, number *a,const coeffs r);
45 
46 #ifdef LDEBUG
47 BOOLEAN npDBTest (number a, const char *f, const int l, const coeffs r);
48 #endif
49 
50 //int npGetChar();
51 
52 nMapFunc npSetMap(const coeffs src, const coeffs dst);
53 number npMapP(number from, const coeffs src, const coeffs r);
54 
55 // extern int npGen; // obsolete
56 
57 // int npGen=0;
58 
59 /*-------specials for spolys, do NOT use otherwise--------------------------*/
60 /* for npMultM, npSubM, npNegM, npEqualM : */
61 #ifdef HAVE_DIV_MOD
62 extern unsigned short *npInvTable;
63 #else
64 #ifndef HAVE_MULT_MOD
65 extern long npPminus1M;
66 extern unsigned short *npExpTable;
67 extern unsigned short *npLogTable;
68 #endif
69 #endif
70 
71 #ifdef NV_OPS
72 #pragma GCC diagnostic ignored "-Wlong-long"
73 static inline number nvMultM(number a, number b, const coeffs r)
74 {
75  assume( getCoeffType(r) == n_Zp );
76 
77 #if SIZEOF_LONG == 4
78 #define ULONG64 (unsigned long long)(unsigned long)
79 #else
80 #define ULONG64 (unsigned long)
81 #endif
82  return (number)
83  (unsigned long)((ULONG64 a)*(ULONG64 b) % (ULONG64 r->ch));
84 }
85 number nvMult (number a, number b, const coeffs r);
86 number nvDiv (number a, number b, const coeffs r);
87 number nvInvers (number c, const coeffs r);
88 //void nvPower (number a, int i, number * result, const coeffs r);
89 #endif
90 
91 
92 
93 
94 BOOLEAN npGreaterZero (number k, const coeffs r)
95 {
96  n_Test(k, r);
97 
98  int h = (int)((long) k);
99  return ((int)h !=0) && (h <= (r->ch>>1));
100 }
101 
102 //unsigned long npMultMod(unsigned long a, unsigned long b, int npPrimeM)
103 //{
104 // unsigned long c = a*b;
105 // c = c % npPrimeM;
106 // assume(c == (unsigned long) npMultM((number) a, (number) b, npPrimeM));
107 // return c;
108 //}
109 
110 number npMult (number a,number b, const coeffs r)
111 {
112  n_Test(a, r);
113  n_Test(b, r);
114 
115  if (((long)a == 0) || ((long)b == 0))
116  return (number)0;
117  number c = npMultM(a,b, r);
118  n_Test(c, r);
119  return c;
120 }
121 
122 /*2
123 * create a number from int
124 */
125 number npInit (long i, const coeffs r)
126 {
127  long ii=i % (long)r->ch;
128  if (ii < 0L) ii += (long)r->ch;
129 
130  number c = (number)ii;
131  n_Test(c, r);
132  return c;
133 
134 }
135 
136 
137 /*2
138  * convert a number to an int in (-p/2 .. p/2]
139  */
140 long npInt(number &n, const coeffs r)
141 {
142  n_Test(n, r);
143 
144  if ((long)n > (((long)r->ch) >>1)) return ((long)n -((long)r->ch));
145  else return ((long)n);
146 }
147 
148 number npAdd (number a, number b, const coeffs r)
149 {
150  n_Test(a, r);
151  n_Test(b, r);
152 
153  number c = npAddM(a,b, r);
154 
155  n_Test(c, r);
156 
157  return c;
158 }
159 
160 number npSub (number a, number b, const coeffs r)
161 {
162  n_Test(a, r);
163  n_Test(b, r);
164 
165  number c = npSubM(a,b,r);
166 
167  n_Test(c, r);
168 
169  return c;
170 }
171 
172 BOOLEAN npIsZero (number a, const coeffs r)
173 {
174  n_Test(a, r);
175 
176  return 0 == (long)a;
177 }
178 
179 BOOLEAN npIsOne (number a, const coeffs r)
180 {
181  n_Test(a, r);
182 
183  return 1 == (long)a;
184 }
185 
186 BOOLEAN npIsMOne (number a, const coeffs r)
187 {
188  n_Test(a, r);
189 
190  return ((r->npPminus1M == (long)a) &&(1L!=(long)a))/*for char 2*/;
191 }
192 
193 #ifdef HAVE_DIV_MOD
194 
195 #ifdef USE_NTL_XGCD
196 
197 //ifdef HAVE_NTL // in ntl.a
198 //extern void XGCD(long& d, long& s, long& t, long a, long b);
199 #include <NTL/ZZ.h>
200 #ifdef NTL_CLIENT
201 NTL_CLIENT
202 #endif
203 
204 #endif
205 
206 long InvMod(long a, const coeffs R)
207 {
208  long d, s, t;
209 
210 #ifdef USE_NTL_XGCD
211  XGCD(d, s, t, a, R->ch);
212  assume (d == 1);
213 #else
214  long u, v, u0, v0, u1, v1, u2, v2, q, r;
215 
216  assume(a>0);
217  u1=1; u2=0;
218  u = a; v = R->ch;
219 
220  while (v != 0)
221  {
222  q = u / v;
223  r = u % v;
224  u = v;
225  v = r;
226  u0 = u2;
227  u2 = u1 - q*u2;
228  u1 = u0;
229  }
230 
231  assume(u==1);
232  s = u1;
233 #endif
234  if (s < 0)
235  return s + R->ch;
236  else
237  return s;
238 }
239 #endif
240 
241 inline number npInversM (number c, const coeffs r)
242 {
243  n_Test(c, r);
244 #ifndef HAVE_DIV_MOD
245  number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
246 #else
247  long inv=(long)r->npInvTable[(long)c];
248  if (inv==0)
249  {
250  inv=InvMod((long)c,r);
251  r->npInvTable[(long)c]=inv;
252  }
253  number d = (number)inv;
254 #endif
255  n_Test(d, r);
256  return d;
257 
258 }
259 
260 number npDiv (number a,number b, const coeffs r)
261 {
262  n_Test(a, r);
263  n_Test(b, r);
264 
265 //#ifdef NV_OPS
266 // if (r->ch>NV_MAX_PRIME)
267 // return nvDiv(a,b);
268 //#endif
269  if ((long)a==0L)
270  return (number)0L;
271  number d;
272 
273 #ifndef HAVE_DIV_MOD
274  if ((long)b==0L)
275  {
276  WerrorS(nDivBy0);
277  return (number)0L;
278  }
279 
280  int s = r->npLogTable[(long)a] - r->npLogTable[(long)b];
281  if (s < 0)
282  s += r->npPminus1M;
283  d = (number)(long)r->npExpTable[s];
284 #else
285  number inv=npInversM(b,r);
286  d = npMultM(a,inv,r);
287 #endif
288 
289  n_Test(d, r);
290  return d;
291 
292 }
293 number npInvers (number c, const coeffs r)
294 {
295  n_Test(c, r);
296 
297  if ((long)c==0L)
298  {
299  WerrorS("1/0");
300  return (number)0L;
301  }
302  number d = npInversM(c,r);
303 
304  n_Test(d, r);
305  return d;
306 
307 }
308 
309 number npNeg (number c, const coeffs r)
310 {
311  n_Test(c, r);
312 
313  if ((long)c==0L) return c;
314 
315 #if 0
316  number d = npNegM(c,r);
317  n_Test(d, r);
318  return d;
319 #else
320  c = npNegM(c,r);
321  n_Test(c, r);
322  return c;
323 #endif
324 }
325 
326 BOOLEAN npGreater (number a,number b, const coeffs r)
327 {
328  n_Test(a, r);
329  n_Test(b, r);
330 
331  //return (long)a != (long)b;
332  return ((long)a) > ((long)b);
333 }
334 
335 BOOLEAN npEqual (number a,number b, const coeffs r)
336 {
337  n_Test(a, r);
338  n_Test(b, r);
339 
340 // return (long)a == (long)b;
341 
342  return npEqualM(a,b,r);
343 }
344 
345 void npWrite (number a, const coeffs r)
346 {
347  n_Test(a, r);
348 
349  if ((long)a>(((long)r->ch) >>1)) StringAppend("-%d",(int)(((long)r->ch)-((long)a)));
350  else StringAppend("%d",(int)((long)a));
351 }
352 
353 #if 0
354 void npPower (number a, int i, number * result, const coeffs r)
355 {
356  n_Test(a, r);
357 
358  if (i==0)
359  {
360  //npInit(1,result);
361  *(long *)result = 1;
362  }
363  else if (i==1)
364  {
365  *result = a;
366  }
367  else
368  {
369  npPower(a,i-1,result,r);
370  *result = npMultM(a,*result,r);
371  }
372 }
373 #endif
374 
375 static const char* npEati(const char *s, int *i, const coeffs r)
376 {
377 
378  if (((*s) >= '0') && ((*s) <= '9'))
379  {
380  unsigned long ii=0L;
381  do
382  {
383  ii *= 10;
384  ii += *s++ - '0';
385  if (ii >= (MAX_INT_VAL / 10)) ii = ii % r->ch;
386  }
387  while (((*s) >= '0') && ((*s) <= '9'));
388  if (ii >= (unsigned long)r->ch) ii = ii % r->ch;
389  *i=(int)ii;
390  }
391  else (*i) = 1;
392  return s;
393 }
394 
395 const char * npRead (const char *s, number *a, const coeffs r)
396 {
397  int z;
398  int n=1;
399 
400  s = npEati(s, &z, r);
401  if ((*s) == '/')
402  {
403  s++;
404  s = npEati(s, &n, r);
405  }
406  if (n == 1)
407  *a = (number)(long)z;
408  else
409  {
410  if ((z==0)&&(n==0)) WerrorS(nDivBy0);
411  else
412  {
413 #ifdef NV_OPS
414  if (r->ch>NV_MAX_PRIME)
415  *a = nvDiv((number)(long)z,(number)(long)n,r);
416  else
417 #endif
418  *a = npDiv((number)(long)z,(number)(long)n,r);
419  }
420  }
421  n_Test(*a, r);
422  return s;
423 }
424 
425 /*2
426 * set the charcteristic (allocate and init tables)
427 */
428 
430 {
431  #ifdef HAVE_DIV_MOD
432  if (r->npInvTable!=NULL)
433  omFreeSize( (void *)r->npInvTable, r->ch*sizeof(unsigned short) );
434  r->npInvTable=NULL;
435  #else
436  if (r->npExpTable!=NULL)
437  {
438  omFreeSize( (void *)r->npExpTable, r->ch*sizeof(unsigned short) );
439  omFreeSize( (void *)r->npLogTable, r->ch*sizeof(unsigned short) );
440  r->npExpTable=NULL; r->npLogTable=NULL;
441  }
442  #endif
443 }
444 
445 static BOOLEAN npCoeffsEqual(const coeffs r, n_coeffType n, void * parameter)
446 {
447  /* test, if r is an instance of nInitCoeffs(n,parameter) */
448  return (n==n_Zp) && (r->ch==(int)(long)parameter);
449 }
450 CanonicalForm npConvSingNFactoryN( number n, BOOLEAN setChar, const coeffs r )
451 {
452  if (setChar) setCharacteristic( r->ch );
453  CanonicalForm term(npInt( n,r ));
454  return term;
455 }
456 
457 number npConvFactoryNSingN( const CanonicalForm n, const coeffs r)
458 {
459  if (n.isImm())
460  {
461  return npInit(n.intval(),r);
462  }
463  else
464  {
465  assume(0);
466  return NULL;
467  }
468 }
469 
470 static char* npCoeffName(const coeffs cf)
471 {
472  static char npCoeffName_buf[15];
473  snprintf(npCoeffName_buf,14,"ZZ/%d",cf->ch);
474  return npCoeffName_buf;
475 }
476 
477 static char* npCoeffString(const coeffs cf)
478 {
479  return omStrDup(npCoeffName(cf));
480 }
481 
482 static void npWriteFd(number n, FILE* f, const coeffs)
483 {
484  fprintf(f,"%d ",(int)(long)n);
485 }
486 
487 static number npReadFd(s_buff f, const coeffs)
488 {
489  // read int
490  int dd;
491  dd=s_readint(f);
492  return (number)(long)dd;
493 }
494 
495 static number npRandom(siRandProc p, number, number, const coeffs cf)
496 {
497  return npInit(p(),cf);
498 }
499 
501 {
502  assume( getCoeffType(r) == n_Zp );
503  const int c = (int) (long) p;
504 
505  assume( c > 0 );
506 
507  int i, w;
508 
509  r->is_field=TRUE;
510  r->is_domain=TRUE;
511  r->rep=n_rep_int;
512 
513  r->ch = c;
514  r->npPminus1M = c /*r->ch*/ - 1;
515 
516  //r->cfInitChar=npInitChar;
517  r->cfKillChar=npKillChar;
518  r->nCoeffIsEqual=npCoeffsEqual;
519  r->cfCoeffString=npCoeffString;
520  r->cfCoeffName=npCoeffName;
521  r->cfCoeffWrite=npCoeffWrite;
522 
523  r->cfMult = npMult;
524  r->cfSub = npSub;
525  r->cfAdd = npAdd;
526  r->cfDiv = npDiv;
527  r->cfInit = npInit;
528  //r->cfSize = ndSize;
529  r->cfInt = npInt;
530  #ifdef HAVE_RINGS
531  //r->cfDivComp = NULL; // only for ring stuff
532  //r->cfIsUnit = NULL; // only for ring stuff
533  //r->cfGetUnit = NULL; // only for ring stuff
534  //r->cfExtGcd = NULL; // only for ring stuff
535  // r->cfDivBy = NULL; // only for ring stuff
536  #endif
537  r->cfInpNeg = npNeg;
538  r->cfInvers= npInvers;
539  //r->cfCopy = ndCopy;
540  //r->cfRePart = ndCopy;
541  //r->cfImPart = ndReturn0;
542  r->cfWriteLong = npWrite;
543  r->cfRead = npRead;
544  //r->cfNormalize=ndNormalize;
545  r->cfGreater = npGreater;
546  r->cfEqual = npEqual;
547  r->cfIsZero = npIsZero;
548  r->cfIsOne = npIsOne;
549  r->cfIsMOne = npIsMOne;
550  r->cfGreaterZero = npGreaterZero;
551  //r->cfPower = npPower;
552  //r->cfGetDenom = ndGetDenom;
553  //r->cfGetNumerator = ndGetNumerator;
554  //r->cfGcd = ndGcd;
555  //r->cfLcm = ndGcd;
556  //r->cfDelete= ndDelete;
557  r->cfSetMap = npSetMap;
558  //r->cfName = ndName;
559  //r->cfInpMult=ndInpMult;
560 #ifdef NV_OPS
561  if (c>NV_MAX_PRIME)
562  {
563  r->cfMult = nvMult;
564  r->cfDiv = nvDiv;
565  r->cfExactDiv= nvDiv;
566  r->cfInvers= nvInvers;
567  //r->cfPower= nvPower;
568  }
569 #endif
570 #ifdef LDEBUG
571  // debug stuff
572  r->cfDBTest=npDBTest;
573 #endif
574 
575  r->convSingNFactoryN=npConvSingNFactoryN;
576  r->convFactoryNSingN=npConvFactoryNSingN;
577 
578  r->cfRandom=npRandom;
579 
580  // io via ssi
581  r->cfWriteFd=npWriteFd;
582  r->cfReadFd=npReadFd;
583 
584  // the variables:
585  r->nNULL = (number)0;
586  r->type = n_Zp;
587  r->ch = c;
588  r->has_simple_Alloc=TRUE;
589  r->has_simple_Inverse=TRUE;
590 
591  // the tables
592 #ifdef NV_OPS
593  if (r->ch <=NV_MAX_PRIME)
594 #endif
595  {
596 #if !defined(HAVE_DIV_MOD) || !defined(HAVE_MULT_MOD)
597  r->npExpTable=(unsigned short *)omAlloc( r->ch*sizeof(unsigned short) );
598  r->npLogTable=(unsigned short *)omAlloc( r->ch*sizeof(unsigned short) );
599  r->npExpTable[0] = 1;
600  r->npLogTable[0] = 0;
601  if (r->ch > 2)
602  {
603  w = 1;
604  loop
605  {
606  r->npLogTable[1] = 0;
607  w++;
608  i = 0;
609  loop
610  {
611  i++;
612  r->npExpTable[i] =(int)(((long)w * (long)r->npExpTable[i-1]) % r->ch);
613  r->npLogTable[r->npExpTable[i]] = i;
614  if /*(i == r->ch - 1 ) ||*/ (/*(*/ r->npExpTable[i] == 1 /*)*/)
615  break;
616  }
617  if (i == r->ch - 1)
618  break;
619  }
620  }
621  else
622  {
623  r->npExpTable[1] = 1;
624  r->npLogTable[1] = 0;
625  }
626 #endif
627 #ifdef HAVE_DIV_MOD
628  r->npInvTable=(unsigned short*)omAlloc0( r->ch*sizeof(unsigned short) );
629 #endif
630  }
631  return FALSE;
632 }
633 
634 #ifdef LDEBUG
635 BOOLEAN npDBTest (number a, const char *f, const int l, const coeffs r)
636 {
637  if (((long)a<0L) || ((long)a>(long)r->ch))
638  {
639  Print("wrong mod p number %ld at %s,%d\n",(long)a,f,l);
640  return FALSE;
641  }
642  return TRUE;
643 }
644 #endif
645 
646 number npMapP(number from, const coeffs src, const coeffs dst_r)
647 {
648  long i = (long)from;
649  if (i>src->ch/2)
650  {
651  i-=src->ch;
652  while (i < 0) i+=dst_r->ch;
653  }
654  i%=dst_r->ch;
655  return (number)i;
656 }
657 
658 static number npMapLongR(number from, const coeffs /*src*/, const coeffs dst_r)
659 {
660  gmp_float *ff=(gmp_float*)from;
661  mpf_t *f=ff->_mpfp();
662  number res;
663  mpz_ptr dest,ndest;
664  int size,i;
665  int e,al,bl;
666  long iz;
667  mp_ptr qp,dd,nn;
668 
669  size = (*f)[0]._mp_size;
670  if (size == 0)
671  return npInit(0,dst_r);
672  if(size<0)
673  size = -size;
674 
675  qp = (*f)[0]._mp_d;
676  while(qp[0]==0)
677  {
678  qp++;
679  size--;
680  }
681 
682  if(dst_r->ch>2)
683  e=(*f)[0]._mp_exp-size;
684  else
685  e=0;
686  res = ALLOC_RNUMBER();
687 #if defined(LDEBUG)
688  res->debug=123456;
689 #endif
690  dest = res->z;
691 
692  long in=0;
693  if (e<0)
694  {
695  al = dest->_mp_size = size;
696  if (al<2) al = 2;
697  dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
698  for (i=0;i<size;i++) dd[i] = qp[i];
699  bl = 1-e;
700  nn = (mp_ptr)omAlloc(sizeof(mp_limb_t)*bl);
701  nn[bl-1] = 1;
702  for (i=bl-2;i>=0;i--) nn[i] = 0;
703  ndest = res->n;
704  ndest->_mp_d = nn;
705  ndest->_mp_alloc = ndest->_mp_size = bl;
706  res->s = 0;
707  in=mpz_fdiv_ui(ndest,dst_r->ch);
708  mpz_clear(ndest);
709  }
710  else
711  {
712  al = dest->_mp_size = size+e;
713  if (al<2) al = 2;
714  dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
715  for (i=0;i<size;i++) dd[i+e] = qp[i];
716  for (i=0;i<e;i++) dd[i] = 0;
717  res->s = 3;
718  }
719 
720  dest->_mp_d = dd;
721  dest->_mp_alloc = al;
722  iz=mpz_fdiv_ui(dest,dst_r->ch);
723  mpz_clear(dest);
724  if(res->s==0)
725  iz=(long)npDiv((number)iz,(number)in,dst_r);
726  FREE_RNUMBER(res); // Q!?
727  return (number)iz;
728 }
729 
730 #ifdef HAVE_RINGS
731 /*2
732 * convert from a GMP integer
733 */
734 number npMapGMP(number from, const coeffs /*src*/, const coeffs dst)
735 {
736  mpz_ptr erg = (mpz_ptr) omAlloc(sizeof(mpz_t)); // evtl. spaeter mit bin
737  mpz_init(erg);
738 
739  mpz_mod_ui(erg, (mpz_ptr) from, dst->ch);
740  number r = (number) mpz_get_si(erg);
741 
742  mpz_clear(erg);
743  omFree((void *) erg);
744  return (number) r;
745 }
746 
747 number npMapZ(number from, const coeffs src, const coeffs dst)
748 {
749  if (SR_HDL(from) & SR_INT)
750  {
751  long f_i=SR_TO_INT(from);
752  return npInit(f_i,dst);
753  }
754  return npMapGMP(from,src,dst);
755 }
756 
757 /*2
758 * convert from an machine long
759 */
760 number npMapMachineInt(number from, const coeffs /*src*/,const coeffs dst)
761 {
762  long i = (long) (((unsigned long) from) % dst->ch);
763  return (number) i;
764 }
765 #endif
766 
767 number npMapCanonicalForm (number a, const coeffs /*src*/, const coeffs dst)
768 {
769  setCharacteristic (dst ->ch);
771  return (number) (f.intval());
772 }
773 
774 nMapFunc npSetMap(const coeffs src, const coeffs dst)
775 {
776 #ifdef HAVE_RINGS
777  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src))
778  {
779  return npMapMachineInt;
780  }
781  if (src->rep==n_rep_gmp) //nCoeff_is_Ring_Z(src) || nCoeff_is_Ring_PtoM(src) || nCoeff_is_Ring_ModN(src))
782  {
783  return npMapGMP;
784  }
785  if (src->rep==n_rep_gap_gmp) //nCoeff_is_Ring_Z(src)
786  {
787  return npMapZ;
788  }
789 #endif
790  if (src->rep==n_rep_gap_rat) /* Q, Z */
791  {
792  return nlModP; // npMap0; // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to Zp // FIXME!
793  }
794  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) )
795  {
796  if (n_GetChar(src) == n_GetChar(dst))
797  {
798  return ndCopyMap;
799  }
800  else
801  {
802  return npMapP;
803  }
804  }
805  if ((src->rep==n_rep_gmp_float) && nCoeff_is_long_R(src))
806  {
807  return npMapLongR;
808  }
809  if (nCoeff_is_CF (src))
810  {
811  return npMapCanonicalForm;
812  }
813  return NULL; /* default */
814 }
815 
816 // -----------------------------------------------------------
817 // operation for very large primes (32749< p < 2^31-1)
818 // ----------------------------------------------------------
819 #ifdef NV_OPS
820 
821 number nvMult (number a,number b, const coeffs r)
822 {
823  //if (((long)a == 0) || ((long)b == 0))
824  // return (number)0;
825  //else
826  return nvMultM(a,b,r);
827 }
828 
829 void nvInpMult(number &a, number b, const coeffs r)
830 {
831  number n=nvMultM(a,b,r);
832  a=n;
833 }
834 
835 
836 inline long nvInvMod(long a, const coeffs R)
837 {
838 #ifdef HAVE_DIV_MOD
839  return InvMod(a, R);
840 #else
841 /// TODO: use "long InvMod(long a, const coeffs R)"?!
842 
843  long s;
844 
845  long u, u0, u1, u2, q, r; // v0, v1, v2,
846 
847  u1=1; // v1=0;
848  u2=0; // v2=1;
849  u = a;
850 
851  long v = R->ch;
852 
853  while (v != 0)
854  {
855  q = u / v;
856  r = u % v;
857  u = v;
858  v = r;
859  u0 = u2;
860 // v0 = v2;
861  u2 = u1 - q*u2;
862 // v2 = v1 - q*v2;
863  u1 = u0;
864 // v1 = v0;
865  }
866 
867  s = u1;
868  //t = v1;
869  if (s < 0)
870  return s + R->ch;
871  else
872  return s;
873 #endif
874 }
875 
876 inline number nvInversM (number c, const coeffs r)
877 {
878  long inv=nvInvMod((long)c,r);
879  return (number)inv;
880 }
881 
882 number nvDiv (number a,number b, const coeffs r)
883 {
884  if ((long)a==0L)
885  return (number)0L;
886  else if ((long)b==0L)
887  {
888  WerrorS(nDivBy0);
889  return (number)0L;
890  }
891  else
892  {
893  number inv=nvInversM(b,r);
894  return nvMultM(a,inv,r);
895  }
896 }
897 number nvInvers (number c, const coeffs r)
898 {
899  if ((long)c==0L)
900  {
901  WerrorS(nDivBy0);
902  return (number)0L;
903  }
904  return nvInversM(c,r);
905 }
906 #if 0
907 void nvPower (number a, int i, number * result, const coeffs r)
908 {
909  if (i==0)
910  {
911  //npInit(1,result);
912  *(long *)result = 1;
913  }
914  else if (i==1)
915  {
916  *result = a;
917  }
918  else
919  {
920  nvPower(a,i-1,result,r);
921  *result = nvMultM(a,*result,r);
922  }
923 }
924 #endif
925 #endif
926 
927 void npCoeffWrite (const coeffs r, BOOLEAN /*details*/)
928 {
929  Print("// characteristic : %d\n",r->ch);
930 }
931 
long intval() const
conversion functions
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
#define Print
Definition: emacs.cc:83
unsigned short * npExpTable
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:834
static number npMultM(number a, number b, const coeffs r)
Definition: modulop.h:49
number npInit(long i, const coeffs r)
Definition: modulop.cc:125
long npInt(number &n, const coeffs r)
Definition: modulop.cc:140
Definition: int_poly.h:33
loop
Definition: myNF.cc:98
number nlModP(number q, const coeffs, const coeffs Zp)
Definition: longrat.cc:1425
if(0 > strat->sl)
Definition: myNF.cc:73
#define FALSE
Definition: auxiliary.h:94
number npMapZ(number from, const coeffs src, const coeffs dst)
Definition: modulop.cc:747
mpf_t * _mpfp()
Definition: mpr_complex.h:134
return P p
Definition: myNF.cc:203
number nvInvers(number c, const coeffs r)
Definition: modulop.cc:897
static void npWriteFd(number n, FILE *f, const coeffs)
Definition: modulop.cc:482
f
Definition: cfModGcd.cc:4022
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:244
bool isImm() const
static unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:249
static FORCE_INLINE BOOLEAN nCoeff_is_long_R(const coeffs r)
Definition: coeffs.h:908
void npPower(number a, int i, number *result, const coeffs r)
number npInvers(number c, const coeffs r)
Definition: modulop.cc:293
#define npEqualM(A, B, r)
Definition: modulop.h:132
static char * npCoeffName(const coeffs cf)
Definition: modulop.cc:470
number nvMult(number a, number b, const coeffs r)
Definition: modulop.cc:821
long nvInvMod(long a, const coeffs R)
Definition: modulop.cc:836
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
{p < 2^31}
Definition: coeffs.h:30
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:750
(), see rinteger.h, new impl.
Definition: coeffs.h:112
number npAdd(number a, number b, const coeffs r)
Definition: modulop.cc:148
void nvInpMult(number &a, number b, const coeffs r)
Definition: modulop.cc:829
number npMapP(number from, const coeffs src, const coeffs r)
Definition: modulop.cc:646
void npWrite(number a, const coeffs r)
Definition: modulop.cc:345
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition: coeffs.h:448
factory&#39;s main class
Definition: canonicalform.h:75
#define TRUE
Definition: auxiliary.h:98
number npDiv(number a, number b, const coeffs r)
Definition: modulop.cc:260
#define FREE_RNUMBER(x)
Definition: coeffs.h:86
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:93
BOOLEAN npEqual(number a, number b, const coeffs r)
Definition: modulop.cc:335
BOOLEAN npInitChar(coeffs r, void *p)
Definition: modulop.cc:500
#define omAlloc(size)
Definition: omAllocDecl.h:210
long npPminus1M
BOOLEAN npDBTest(number a, const char *f, const int l, const coeffs r)
Definition: modulop.cc:635
void setCharacteristic(int c)
Definition: cf_char.cc:23
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
static number npNegM(number a, const coeffs r)
Definition: modulop.h:111
number npInversM(number c, const coeffs r)
Definition: modulop.cc:241
static number npSubM(number a, number b, const coeffs r)
Definition: modulop.h:82
static number npRandom(siRandProc p, number, number, const coeffs cf)
Definition: modulop.cc:495
poly res
Definition: myNF.cc:322
number npMapMachineInt(number from, const coeffs, const coeffs dst)
Definition: modulop.cc:760
BOOLEAN npGreater(number a, number b, const coeffs r)
Definition: modulop.cc:326
number nvDiv(number a, number b, const coeffs r)
Definition: modulop.cc:882
unsigned short * npLogTable
const ring r
Definition: syzextra.cc:208
BOOLEAN npIsMOne(number a, const coeffs r)
Definition: modulop.cc:186
Coefficient rings, fields and other domains suitable for Singular polynomials.
void npCoeffWrite(const coeffs r, BOOLEAN details)
Definition: modulop.cc:927
static FORCE_INLINE BOOLEAN nCoeff_is_CF(const coeffs r)
Definition: coeffs.h:914
int s_readint(s_buff F)
Definition: s_buff.cc:110
#define omFree(addr)
Definition: omAllocDecl.h:261
#define assume(x)
Definition: mod2.h:394
The main handler for Singular numbers which are suitable for Singular polynomials.
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
const ring R
Definition: DebugPrint.cc:36
BOOLEAN npGreaterZero(number k, const coeffs r)
Definition: modulop.cc:94
const int MAX_INT_VAL
Definition: mylimits.h:12
static const char * npEati(const char *s, int *i, const coeffs r)
Definition: modulop.cc:375
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:742
static number npAddM(number a, number b, const coeffs r)
Definition: modulop.h:77
All the auxiliary stuff.
const char *const nDivBy0
Definition: numbers.h:83
#define StringAppend
Definition: emacs.cc:82
int i
Definition: cfEzgcd.cc:123
nMapFunc npSetMap(const coeffs src, const coeffs dst)
Definition: modulop.cc:774
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
static number npMapLongR(number from, const coeffs, const coeffs dst_r)
Definition: modulop.cc:658
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:425
int(* siRandProc)()
Definition: sirandom.h:9
number npSub(number a, number b, const coeffs r)
Definition: modulop.cc:160
number npConvFactoryNSingN(const CanonicalForm n, const coeffs r)
Definition: modulop.cc:457
#define NV_MAX_PRIME
Definition: modulop.h:21
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
#define SR_TO_INT(SR)
Definition: longrat.h:70
(number), see longrat.h
Definition: coeffs.h:111
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static char * npCoeffString(const coeffs cf)
Definition: modulop.cc:477
n_coeffType
Definition: coeffs.h:27
CanonicalForm cf
Definition: cfModGcd.cc:4024
#define NULL
Definition: omList.c:10
#define ULONG64
(gmp_float), see
Definition: coeffs.h:117
number npNeg(number c, const coeffs r)
Definition: modulop.cc:309
#define SR_INT
Definition: longrat.h:68
const CanonicalForm & w
Definition: facAbsFact.cc:55
#define ALLOC_RNUMBER()
Definition: coeffs.h:87
number npMult(number a, number b, const coeffs r)
Definition: modulop.cc:110
CanonicalForm npConvSingNFactoryN(number n, BOOLEAN setChar, const coeffs r)
Definition: modulop.cc:450
static number npReadFd(s_buff f, const coeffs)
Definition: modulop.cc:487
static BOOLEAN npCoeffsEqual(const coeffs r, n_coeffType n, void *parameter)
Definition: modulop.cc:445
number nvInversM(number c, const coeffs r)
Definition: modulop.cc:876
(int), see modulop.h
Definition: coeffs.h:110
#define SR_HDL(A)
Definition: tgb.cc:35
void npKillChar(coeffs r)
Definition: modulop.cc:429
const char * npRead(const char *s, number *a, const coeffs r)
Definition: modulop.cc:395
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:85
const poly b
Definition: syzextra.cc:213
BOOLEAN npIsOne(number a, const coeffs r)
Definition: modulop.cc:179
number npMapGMP(number from, const coeffs, const coeffs dst)
Definition: modulop.cc:734
BOOLEAN npIsZero(number a, const coeffs r)
Definition: modulop.cc:172
#define omAlloc0(size)
Definition: omAllocDecl.h:211
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
static number nvMultM(number a, number b, const coeffs r)
Definition: modulop.cc:73
#define omStrDup(s)
Definition: omAllocDecl.h:263
number npMapCanonicalForm(number a, const coeffs, const coeffs dst)
Definition: modulop.cc:767