Changeset 5eeb4f in git

Timestamp:

Apr 18, 2018, 6:42:01 PM (5 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')

Children:

65c1bd5b526a9447123bf85f32538aff3498501c

Parents:

83789eef751cc6cbd6f5106c113ccb43c6af36b0

Message:

opt: Z/p arithmetic revisited

Files:

• factory/ffops.h (modified) (1 diff)
• libpolys/coeffs/modulop.cc (modified) (8 diffs)

factory/ffops.h

@@ -53 +53 @@
     long n = a % ff_prime;
 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
+    #if SIZEOF_LONG==8
+    n += (n >> 63) & ff_prime;
+    #else
     n += (n >> 31) & ff_prime;
+    #endif
     return n;
 #else

libpolys/coeffs/modulop.cc

@@ -170 +170 @@
 static inline long InvMod(long a, const coeffs R)
 {
-   long d, s, t;
+   long s, t;
 
 #ifdef USE_NTL_XGCD
+   long d;
    XGCD(d, s, t, a, R->ch);
    assume (d == 1);
@@ -185 +186 @@
    {
       q = u / v;
-      r = u % v;
+      //r = u % v;
+      r = u - q*v;
       u = v;
       v = r;
@@ -196 +198 @@
    s = u1;
 #endif
+#ifdef HAVE_GENERIC_ADD
    if (s < 0)
       return s + R->ch;
    else
       return s;
+#else
+  #if SIZEOF_LONG == 8
+  s += (s >> 63) & R->ch;
+  #else
+  s += (s >> 31) & R->ch;
+  #endif
+#endif
 }
 #endif
@@ -206 +216 @@
 {
   n_Test(c, r);
-#ifndef HAVE_DIV_MOD
+#if !defined(HAVE_MULT_MOD) && (!defined(HAVE_DIV_MOD))
   number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
 #else
@@ -212 +222 @@
   if (inv==0)
   {
+    #ifndef HAVE_MULT_MOD
+    inv = (long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
+    #else
     inv=InvMod((long)c,r);
+    #endif
     r->npInvTable[(long)c]=inv;
   }
@@ -219 +233 @@
   n_Test(d, r);
   return d;
-
 }
 
@@ -227 +240 @@
   n_Test(b, r);
 
-//#ifdef NV_OPS
-//  if (r->ch>NV_MAX_PRIME)
-//    return nvDiv(a,b);
-//#endif
-  if ((long)a==0L)
-    return (number)0L;
-  number d;
-
-#ifndef HAVE_DIV_MOD
   if ((long)b==0L)
   {
@@ -241 +245 @@
     return (number)0L;
   }
-
+  if ((long)a==0) return (number)0L;
+
+  number d;
+#ifndef HAVE_DIV_MOD
   int s = r->npLogTable[(long)a] - r->npLogTable[(long)b];
   if (s < 0)