mjo/polynomial.py: improve multidiv performance a bit.

We don't need to re-check earlier "denominators" after division has
occurred, even though we *do* need to re-check the current one. This
makes the algorithm closer in practice to the one given in the text.

diff --git a/mjo/polynomial.py b/mjo/polynomial.py
index c3fbf56a475f7f1ee75fecc4c6d63fae16196f68..7414bdf16b33e8178c746a3edf5b6fa4dd3f985b 100644 (file)
--- a/mjo/polynomial.py
+++ b/mjo/polynomial.py
@@ -116,8 +116,9 @@ def multidiv(f, gs):
     qs = [R.zero()]*s
 
     while p != R.zero():
-        for i in range(0,s):
-            division_occurred = false
+        i = 0
+        division_occurred = false
+        while i < s:
             # If gs[i].lt() divides p.lt(), then this remainder will
             # be zero and the quotient will be in R (and not the
             # fraction ring, which is important).
@@ -126,7 +127,13 @@ def multidiv(f, gs):
                 qs[i] += factor
                 p -= factor*gs[i]
                 division_occurred = true
-                break
+                # Don't increment "i" here because we want to try
+                # again with this "denominator" g[i]. We might
+                # get another factor out of it, but we know that
+                # we can't get another factor out of an *earlier*
+                # denominator g[i-k] for some k.
+            else:
+                i += 1
 
         if not division_occurred:
             r += p.lt()