How fast is division?

Question

hi,

i was once supposed to make a short assembler code for dividing with numbers that are not power of 2. My solution was subtracting the divider in cycles and the number of cycles was the actual result. Is there anything faster? What's the usual way to sort this out?

Answer 1

There are a bunch of algorithms mentioned and detailed on Wikipedia.

Answer 2

Repeated subtraction is a dangerously inefficient way of doing division. In the worst case, an N-bit division can take O(2**N) subtractions!!

@Johannes answer has a link that gives you algorithms that work much better than that.

If I was asked to implement division in assembler, I'd probably do an extensive search for an existing library of numeric routines. This is the kind of problem where it takes a lot of expertise to come up with close to optimal code.

EDIT : in response to the OP's comment:

It's just that i'm making some program in C++ now and i'm deciding whether use division to solve one problem or make up something else to make it faster.

I suggest that you just use division, and leave it to the C++ compiler to generate the most efficient instruction sequence to achieve the required result for your particular target platform.