Everyone knows how expensive division instructions can be, especially on the x86. I found a

Enjoy ;)

__neat article__(though, fairly old) that has some good information on using alternate methods. These alternate methods are nothing new, and are not alien to me... but the biggest thing about that link, is that it provides some 32-bit constants for use in alternate methods... a handy reference.Enjoy ;)

Agner Fog has explained the multiplication by reciprocal in his "Optimizing subroutines in Assembly language" manual rather completely at the "Integer division by a constant (all processors)" section. By far it's the fastest way I have found to for example divide a number by 10.

"Magic Divider" by The Svin does the trick for every division by constant.

Thanks for the info :)

I've skimmed through Agner's manuals to grasp general ideas before, but there is so much information that it is hard to remember what all is in there :P

I've skimmed through Agner's manuals to grasp general ideas before, but there is so much information that it is hard to remember what all is in there :P

To the Ineffable All,

I call the above methods, "half division" algos. That's because they don't give you a remainder. Of course you can get the remainder by subtracting from the dividend, the product of the quotient and divisor. But do you save any time doing that? :shock: Ratch

I call the above methods, "half division" algos. That's because they don't give you a remainder. Of course you can get the remainder by subtracting from the dividend, the product of the quotient and divisor. But do you save any time doing that? :shock: Ratch

According to the link "Chapter 10: Integer Division by Constants" within the page I linked above, there are statistics for a particular example, obviously in favor of the method described. This method includes the remainder, such as you described.

I guess the best way to figure that out exactly, is to test and compare the said method to a standard DIV instruction ourselves :)

I guess the best way to figure that out exactly, is to test and compare the said method to a standard DIV instruction ourselves :)

I always wondered: If such 'smart & quick' division methods exist, then why Intel/AMD won't make their 'div' instructions use these methods? If I can 'div' in 'X' cycles, then why not make a 'div' instruction which divides in 'X' cycles using this algorithm? I wouldn't be much more expensive, would it..?

I always wondered: If such 'smart & quick' division methods exist, then why Intel/AMD won't make their 'div' instructions use these methods? If I can 'div' in 'X' cycles, then why not make a 'div' instruction which divides in 'X' cycles using this algorithm? I wouldn't be much more expensive, would it..?

You must realize that, in order to get the "magic number" required to replace the division by a multiplication, you must FIRST perform a division. THEN, the time required to perform that division PLUS a multiplication would take more time than the single division.

The only time that the multiplication by the reciprocal is time saving is when you either set a constant's reciprocal in the .data section OR you can use the reciprocal of a variable more than once. That knowledge CANNOT be built-in on a chip.

Another factor which must be considered is that some of the "magic numbers" suggested have been

*expanded*to improve overall accuracy when used with large numbers. Those require the subsequent use of shifts to provide the correct answer and everybody knows that such instructions can be slow on some processors.

Raymond

Don't tell me that the magic numbers are the only fast-division method? I'm sure that smart mathematicians could develop something faster if they really wanted :P Or they could at least make some frequently used divisions faster..? What I mean is: Is it really so hard to make fast (and still cheap) division?

ti_mo_n,

As Raymond said, if you can pre-compute the inverses beforehand with a compiler or manual program, then no. Otherwise it takes a intimate knowledge of number theory and hardware engineering to make the chip to do it. Ratch

What I mean is: Is it really so hard to make fast (and still cheap) division?

As Raymond said, if you can pre-compute the inverses beforehand with a compiler or manual program, then no. Otherwise it takes a intimate knowledge of number theory and hardware engineering to make the chip to do it. Ratch

Mathematically there is a quick division replacement

but computationally it is much slower because of the overhead

(getting the logs and the inverse log).

The exponential (inverse natural logarithm)

of the difference of the natural logarithms of the dividend and divisor.

20 = 100 / 5

20 = exp(ln(100) - ln(5))

but computationally it is much slower because of the overhead

(getting the logs and the inverse log).

The exponential (inverse natural logarithm)

of the difference of the natural logarithms of the dividend and divisor.

20 = 100 / 5

20 = exp(ln(100) - ln(5))

"Magic Divider" by The Svin does the trick for every division by constant.

That is a great little utility that I make constant use of, I have included it in this post for those who do not have it. I hope The Svin doesn't mind...

do you all live in the dark ages?, chip is already builtin your x86 to perform RCP lookups for you, I timed a RCPPS followed by a MULPS 5.5 cycles and it equalivent to 4 lowprecisionfdivs, higherprecision you use RCP with newton-rapson

integer divs? there are floattoint conversion that converts two reciprocals for you at a time

integer divs? there are floattoint conversion that converts two reciprocals for you at a time

and please remind me of the precision of the methods you mentioned :) .