Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

migrated from codereview.stackexchange.com Jun 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

1 Answer 1

up vote 1 down vote accepted

There is pretty much no way your own hand-rolled operation will be anything but pathetically slow compared to the built-in operations in python. If you try to implement hand-rolled operations you will make you program much much slower.

If you'd like to know how to make your code run faster, ask that question. Post your complete slow code on http://codreview.stackexchange.com, and get feedback there on what can be improved.

share|improve this answer
    
Part of the issue is that I'm working with very large integers (>200 bits) and many typical programming solutions don't always go over well. For instance, max recursion depth is hit early on and so only iteration is possible. Not sure how much of this is used in average coding but I'm wondering if there is some equation or rule of thumb in writing to support very large numbers -- use addition or subtraction whenever possible, etc...? or convert to binary then operate? would doing these things also speed up the code or just support bigger numbers? –  stackuser Jun 30 '13 at 22:20
    
@stackuser, the rule of thumb is don't use large numbers. I don't know what you are doing, but do you really need to use such large numbers? –  Winston Ewert Jun 30 '13 at 23:03
    
Yes, you really need to use such large numbers. Unless you have a better way of doing cryptography and cryptanalysis. I thought this was asking a programming-specific question, but I'm just a student and I guess I need to post this in the crypto-stack-exchange. Sorry for bothering everyone here, but I'm really just not sure where else to ask. Crypto SE or maybe math SE, I'm just not sure where else to take this question... –  stackuser Jul 1 '13 at 2:01
    
@stackuser, no no, this is the best site for your question. I see you've got a good reason to use big numbers (most cases don't) –  Winston Ewert Jul 1 '13 at 2:10
2  
@stackuser, what you need is code.google.com/p/gmpy, a library that gives you an efficient object to represent long numbers. It uses highly optimized C underneath. It'll be the most efficient way to deal with those numbers that you can get in python. –  Winston Ewert Jul 1 '13 at 5:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.