Python — Time complexity of built-in functions versus manually-built functions in finite fields
- by stackuser
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.
