Python — polynomial operations class

This Python class takes a GF2 (finite field mod 2, basically binary) polynomial in string form, converts it to a binary value, then does arithmetic operations, then converts the result back into a polynomial in string form.

There are 2 parts I'd like to direct your attention to. I'll call them exhibits a and b.

For exhibit a, the regex has to be done on the string upon intake, so there were some issues with how class instances were used in terms of still allowing the string format. So that's the reason why the class is being called at the bottom. That should be invisible to the user (unless they actually go looking in the file), and when they call the class in whatever file is being used, then it should just be another class and they go on about their business. Not saying it's good coding, just saying why it looks like that. I'm sure it looks duck-taped from the professional Python coder's perspective, but for me I was pretty glad to solve it any way possible.

Also somewhat duck-taped was the modular inverse function, which I'll give as exhibit b.

I'm teaching myself Python and trying to drop all my beginner bad habits quickly. Just trying to get some good advice on the code.

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 = obj.id(lst)
return int(''.join(map(str,result)))

def parsePolyToListInput(self,poly):
c = [int(i.group(0)) for i in re.finditer(r'\d+', poly)] #re.finditer returns an iterator
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 and orders min and max for use
x = obj.parsePolyToListInput(x); y = obj.parsePolyToListInput(y)
a = obj.listToInt(x); b = obj.listToInt(y)
bina = int(str(a),2); binb = int(str(b),2)
#a = min(bina,binb); b = max(bina,binb);
return bina,binb  #bina,binb are binary values like 110100101100.....

def add(self,a,b): # a,b are GF(2) polynomials like x**7 + x**3 + x**0 ....
bina,binb = obj.prepBinary(a,b)
return obj.outFormat(bina^binb)  #returns binary string

def subtract(self,x,y):  # same as addition in GF(2)

def multiply(self,a,b):  # a,b are GF(2) polynomials like x**7 + x**3 + x**0 ....
a,b = obj.prepBinary(a,b)
return obj.outFormat(a*b)  #returns product of 2 polynomials in gf2

def divide(self,a,b): #a,b are GF(2) polynomials like x**7 + x**3 + x**0 ....
a,b = obj.prepBinary(a,b)
#bitsa = "{0:b}".format(a); bitsb = "{0:b}".format(b)
return obj.outFormat(a/b),obj.outFormat(a%b)  #returns remainder and quotient formatted as polynomials

def quotient(self,a,b): #separate quotient function for clarity when calling
return obj.divide(a,b)

def remainder(self,a,b): #separate remainder function for clarity when calling
return obj.divide(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 extendedEuclideanGF2(self,a,b): # extended euclidean. a,b are values 10110011... in integer form
inita,initb=a,b;  x,prevx=0,1;  y,prevy = 1,0
while b != 0:
q = int("{0:b}".format(a//b),2)
a,b = b,int("{0:b}".format(a%b),2);
x,prevx = (int("{0:b}".format(prevx-q*x)), int("{0:b}".format(x,2)));  y,prevy=(prevy-q*y, y)
#print("%d * %d + %d * %d = %d" % (inita,prevx,initb,prevy,a))
return a,prevx,prevy  # returns gcd of (a,b), and factors s and t

def modular_inverse(self,a,mod): # a,mod are GF(2) polynomials like x**7 + x**3 + x**0 ....
a,mod = obj.prepBinary(a,mod)
bitsa = int("{0:b}".format(a),2); bitsb = int("{0:b}".format(mod),2)
#return bitsa,bitsb,type(bitsa),type(bitsb),a,mod,type(a),type(mod)
gcd,s,t = obj.extendedEuclideanGF2(a,mod); s = int("{0:b}".format(s))
initmi = s%mod; mi = int("{0:b}".format(initmi))
print ("%d * %d mod %d = 1"%(a,initmi,mod))
if gcd !=1: return obj.outFormat(mi),False
return obj.outFormat(mi)   # returns modular inverse of a,mod

obj = gf2pim()

I would first like to recommend reading PEP8 for style recommendations. Following the style guide is optional, but makes your code more readable and more understandable for other pythonistas as much python code out there follows this PEP. There is even a conformance checker you can run yourself.

I would therefore make the class GF2PIM (acronyms are in class names are always a problem) or GF2Pim. And no camelCasing in method names ( parse_poly_to_list_input instead of parsePolyToListInput ).

Within the class methods you refer to the global obj. E.g. in listToInt which calls obj.id(). This then means that within id() (the method from gf2pim, not the python build-in function id) the first parameter (self) will be obj. listToInt however is itself called with obj as its first parameter (in prepBinary()). You should remove the references within the gf2pim to obj and only use self so for listToInt() you would get:

def list_to_int(self, lst):
"""converts list to integer for later use"""
result = self.id(lst)
return int(''.join(map(str, result)))

The comment on what the function does was changed to a documentation string (which can be viewed with obj.list_to_int.doc and which intelligent editors will display on use of the method).

As id() is not using self at all you can make it a staticmethod:

@staticmethod
def id(lst):
"""returns modulus 2 (1,0,0,1,1,....) for input lists"""
return [int(lst[i])%2 for i in range(len(lst))]

It is unclear how gf2pim is used after the creation of obj doesn't do anything since gf2pim has no __init__(). It is probable that the creation of an gf2pim object can be diverted to the user of this module.

After cleaning things up that way there can probably be done more, but here is where I would start.

• new users can't upvote, so maybe someone will help you out there. i implemented what you said, and it definitely looks better using self instead of some awkward class instance from outside the class, etc. i also put in the doc strings. thanks – stackuser Jun 29 '13 at 20:15

speaking to exhibit a:

Perhaps I'm missing something, but AFAICT your class does not seem to carry any state: there aren't any variables shared between functions or persisting between function calls.

If that's so, it's easier and simpler just to make it a module -- it's merely a collection of related functions, not collection of data and methods for manipulating the data. You can get away from the whole obj business by just removing the class header and all references to 'self'. Other users would import the module and call the functions directly with no extra work.

• you're right. i will be making the case to leave this as a module. i'm wondering if class or module in this case would affect the performance or if this is more for readability/style. – stackuser Jun 29 '13 at 20:12
• There's really no performance implications - it's just a paradigm thing. Classes are bundles of state-plus-methods, modules are just collections of methods. Technically modules can have state too (your 'obj' is a module level variable) but by convention most folks use classes for stateful collections of functionality and modules for stateless. – theodox Jun 29 '13 at 21:06
• The only other rational for using a class would be if you had sets of similar functionality and passed classes along to other code which could call the methods without knowing implementation details: eg, you might have bunch of classes representing different languages that all had the same 'say_hello' method. Instead of a ton of code for 'if language == 'english' then' choices, you'd just pass in an English or Spanish or Chinese class and the calling code would call 'say_hello' and get the right response. Could do the same with modules but it's more common to uses classes for that. – theodox Jun 29 '13 at 21:09