Changeset 3426de2 in git

Timestamp:

Sep 6, 2011, 3:08:38 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'cdfcdb8287f66bc6070028082cbbc6eff10e609b')

Children:

725e6002e0b07ad1474e14f72296c0c85a47ae4d

Parents:

96f9fdfab406c4f1b69b407c26a25d199352b8c5

Message:

optimizations for division with remainder and lattice recombination


git-svn-id: file:///usr/local/Singular/svn/trunk@14380 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

factory

Files:

• facFqBivar.cc (modified) (5 diffs)
• facHensel.cc (modified) (4 diffs)

factory/facFqBivar.cc

@@ -1455 +1455 @@
           break;
         }
-        if (isReduced (NTLN))
+        if (isReduced (NTLN) && l > (minBound+1)*2)
         {
           reduced= true;
@@ -1514 +1514 @@
   if (start > l)
     l= start;
+  int startl= l;
   int oldL= l/2;
   bool reduced= false;
@@ -1629 +1630 @@
           break;
         }
-        if (isReduced (NTLN))
+        if (isReduced (NTLN) && l > startl)
         {
           reduced= true;
@@ -1742 +1743 @@
           break;
         }
-        if (isReduced (NTLN))
+        if (isReduced (NTLN) && l > (minBound+1)*2)
         {
           reduced= true;
@@ -1855 +1856 @@
           break;
         }
-        if (isReduced (NTLN))
+        if (isReduced (NTLN) && l > (minBound+1)*2)
         {
           reduced= true;

factory/facHensel.cc

@@ -1380 +1380 @@
     return 0;
 
+  Variable v;
   CanonicalForm Q;
   if (degB <= 1 || CFFactory::gettype() == GaloisFieldDomain)
@@ -1388 +1389 @@
   else
   {
-    CanonicalForm R= reverse (A, degA);
-    CanonicalForm revB= reverse (B, degB);
-    revB= newtonInverse (revB, m + 1, M);
-    Q= mulMod2 (R, revB, M);
-    Q= mod (Q, power (x, m + 1));
-    Q= reverse (Q, m);
+    if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
+    {
+      CanonicalForm R= reverse (A, degA);
+      CanonicalForm revB= reverse (B, degB);
+      revB= newtonInverse (revB, m + 1, M);
+      Q= mulMod2 (R, revB, M);
+      Q= mod (Q, power (x, m + 1));
+      Q= reverse (Q, m);
+    }
+    else
+    {
+      zz_pX mipo= convertFacCF2NTLzzpX (M);
+      Variable y= Variable (2);
+      zz_pEX NTLA, NTLB;
+      NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
+      NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
+      div (NTLA, NTLA, NTLB);
+      Q= convertNTLzz_pEX2CF (NTLA, x, y);
+    }
   }
 
@@ -1417 +1431 @@
   }
 
+  Variable v;
   if (degB <= 1 || CFFactory::gettype() == GaloisFieldDomain)
   {
@@ -1423 +1438 @@
   else
   {
-    R= reverse (A, degA);
-
-    CanonicalForm revB= reverse (B, degB);
-    revB= newtonInverse (revB, m + 1, M);
-    Q= mulMod2 (R, revB, M);
-
-    Q= mod (Q, power (x, m + 1));
-    Q= reverse (Q, m);
-
-    R= A - mulMod2 (Q, B, M);
+    if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
+    {
+      R= reverse (A, degA);
+
+      CanonicalForm revB= reverse (B, degB);
+      revB= newtonInverse (revB, m + 1, M);
+      Q= mulMod2 (R, revB, M);
+
+      Q= mod (Q, power (x, m + 1));
+      Q= reverse (Q, m);
+
+      R= A - mulMod2 (Q, B, M);
+    }
+    else
+    {
+      zz_pX mipo= convertFacCF2NTLzzpX (M);
+      Variable y= Variable (2);
+      zz_pEX NTLA, NTLB;
+      NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
+      NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
+      zz_pEX NTLQ, NTLR;
+      DivRem (NTLQ, NTLR, NTLA, NTLB);
+      Q= convertNTLzz_pEX2CF (NTLQ, x, y);
+      R= convertNTLzz_pEX2CF (NTLR, x, y);
+    }
   }
 }