multiply by dividing

[thomas_remkus]

I have recently read a tip stating that if you face a full 32-bit number and need to divide you multiple and take the ?"top"? half as the result. What does this even mean? And if it truely does mean something then how much faster is it? Can someone help me understand this madness? And if it's so awesome, there's got to be a macro out there that already does this ... ?

[u]

The MagicDivider by TheSvin, iirc. Look it up. It's much faster than div. There's also a macro, for the first 80 numbers.

[thomas_remkus]

Thanks for this point. The only thing I came up with was a reference in "http://www.masm32.com/board/index.php?topic=6382.0". Was this the only reference you were talking about?

[GregL]

Here's a thread about it.

And the source code for The MagicDivider is here too.

[raymond]

Simply imagine that you have to divide many integers by 3 in the decimal system and you only need the result as a truncated integer. You could also say that you need to multiply all those numbers by 1/3. If you use 0.33333333333333334 as the closest rounded-up approximation of 1/3, and you multiply it by 100 for example, you would get 33.333333333333334. If you then drop the fractional part you get 33 which is the truncated result of dividing 100 by 3.

You simply do the same in binary. If you divide 100000000h (EDX=1, EAX=0) by 3, you get 55555555h which you then increment to 55555556h. If you multiply that by 100, you would get 2155555598h, of which the 21h would be in EDX and the 55555598h would be in EAX. The part in EAX is the "fractional" part which you drop. The truncated result is in EDX = 21h = 33. Voila!

The gain in speed is due to the fact that divisions take somewhat longer than multiplications to be performed. That gain in speed will vary depending on the actual numbers being crunched.

In some circles, that 55555556h is often called a magic number. Each integer has its own magic number. Those are useful when you need the same divisor numerous times in a time critical loop. However, if your divisor is a semi-random number generated by other instructions, you would need a division to get its magic number followed by a multiplication to get your quotient; not very efficient in such cases.

Raymond