Changeset 1e5c50 in git for factory/algext.cc

Timestamp:

Nov 12, 2012, 6:21:05 PM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')

Children:

f6237dd32a31b0c8c58f56d6a808bda992e743fa

Parents:

6ea864278bd3cbb9e4869b30bd2abcd525d6ed30

git-author:

Martin Lee <martinlee84@web.de>2012-11-12 18:21:05+01:00

git-committer:

Martin Lee <martinlee84@web.de>2012-11-16 13:20:45+01:00

Message:

chg: faster divisibility test in univariate case in QGCD
chg: added newtonDivrem to header

File:

• factory/algext.cc (modified) (2 diffs)

factory/algext.cc

@@ -26 +26 @@
 #include "cf_map.h"
 #include "cf_generator.h"
+#include "facMul.h"
 
 #ifdef HAVE_NTL
@@ -821 +822 @@
         equal= true; // modular image did not add any new information
       TIMING_START (alg_termination)
+#ifdef HAVE_FLINT
+      if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
+          && f.level() == tmp.level() && tmp.level() == g.level())
+      {
+        CanonicalForm Q, R, sf, sg, stmp;
+        Variable x= Variable (1);
+        sf= swapvar (f, f.mvar(), x);
+        sg= swapvar (g, f.mvar(), x);
+        stmp= swapvar (tmp, f.mvar(), x);
+        newtonDivrem (sf, stmp, Q, R);
+        if (R.isZero())
+        {
+          newtonDivrem (sg, stmp, Q, R);
+          if (R.isZero())
+          {
+            Off (SW_RATIONAL);
+            setReduce (a,true);
+            if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
+            TIMING_END_AND_PRINT (alg_termination,
+                                 "time for successful termination test in alg gcd: ")
+            return tmp*gcdcfcg;
+          }
+        }
+      }
+      else
+#endif
       if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
       {