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* npCoeffString(const coeffs r)
471 {
472 #ifdef SINGULAR_4_1
473  char *s=(char*)omAlloc(14);
474  snprintf(s,14,"ZZ/%d",r->ch);
475 #else
476  char *s=(char*)omAlloc(11);
477  snprintf(s,11,"%d",r->ch);
478 #endif
479  return s;
480 }
481 
482 static void npWriteFd(number n, FILE* f, const coeffs r)
483 {
484  fprintf(f,"%d ",(int)(long)n);
485 }
486 
487 static number npReadFd(s_buff f, const coeffs r)
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 
521  r->cfMult = npMult;
522  r->cfSub = npSub;
523  r->cfAdd = npAdd;
524  r->cfDiv = npDiv;
525  r->cfInit = npInit;
526  //r->cfSize = ndSize;
527  r->cfInt = npInt;
528  #ifdef HAVE_RINGS
529  //r->cfDivComp = NULL; // only for ring stuff
530  //r->cfIsUnit = NULL; // only for ring stuff
531  //r->cfGetUnit = NULL; // only for ring stuff
532  //r->cfExtGcd = NULL; // only for ring stuff
533  // r->cfDivBy = NULL; // only for ring stuff
534  #endif
535  r->cfInpNeg = npNeg;
536  r->cfInvers= npInvers;
537  //r->cfCopy = ndCopy;
538  //r->cfRePart = ndCopy;
539  //r->cfImPart = ndReturn0;
540  r->cfWriteLong = npWrite;
541  r->cfRead = npRead;
542  //r->cfNormalize=ndNormalize;
543  r->cfGreater = npGreater;
544  r->cfEqual = npEqual;
545  r->cfIsZero = npIsZero;
546  r->cfIsOne = npIsOne;
547  r->cfIsMOne = npIsMOne;
548  r->cfGreaterZero = npGreaterZero;
549  //r->cfPower = npPower;
550  //r->cfGetDenom = ndGetDenom;
551  //r->cfGetNumerator = ndGetNumerator;
552  //r->cfGcd = ndGcd;
553  //r->cfLcm = ndGcd;
554  //r->cfDelete= ndDelete;
555  r->cfSetMap = npSetMap;
556  //r->cfName = ndName;
557  //r->cfInpMult=ndInpMult;
558 #ifdef NV_OPS
559  if (c>NV_MAX_PRIME)
560  {
561  r->cfMult = nvMult;
562  r->cfDiv = nvDiv;
563  r->cfExactDiv= nvDiv;
564  r->cfInvers= nvInvers;
565  //r->cfPower= nvPower;
566  }
567 #endif
568  r->cfCoeffWrite=npCoeffWrite;
569 #ifdef LDEBUG
570  // debug stuff
571  r->cfDBTest=npDBTest;
572 #endif
573 
574  r->convSingNFactoryN=npConvSingNFactoryN;
575  r->convFactoryNSingN=npConvFactoryNSingN;
576 
577  r->cfRandom=npRandom;
578 
579  // io via ssi
580  r->cfWriteFd=npWriteFd;
581  r->cfReadFd=npReadFd;
582 
583  // the variables:
584  r->nNULL = (number)0;
585  r->type = n_Zp;
586  r->ch = c;
587  r->has_simple_Alloc=TRUE;
588  r->has_simple_Inverse=TRUE;
589 
590  // the tables
591 #ifdef NV_OPS
592  if (r->ch <=NV_MAX_PRIME)
593 #endif
594  {
595 #if !defined(HAVE_DIV_MOD) || !defined(HAVE_MULT_MOD)
596  r->npExpTable=(unsigned short *)omAlloc( r->ch*sizeof(unsigned short) );
597  r->npLogTable=(unsigned short *)omAlloc( r->ch*sizeof(unsigned short) );
598  r->npExpTable[0] = 1;
599  r->npLogTable[0] = 0;
600  if (r->ch > 2)
601  {
602  w = 1;
603  loop
604  {
605  r->npLogTable[1] = 0;
606  w++;
607  i = 0;
608  loop
609  {
610  i++;
611  r->npExpTable[i] =(int)(((long)w * (long)r->npExpTable[i-1]) % r->ch);
612  r->npLogTable[r->npExpTable[i]] = i;
613  if /*(i == r->ch - 1 ) ||*/ (/*(*/ r->npExpTable[i] == 1 /*)*/)
614  break;
615  }
616  if (i == r->ch - 1)
617  break;
618  }
619  }
620  else
621  {
622  r->npExpTable[1] = 1;
623  r->npLogTable[1] = 0;
624  }
625 #endif
626 #ifdef HAVE_DIV_MOD
627  r->npInvTable=(unsigned short*)omAlloc0( r->ch*sizeof(unsigned short) );
628 #endif
629  }
630  return FALSE;
631 }
632 
633 #ifdef LDEBUG
634 BOOLEAN npDBTest (number a, const char *f, const int l, const coeffs r)
635 {
636  if (((long)a<0L) || ((long)a>(long)r->ch))
637  {
638  Print("wrong mod p number %ld at %s,%d\n",(long)a,f,l);
639  return FALSE;
640  }
641  return TRUE;
642 }
643 #endif
644 
645 number npMapP(number from, const coeffs src, const coeffs dst_r)
646 {
647  long i = (long)from;
648  if (i>src->ch/2)
649  {
650  i-=src->ch;
651  while (i < 0) i+=dst_r->ch;
652  }
653  i%=dst_r->ch;
654  return (number)i;
655 }
656 
657 static number npMapLongR(number from, const coeffs /*src*/, const coeffs dst_r)
658 {
659  gmp_float *ff=(gmp_float*)from;
660  mpf_t *f=ff->_mpfp();
661  number res;
662  mpz_ptr dest,ndest;
663  int size,i;
664  int e,al,bl;
665  long iz;
666  mp_ptr qp,dd,nn;
667 
668  size = (*f)[0]._mp_size;
669  if (size == 0)
670  return npInit(0,dst_r);
671  if(size<0)
672  size = -size;
673 
674  qp = (*f)[0]._mp_d;
675  while(qp[0]==0)
676  {
677  qp++;
678  size--;
679  }
680 
681  if(dst_r->ch>2)
682  e=(*f)[0]._mp_exp-size;
683  else
684  e=0;
685  res = ALLOC_RNUMBER();
686 #if defined(LDEBUG)
687  res->debug=123456;
688 #endif
689  dest = res->z;
690 
691  long in=0;
692  if (e<0)
693  {
694  al = dest->_mp_size = size;
695  if (al<2) al = 2;
696  dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
697  for (i=0;i<size;i++) dd[i] = qp[i];
698  bl = 1-e;
699  nn = (mp_ptr)omAlloc(sizeof(mp_limb_t)*bl);
700  nn[bl-1] = 1;
701  for (i=bl-2;i>=0;i--) nn[i] = 0;
702  ndest = res->n;
703  ndest->_mp_d = nn;
704  ndest->_mp_alloc = ndest->_mp_size = bl;
705  res->s = 0;
706  in=mpz_fdiv_ui(ndest,dst_r->ch);
707  mpz_clear(ndest);
708  }
709  else
710  {
711  al = dest->_mp_size = size+e;
712  if (al<2) al = 2;
713  dd = (mp_ptr)omAlloc(sizeof(mp_limb_t)*al);
714  for (i=0;i<size;i++) dd[i+e] = qp[i];
715  for (i=0;i<e;i++) dd[i] = 0;
716  res->s = 3;
717  }
718 
719  dest->_mp_d = dd;
720  dest->_mp_alloc = al;
721  iz=mpz_fdiv_ui(dest,dst_r->ch);
722  mpz_clear(dest);
723  if(res->s==0)
724  iz=(long)npDiv((number)iz,(number)in,dst_r);
725  FREE_RNUMBER(res); // Q!?
726  return (number)iz;
727 }
728 
729 #ifdef HAVE_RINGS
730 /*2
731 * convert from a GMP integer
732 */
733 number npMapGMP(number from, const coeffs /*src*/, const coeffs dst)
734 {
735  mpz_ptr erg = (mpz_ptr) omAlloc(sizeof(mpz_t)); // evtl. spaeter mit bin
736  mpz_init(erg);
737 
738  mpz_mod_ui(erg, (mpz_ptr) from, dst->ch);
739  number r = (number) mpz_get_si(erg);
740 
741  mpz_clear(erg);
742  omFree((void *) erg);
743  return (number) r;
744 }
745 
746 number npMapZ(number from, const coeffs src, const coeffs dst)
747 {
748  if (SR_HDL(from) & SR_INT)
749  {
750  long f_i=SR_TO_INT(from);
751  return npInit(f_i,dst);
752  }
753  return npMapGMP(from,src,dst);
754 }
755 
756 /*2
757 * convert from an machine long
758 */
759 number npMapMachineInt(number from, const coeffs /*src*/,const coeffs dst)
760 {
761  long i = (long) (((unsigned long) from) % dst->ch);
762  return (number) i;
763 }
764 #endif
765 
766 number npMapCanonicalForm (number a, const coeffs /*src*/, const coeffs dst)
767 {
768  setCharacteristic (dst ->ch);
770  return (number) (f.intval());
771 }
772 
773 nMapFunc npSetMap(const coeffs src, const coeffs dst)
774 {
775 #ifdef HAVE_RINGS
776  if ((src->rep==n_rep_int) && nCoeff_is_Ring_2toM(src))
777  {
778  return npMapMachineInt;
779  }
780  if (src->rep==n_rep_gmp) //nCoeff_is_Ring_Z(src) || nCoeff_is_Ring_PtoM(src) || nCoeff_is_Ring_ModN(src))
781  {
782  return npMapGMP;
783  }
784  if (src->rep==n_rep_gap_gmp) //nCoeff_is_Ring_Z(src)
785  {
786  return npMapZ;
787  }
788 #endif
789  if (src->rep==n_rep_gap_rat) /* Q, Z */
790  {
791  return nlModP; // npMap0; // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to Zp // FIXME!
792  }
793  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src) )
794  {
795  if (n_GetChar(src) == n_GetChar(dst))
796  {
797  return ndCopyMap;
798  }
799  else
800  {
801  return npMapP;
802  }
803  }
804  if ((src->rep==n_rep_gmp_float) && nCoeff_is_long_R(src))
805  {
806  return npMapLongR;
807  }
808  if (nCoeff_is_CF (src))
809  {
810  return npMapCanonicalForm;
811  }
812  return NULL; /* default */
813 }
814 
815 // -----------------------------------------------------------
816 // operation for very large primes (32749< p < 2^31-1)
817 // ----------------------------------------------------------
818 #ifdef NV_OPS
819 
820 number nvMult (number a,number b, const coeffs r)
821 {
822  //if (((long)a == 0) || ((long)b == 0))
823  // return (number)0;
824  //else
825  return nvMultM(a,b,r);
826 }
827 
828 void nvInpMult(number &a, number b, const coeffs r)
829 {
830  number n=nvMultM(a,b,r);
831  a=n;
832 }
833 
834 
835 inline long nvInvMod(long a, const coeffs R)
836 {
837 #ifdef HAVE_DIV_MOD
838  return InvMod(a, R);
839 #else
840 /// TODO: use "long InvMod(long a, const coeffs R)"?!
841 
842  long s;
843 
844  long u, u0, u1, u2, q, r; // v0, v1, v2,
845 
846  u1=1; // v1=0;
847  u2=0; // v2=1;
848  u = a;
849 
850  long v = R->ch;
851 
852  while (v != 0)
853  {
854  q = u / v;
855  r = u % v;
856  u = v;
857  v = r;
858  u0 = u2;
859 // v0 = v2;
860  u2 = u1 - q*u2;
861 // v2 = v1 - q*v2;
862  u1 = u0;
863 // v1 = v0;
864  }
865 
866  s = u1;
867  //t = v1;
868  if (s < 0)
869  return s + R->ch;
870  else
871  return s;
872 #endif
873 }
874 
875 inline number nvInversM (number c, const coeffs r)
876 {
877  long inv=nvInvMod((long)c,r);
878  return (number)inv;
879 }
880 
881 number nvDiv (number a,number b, const coeffs r)
882 {
883  if ((long)a==0L)
884  return (number)0L;
885  else if ((long)b==0L)
886  {
887  WerrorS(nDivBy0);
888  return (number)0L;
889  }
890  else
891  {
892  number inv=nvInversM(b,r);
893  return nvMultM(a,inv,r);
894  }
895 }
896 number nvInvers (number c, const coeffs r)
897 {
898  if ((long)c==0L)
899  {
900  WerrorS(nDivBy0);
901  return (number)0L;
902  }
903  return nvInversM(c,r);
904 }
905 #if 0
906 void nvPower (number a, int i, number * result, const coeffs r)
907 {
908  if (i==0)
909  {
910  //npInit(1,result);
911  *(long *)result = 1;
912  }
913  else if (i==1)
914  {
915  *result = a;
916  }
917  else
918  {
919  nvPower(a,i-1,result,r);
920  *result = nvMultM(a,*result,r);
921  }
922 }
923 #endif
924 #endif
925 
926 void npCoeffWrite (const coeffs r, BOOLEAN /*details*/)
927 {
928  Print("// characteristic : %d\n",r->ch);
929 }
930 
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
if(0 > strat->sl)
Definition: myNF.cc:73
#define FALSE
Definition: auxiliary.h:97
number npMapZ(number from, const coeffs src, const coeffs dst)
Definition: modulop.cc:746
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:896
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:239
bool isImm() const
static FORCE_INLINE BOOLEAN nCoeff_is_long_R(const coeffs r)
Definition: coeffs.h:905
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
number nvMult(number a, number b, const coeffs r)
Definition: modulop.cc:820
long nvInvMod(long a, const coeffs R)
Definition: modulop.cc:835
#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:828
number npMapP(number from, const coeffs src, const coeffs r)
Definition: modulop.cc:645
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:101
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
static number npReadFd(s_buff f, const coeffs r)
Definition: modulop.cc:487
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:634
void setCharacteristic(int c)
Definition: cf_char.cc:23
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
static void npWriteFd(number n, FILE *f, const coeffs r)
Definition: modulop.cc:482
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:759
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:881
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:926
static FORCE_INLINE BOOLEAN nCoeff_is_CF(const coeffs r)
Definition: coeffs.h:911
int s_readint(s_buff F)
Definition: s_buff.cc:119
#define omFree(addr)
Definition: omAllocDecl.h:261
#define assume(x)
Definition: mod2.h:403
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
number nlModP(number q, const coeffs Q, const coeffs Zp)
Definition: longrat.cc:1423
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
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
nMapFunc npSetMap(const coeffs src, const coeffs dst)
Definition: modulop.cc:773
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
static number npMapLongR(number from, const coeffs, const coeffs dst_r)
Definition: modulop.cc:657
static char * npCoeffString(const coeffs r)
Definition: modulop.cc:470
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
n_coeffType
Definition: coeffs.h:27
CanonicalForm cf
Definition: cfModGcd.cc:4024
unsigned long InvMod(unsigned long a, const coeffs r)
Definition: rmodulo2m.cc:531
#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 BOOLEAN npCoeffsEqual(const coeffs r, n_coeffType n, void *parameter)
Definition: modulop.cc:445
number nvInversM(number c, const coeffs r)
Definition: modulop.cc:875
(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:88
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:733
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
number npMapCanonicalForm(number a, const coeffs, const coeffs dst)
Definition: modulop.cc:766