What's up with this code?

[Gerard Flanagan]

Gregory Petrosyan wrote:
> Hello, it's me again.
> I am trying to optimise small module for working with polynomials, and
> I have encountered problem: new, optimised, code, doesn't work in some
> specific case. Here's the old version of the code:
>
> (3x^2 + 2x + 1  <=>  poly([3, 2, 1]), btw)
>
>     def __add__(self, other):
>         "Return sum of two polynomials"
>         rcoefs1 = list(reversed(self.coefs))
>         rcoefs2 = list(reversed(other.coefs))
>         coefs = [c1+c2 for c1,c2 in zip(rcoefs1, rcoefs2)]
>         minlen = min(len(rcoefs1), len(rcoefs2))
>         coefs.extend(rcoefs1[minlen:] + rcoefs2[minlen:])
>         return Polynomial(reversed(coefs))
>

Gregory

It seems that zip/izip will only generate values while all of the
iterable parameters have values, eg. if rcoefs1 has length 3 and
rcoefs2 has length 5, zip will have length 3.  This is the point of the
lines

         minlen = min(len(rcoefs1), len(rcoefs2))
         coefs.extend(rcoefs1[minlen:] + rcoefs2[minlen:])

in the old code - to pad out 'coefs' with the unused values in the
longer 'rcoef'.  I think that's the source of the results you're
getting.

Here's an interactive session:

>>> import itertools as it
>>> a = [1,2,3]
>>> b = [0,0,0,4,5]
>>> c = [ alpha+beta for alpha,beta in it.izip(a,b) ]
>>> c
[1, 2, 3]
>>> inf = min( len(a), len(b) )
>>> inf
3
>>> a[inf:]
[]
>>> b[inf:]
[4, 5]
>>> c.extend( a[inf:] + b[inf:] )
>>> c
[1, 2, 3, 4, 5]

[...]

> Here's the new version:
>
>     def __add__(self, other):
>         rcoefs1 = reversed(self.coefs)
>         rcoefs2 = reversed(other.coefs)
>         coefs = [c1+c2 for c1,c2 in it.izip(rcoefs1, rcoefs2)]
>         coefs.extend(it.chain(rcoefs1, rcoefs2)) #? -- here is magic
>         if coefs[-1] != 0:
>             return Polynomial(reversed(coefs), False, False)
>         else:
>             return Polynomial(reversed(coefs), False)
>
> Last four lines are ok (tested), "magic" seems to occure in #? line.
> What's the magic? Here it is:
>
> poly([1,2,1]) + poly([1,-2,1]) is ok,
> poly([1,-2,1]) + poly([5,4,3,2,1]) is ok,
> poly([1]) + poly([2]) is ok,
> poly([1,2,1]) + poly([5,4,3,2,1]) is ok, but
>
> poly([1,0]) + poly([-1])  gives poly([-1]),
> poly([1,-3]) + poly([-2]) gives poly([-5]) etc.
>
> So, "magic" happens when processing something like poly([a,b]) +
> poly([c]) and it gives poly([b+c]) as result. Can anybody help me with
> it?
>
> Regards, Gregory.


I don't really understand your "magic" line.

Here's some code I was playing about with, it pads the shorter
coefficient list *before* applying izip - nothing distinguished about
it, but maybe instructive as a comparison to what you've got.

import itertools as it

class Polynomial(object):
    def __init__(self, *coeffs):
        self.coefs = list(coeffs)
        #print self.coefs

    def __add__(self, other):
        rcoefs1 = self.coefs[:]
        rcoefs2 = other.coefs[:]
        d1 = len(rcoefs1)
        d2 = len(rcoefs2)
        sup = max( d1, d2 )
        #pad the shorter of the two lists with zeros
        #so that it is the same length as the other
        rcoefs1 += [0] * (sup - d1)
        rcoefs2 += [0] * (sup - d2)
        coefs = [c1+c2 for c1,c2 in it.izip(rcoefs1, rcoefs2 )]
        return Polynomial(*coefs)

    def __str__(self):
        return str(tuple(self.coefs))

print
print Polynomial(1,2,1) + Polynomial(1,-2,1)
a = Polynomial(1,-2,1)
b = Polynomial(5,4,3,2,1)
c = a+b
print a
print b
print c
print Polynomial(1) + Polynomial(2)
print Polynomial(1,0) + Polynomial(-1)
print Polynomial(1,-3) + Polynomial(-2)

Gerard