__nonzero__ for polynomials and lcm

[GoogleCodeExporter]

 Adding __nonzero__ to UnivariatePolynomial one can use gcd and lcm for
polynomials. 
For example

x = Symbol('x')
poly = UnivariatePolynomial
p = poly([1, 1])**1000
p1 = poly([1, 2]) * p
p2 = poly([1, 3]) * p
p3 = gcd(p1, p2)
p4 = lcm(p1, p2)

lcm is faster as defined in the patch below (600x for the above example on
my computer)

Index: polynomials/univariate.py
===================================================================
--- polynomials/univariate.py   (revision 760)
+++ polynomials/univariate.py   (working copy)
@@ -165,6 +165,8 @@
         return self.__class__([c*(k+1) for k, c in enumerate(self.coefs[1:])],
             self.symbol, False)

+    def __nonzero__(self):
+        return bool(self.coefs)

 poly = UnivariatePolynomial

Index: arithmetic/__init__.py
===================================================================
--- arithmetic/__init__.py      (revision 760)
+++ arithmetic/__init__.py      (working copy)
@@ -1,4 +1,4 @@

 from .numbers import FractionTuple, Float, Complex
-from .number_theory import gcd, multinomial_coefficients
+from .number_theory import gcd, lcm, multinomial_coefficients
 from .infinity import Infinity
Index: arithmetic/number_theory.py
===================================================================
--- arithmetic/number_theory.py (revision 760)
+++ arithmetic/number_theory.py (working copy)
@@ -32,7 +32,7 @@
     L = len(args)
     if L == 0: return 0
     if L == 1: return args[0]
-    if L == 2: return div(args[0]*args[1], gcd(*args))
+    if L == 2: return div(args[0], gcd(*args))*args[1]
     return lcm(lcm(args[0], args[1]), *args[2:])

 # TODO: this could use the faster implementation in mpmath

Original issue reported on code.google.com by mario.pe...@gmail.com on 29 Feb 2008 at 10:29

[GoogleCodeExporter]

+1

By the way, gcd (and lcm?) could be sped up enormously for long lists of 
arguments by
starting to look for the smallest numbers, although this may be hard to 
implement
generically so it works both for numbers and polynomials.

Original comment by fredrik....@gmail.com on 29 Feb 2008 at 10:42

[GoogleCodeExporter]

The changes have been applied.

A simple test case or two would be nice.

Original comment by fredrik....@gmail.com on 29 Feb 2008 at 10:52

[GoogleCodeExporter]

Here are two simple tests.

p1 = poly([1, 2, 1])
p2 = poly([2, 3, 1])
q, r = divmod(gcd(p1, p2), poly([1,1]))
assert q.degree == 0 and not r
q, r = divmod(lcm(p1, p2), p1*poly([2,1]))
assert q.degree == 0 and not r

Original comment by mario.pe...@gmail.com on 3 Mar 2008 at 10:46

[GoogleCodeExporter]

Added. Thanks!

Original comment by fredrik....@gmail.com on 3 Mar 2008 at 1:37

• Changed state: Fixed