Python -- special method arithmetic using existing class methods
Question: This class takes a finite field polynomial string, parses it, operates
(+-*/%), then outputs in the same format as the input. It works fine (so far).
However, now I'm trying to implement special methods on the arithmetic
operators, and I can't get it past the point of simply concatenating the
strings. Generally, the idea is to initialize the input into a class instance,
but in this case there is a regex on input that seems to complicate any
attempts to do this. I'm teaching myself Python so this is a horror movie for
me, but probably just a toy for any seasoned Python programmer.

These seem to have a lot of info, but I'm not sure how much they're helpful in
this situation:

    
    
    http://stackoverflow.com/questions/10842166/programmatically-create-arithmetic-special-methods-in-python-aka-factory-funct
    http://rosettacode.org/wiki/S-Expressions
    http://www.greenteapress.com/thinkpython/thinkCSpy/html/chap14.html
    http://docs.cython.org/src/userguide/special_methods.html
    

Here's the class and the examples I'm using:

    
    
    import re
    
    class gf2pim:
    
    def id(self,lst):
        """returns modulus 2 (1,0,0,1,1,....) for input lists"""
        return [int(lst[i])%2 for i in range(len(lst))]
    
    def listToInt(self,lst):
        """converts list to integer for later use"""
        result = self.id(lst)
        return int(''.join(map(str,result)))
    
    def parsePolyToListInput(self,poly):
        """performs regex on raw string and converts to list"""
        c = [int(i.group(0)) for i in re.finditer(r'\d+', poly)]
        return [1 if x in c else 0  for x in xrange(max(c), -1, -1)]
    
    def prepBinary(self,x,y):
        """converts to base 2; bina,binb are binary values like 110100101100....."""
        x = self.parsePolyToListInput(x); y = self.parsePolyToListInput(y)
        a = self.listToInt(x); b = self.listToInt(y)
        bina = int(str(a),2); binb = int(str(b),2)
        return bina,binb  #
    
    def add(self,a,b):
        """a,b are GF(2) polynomials like x**7 + x**3 + x**0 ...; returns binary string"""
        bina,binb = self.prepBinary(a,b)
        return self.outFormat(bina^binb)
    
    def subtract(self,x,y):
        """same as addition in GF(2)"""
        return self.add(x,y)
    
    def quotient(self,a,b):
        """a,b are GF(2) polynomials like x**7 + x**3 + x**0 ...; returns quotient formatted as polynomial"""
        a,b = self.prepBinary(a,b)
        return self.outFormat(a/b)
    
    def remainder(self,a,b):
        """a,b are GF(2) polynomials like x**7 + x**3 + x**0 ...; returns remainder formatted as polynomial"""
        a,b = self.prepBinary(a,b)
        return self.outFormat(a%b)
    
    def outFormat(self,raw):
        """process resulting values into polynomial format"""
        raw = "{0:b}".format(raw); raw = str(raw[::-1]); g = [] #reverse binary string for enumeration
        g = [i for i,c in enumerate(raw) if c == '1']
        processed = "x**"+" + x**".join(map(str, g[::-1]))
        if len(g) == 0: return 0 #return 0 if list empty
        return processed  #returns result in gf(2) polynomial form
    
    def __add__(self,other):
        return gf2pim.add(self,other)
    

The last example at the bottom shows the problem:

    
    
    obj = gf2pim()
    a = "x**14 + x**1 + x**0"; b = "x**6 + x**2 + x**1"
    c = "x**2 + x**1 + x**0"; d = "x**3 + x**1 + x**0"
    e = "x**3 + x**2 + x**1 + x**0"; f = "x**2"; g = "x**1 + x**0"; h = "x**3 + x**2 + x**0"
    p = "x**13 + x**1 + x**0"; q = "x**12 + x**1"; j = "x**4 + x**3 + x**1 + x**0"
    print "add: [%s] + [%s]  =  %s "%(a,b,obj.add(a,b))
    print "add: [%s] + [%s]  =  %s "%(c,d,obj.add(c,d))
    print "quotient (max(a,b)/min(a,b): [%s] / [%s]  =  %s "%(a,b,obj.quotient(a,b))
    print "remainder (max(a,b) mod min(a,b)): [%s] mod [%s]  =  %s "%(a,b,obj.remainder(a,b))
    print "quotient (max(a,b)/min(a,b): [%s] / [%s]  =  %s "%(c,d,obj.quotient(c,d))
    print "remainder (max(a,b) mod min(a,b): [%s] mod [%s]  =  %s "%(c,d,obj.remainder(c,d))
    print "quotient (max(a,b)/min(a,b): [%s] / [%s]  =  %s "%(q,q,obj.quotient(q,q))
    print "remainder (max(a,b) mod min(a,b): [%s] mod [%s]  =  %s "%(q,q,obj.remainder(q,q))
    print "modular_inverse: [%s] * [%s] mod [%s] = 1  [%s]"%(p,valuemi2[0],q,valuemi2[1])
    sum1 = obj.add(a,b); quotient1 = obj.quotient(sum1,c)
    
    ### HERE THE PROBLEM IS CLEAR
    print "[(a+b)/c] = ",quotient1
    smadd1 = a+b
    print "smadd1   ",smadd1
    

And the output:

    
    
    >>> 
    add: [x**14 + x**1 + x**0] + [x**6 + x**2 + x**1]  =  x**14 + x**6 + x**2 + x**0 
    add: [x**2 + x**1 + x**0] + [x**3 + x**1 + x**0]  =  x**3 + x**2 
    quotient (max(a,b)/min(a,b): [x**14 + x**1 + x**0] / [x**6 + x**2 + x**1]  =  x**7 + x**6 + x**5 + x**3 + x**1 
    remainder (max(a,b) mod min(a,b)): [x**14 + x**1 + x**0] mod [x**6 + x**2 + x**1]  =  x**2 + x**1 + x**0 
    quotient (max(a,b)/min(a,b): [x**2 + x**1 + x**0] / [x**3 + x**1 + x**0]  =  0 
    remainder (max(a,b) mod min(a,b): [x**2 + x**1 + x**0] mod [x**3 + x**1 + x**0]  =  x**2 + x**1 + x**0 
    quotient (max(a,b)/min(a,b): [x**12 + x**1] / [x**12 + x**1]  =  x**0 
    remainder (max(a,b) mod min(a,b): [x**12 + x**1] mod [x**12 + x**1]  =  0 
    [(a+b)/c]*d =  x**14 + x**12 + x**9 + x**1
    smadd1    x**14 + x**1 + x**0x**6 + x**2 + x**1
    >>> 
    

So as you can see by `smadd1` I need to add these 2 using + and not just
concatenate. Also, I'd like to know if I'll need to use an S-expression tree
in this situation.

EDIT:

Multiply() that was working but isn't now:

    
    
    def __mul__(self,other):
        """
        __multiply__ is the special method for overriding the - operator
        returns product of 2 polynomials in gf2; self,other are values 10110011...
        """
        self = int(str(self),2)
        bitsa = reversed("{0:b}".format(self))
        g = [(other<<i)*int(bit) for i,bit in enumerate(bitsa)]
        return gf2infix(self.outFormat(reduce(lambda x,y: x^y,g)))
    

It's original form was:

    
    
    def multiply(self,a,b):
        """a,b are GF(2) polynomials like x**7 + x**3 + x**0... ; returns product of 2 polynomials in gf2"""
        a = self.prepBinary(a); b = self.prepBinary(b)
        bitsa = reversed("{0:b}".format(a))
        g = [(b<<i)*int(bit) for i,bit in enumerate(bitsa)]
        return self.outFormat(reduce(lambda x,y: x^y,g))
    

* * *

Disregard that issue with `multiply()`, I fixed it. The line that was changed
was:

    
    
    bitsa = reversed("{0:b}".format(self.bin))
    

and the line before that was taken out.


Answer: It looks like you are confusing two concepts: strings that represent finite
field polynomials and objects of the class gf2pim, which also represents
finite field polynomials. You should instantiate a gf2pim object for each
polynomial you wish to manipulate, and the operations on gf2pim objects should
return other gf2pim objects. Currently you are trying to use the + operator on
2 strings, which is why your `__add__` method is not being called. There are
also several other problems with your definition of the gf2pim class. I've
refactored your code a bit below, although it is still not perfect. I also
left out the division methods, but I think what I did should get you on the
right track. See section 3.4.8 of this
[link](http://docs.python.org/2/reference/datamodel.html) for more special
method names for operator overloading.

    
    
    import re
    class gf2pim(object):#Your classes should generally inherit from object
    
    
        def __init__(self, binary):
            '''__init__ is a standard special method used to initialize objects.  Here __init__
            will initialize a gf2pim object based on a binary representation.'''
            self.bin = binary
    
        @classmethod
        def from_string(cls, string):
            return cls(cls._string_to_binary(string))
    
        def to_string(self):
            raw = "{0:b}".format(self.bin); raw = str(raw[::-1]); g = [] #reverse binary string for enumeration
            g = [i for i,c in enumerate(raw) if c == '1']
            processed = "x**"+" + x**".join(map(str, g[::-1]))
            if len(g) == 0: return 0 #return 0 if list empty
            return processed  #returns result in gf(2) polynomial form
    
        @classmethod
        def id(cls, lst):
            """returns modulus 2 (1,0,0,1,1,....) for input lists"""
            return [int(lst[i])%2 for i in range(len(lst))]
    
        @classmethod
        def _list_to_int(self, lst):
            """converts list to integer for later use"""
            result = self.id(lst)
            return int(''.join(map(str,result)))
    
        @classmethod
        def _string_to_list(cls, string):
            """performs regex on raw string and converts to list"""
            c = [int(i.group(0)) for i in re.finditer(r'\d+', string)]
            return [1 if x in c else 0  for x in xrange(max(c), -1, -1)]
    
        @classmethod
        def _string_to_binary(cls, string):
            """converts to base 2; bina,binb are binary values like 110100101100....."""
            x = cls._string_to_list(string)
            a = cls._list_to_int(x)
            bina = int(str(a),2)
            return bina  #
    
        def __add__(self,other):
            """
            __add__ is another special method, and is used to override the + operator.  This will only 
            work for instances of gf2pim and its subclasses.
    
            a,b are GF(2) polynomials like x**7 + x**3 + x**0 ...; returns binary string"""
            return gf2pim(self.bin^other.bin)
    
        def __sub__(self,other):
            """
            __sub__ is the special method for overriding the - operator
    
            same as addition in GF(2)"""
            return self.add(other)
    
        def __str__(self):
            return self.to_string()
    
    if __name__ == '__main__':
        a = gf2pim.from_string("x**14 + x**1 + x**0")
        b = gf2pim.from_string("x**6 + x**2 + x**1")
        smadd1 = a+b
        print "smadd1   ",smadd1        
    

