[Edu-sig] Algebra + Python

[Seth David Schoen]

Seth David Schoen writes:

> Kirby Urner writes:
> 
> > Could this be extended to a symbolic math implementation?  At least,
> > could you implement compose, add, subtract, multiply, and divide methods
> > so that
> > 
> > f.compose(g)
> > f.add(g)
> > 
> > would work?
> > 
> > ============
> > 
> > Sure.
> > 
> > Compose was already implied in Brent's class, since f(10) returns
> > a number, and therefore so does g(f(10)) and g(f(10)).
> 
> I was interested in having a polynomial returned explicitly, not just
> making a function that would have the same effect as composition.  You
> could say I was hoping for a closed form.
> 
> To implement that, I guess you'd want an exponentiation operator for
> polynomials (implement __pow__).
>
> [...]
> 
> I quickly noticed that you can't multiply a Poly by an integer, or add
> or subtract an integer.  I think one approach would be to throw an
> 
> if type(other)==type(3):
> 	other = Poly([other])
> 
> at the start of __add__ and __mul__.  That worked for me, so that I
> could multiply a Poly by an integer or add or subtract an integer.
> 
> You also might want to define __rmul__, __rsub__, and __radd__ in
> terms of __mul__, __sub__, and __add__ (polynomial multiplication
> and addition being commutative).

OK, I implemented __pow__, compose, __rmul__, __rsub__, and __radd__.
The implementation of __pow__ does not take advantage of the binomial
theorem or its higher-order generalizations, mostly because I don't
know the higher-order generalizations.

I also did the type check thing so that integer constants are
automatically converted to polynomials where appropriate.  That means
it would be possible to implement __neg__ as "return self * -1".

(This version gets rid of list comprehensions, +=, and -=, so it will
run under 1.5.2.)

http://www.loyalty.org/~schoen/polynomial.py

>>> q = Poly([1,1])
>>> q
x + 1
>>> q ** 2
x**2 + 2*x + 1
>>> q ** 3
x**3 + 3*x**2 + 3*x + 1
>>> q - 1
x
>>> 1 - q
-x
>>> q * 2
2*x + 2
>>> 2 * q
2*x + 2
>>> 

It seems that it would be helpful to store the coefficients in reverse
order.  Then you could do

for exponent in range(len(self.coeffs)):
	coeff = self.coeffs[exponent]
	# Some code that uses exponent and coeff goes here

rather than counting down.

-- 
Seth David Schoen <schoen@loyalty.org>  | And do not say, I will study when I
Temp.  http://www.loyalty.org/~schoen/  | have leisure; for perhaps you will
down:  http://www.loyalty.org/   (CAF)  | not have leisure.  -- Pirke Avot 2:5