# Python — Time complexity of built-in functions versus manually-built functions in finite fields

Generally, I'm wondering about the advantages versus disadvantages of using the built-in arithmetic functions versus rolling your own in Python.

Specifically, I'm taking in GF(2) finite field polynomials in string format, converting to base 2 values, performing arithmetic, then output back into polynomials as string format. So a small example of this is in multiplication:

Rolling my own:

``````def multiply(a,b):
bitsa = reversed("{0:b}".format(a))
g = [(b<<i)*int(bit) for i,bit in enumerate(bitsa)]
return reduce(lambda x,y: x+y,g)
``````

Versus the built-in:

``````def multiply(a,b):  # a,b are GF(2) polynomials in binary form ....
return a*b  #returns product of 2 polynomials in gf2
``````

Currently, operations like multiplicative inverse (with for example 20 bit exponents) take a long time to run in my program as it's using all of Python's built-in mathematical operations like // floor division and % modulus, etc. as opposed to making my own division, remainder, etc. I'm wondering how much of a gain in efficiency and performance I can get by building these manually (as shown above).

I realize the gains are dependent on how well the manual versions are built, that's not the question. I'd like to find out 'basically' how much advantage there is over the built-in's. So for instance, if multiplication (as in the example above) is well-suited for base 10 (decimal) arithmetic but has to jump through more hoops to change bases to binary and then even more hoops in operating (so it's lower efficiency), that's what I'm wondering. Like, I'm wondering if it's possible to bring the time down significantly by building them myself in ways that maybe some professionals here have already come across.

-

## migrated from codereview.stackexchange.comJun 30 '13 at 21:04

This question came from our site for peer programmer code reviews.

And we are back here again.. – Martijn Pieters Jun 30 '13 at 21:43
@MartijnPieters, eh? – Winston Ewert Jun 30 '13 at 21:54
@WinstonEwert: This post first appeared here. Then it was deleted and re-appeared on Stack Overflow. Then it must've been re-posted on Codereview, from where it was migrated to Programmers again.. – Martijn Pieters Jun 30 '13 at 21:56
You can actually try it out. This link can be helpful. Or you can try having a look at this link and this link. Testing out a few of the group of functions that you are considering to write might help you get a grasp of how good is your code. – Aseem Bansal Jul 3 '13 at 3:59
After trying the code for yourself put all the results on codereview. You might get better response. – Aseem Bansal Jul 3 '13 at 4:01