Changeset 146c603 in git for libpolys/coeffs/longrat.cc

Timestamp:

Nov 9, 2011, 10:13:02 AM (12 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', 'd0474371d8c5d8068ab70bfb42719c97936b18a6')

Children:

8f40312428677d88ab37a31824f2ec53f144a18a

Parents:

fc497757365979d0168460de9969b49bc49c53f2

git-author:

Hans Schoenemann <hannes@mathematik.uni-kl.de>2011-11-09 10:13:02+01:00

git-committer:

Mohamed Barakat <mohamed.barakat@rwth-aachen.de>2011-11-09 16:14:12+01:00

Message:

fix: nlModP (should not use nvDiv/npDiv
implement conversion to/from factory for algext

File:

• libpolys/coeffs/longrat.cc (modified) (1 diff)

libpolys/coeffs/longrat.cc

@@ -1268 +1268 @@
   {
     int in=mpz_fdiv_ui(n->n,(unsigned long)p);
-    #ifdef NV_OPS
-    if (p>NV_MAX_PRIME)
-    return (int)((long)nvDiv((number)iz,(number)in,(const coeffs)r));
-    #endif
-    return (int)((long)npDiv((number)iz,(number)in,(const coeffs)r));
+    long  s, t;
+
+    long  u, v, u0, v0, u1, v1, u2, v2, q, r;
+
+     u1=1; v1=0;
+     u2=0; v2=1;
+     u = in; v = p;
+
+     while (v != 0)
+     {
+        q = u / v;
+        r = u % v;
+        u = v;
+        v = r;
+        u0 = u2;
+        v0 = v2;
+        u2 =  u1 - q*u2;
+        v2 = v1- q*v2;
+        u1 = u0;
+        v1 = v0;
+     }
+
+     s = u1;
+     if (s < 0) s+=p;
+     u=(s*((long)iz)) % ((long)p);
+     return (int)u;
   }
   return iz;