From 4e4efc9eff5c77a2ca19002b1dfa45598e974c54 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Mon, 18 Feb 2019 11:05:53 -0500 Subject: [PATCH] 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. --- mjo/polynomial.py | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/mjo/polynomial.py b/mjo/polynomial.py index c3fbf56..7414bdf 100644 --- 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() -- 2.44.2