Optimizing integer divisions with Multiply Shift in C#

• Download demo - 3.2 Kb
• Download source - 6.5 Kb

Introduction

Some time ago I read an very interesting story about the Fastest way to format time. In this story a remarkable performance boost was created by optimizing integer divisions. This inspiring optimization was proposed by Jeffrey Sax (thanx) and it is based upon the following equivalence for a certain range of num:

    x = num / div;                (1)

equals

    x = (num * mul) >> shift;     (2)

From the story I got the idea to make a simple application that finds the values for shift and mul variables automatically for a given range (0..max) of num.

How it works

The division (1) is replaced by a multiply/shift (2) pair which is in fact an approximation of the original division. The optimization is based upon the fact that the multiply and shift operators are far faster than the division operator. Depending on the range of values (0..max) the variable num can take and the value of div, valid values for mul and shift can be found. It works unless num * mul throws an overflow exception.

The bool FindMulShift(..) function searches for the values for multiply and the shift in the following way. It takes the absolute values of the two parameters to get a positive values for mul. The value of shift wil allways be positive. This implies that in your code you must map the calculation to the domain of positive integers and take care of sign bits yourselve.

First the function checks if div == 0 as this cannot be handled. Then it checks the trivial case where max < div as this allways results in a value 0. Then it is checked if div is a power of two, this is done by checking all possible (0..63) powers in a straightforward loop. For non powers of 2 more math comes in, we can derive the mul factor from the equivalence of formula (1) and (2).

    max / div = max * mul >> shift  (3)

equals

    1 / div = mul >> shift          (4)

equals

    mul = (1<< shift) / div         (5)

It is clear that the mul depends on the shift, so we cannot calculate the value for mul directly. As div is a long we only need to test the 64 possible values for shift, in fact even less. If the value of shift is known the value for mul can be determined too. Due to rounding errors of the division operator we must add 1 to formula (5) to get the right value for mul. By testing the possible values for shift from 0 to 63 we get automatically the smallest possible values for both mul and shift. The current implementation of FindMulShift tests the complete range for num if the value is less than 1.000.000. An alternative way to test the validness of mul and shift is implemented but I have not worked out the mathematical proof. However it seems OK and it is much faster! Todo: work out the mathematical proof.

I think it is possible to calculate valid values for shift and mul directly, but first 'experiments' gave not allways the minimal values and reducing to the minimal value was not always possible in a simple way.

Based upon the same equivalence the performance of the modulo function, %, can also be improved. The modulo or remainder function (6) can be replaced with formula (7) that contains a division operation, and this can be rewritten to formula (8) based upon mul and shift. Note that the single % operator is replaced by four operators.

    x = num % div;                               (6)

equals

    x = num - (num/div) * div;                   (7)

equals

    x = num - ((num * mul) >> shift) * div;      (8)

The order of the expression (8) is important as in this order it reduces the chance of an overflow exception. Note that this expression is only valid for positive values of num and div.

When to use

The optimization can be used in any application that implements a lot of integer divisions or modulos and in which the range of the numerator is known. Think of graphic libraries, processing very large (database)tables, averaging samples of real time sensors, Math libraries, webservices etc. I can also imagine that a programmer gives hints about the range of the variables passed to a function. The compiler can use this information to optimize the resulting code beyond current levels. In pseudocode it could look like below. The code

    [OPTIMIZE celcius={-273..10000}]
    public int CelciusToFahrenheit(int celcius)
    {
        return (celcius - 32)/9 * 5;
    }

could become to something like:

    [OPTIMIZED celcius={-273..10000}]
    public int CelciusToFahrenheit(int celcius)
    {
        // @ORG: return (celcius - 32)/9 * 5;

        int x = celcius - 32;        // use register for x

        if (x >=0 )
            return (x * 3641 >> 15) * 5;
        else
            return -((-x) * 3641 >> 15) * 5;
    }

Another way to use this optimizer is as a "Math Optimizer Plugin" for the programming environment. Such a plugin could include a whole range of 'tricks' like the bithacks collected by Sean Anderson.

Performance

The src application makes some simple performance measurements. To see the influence of the debugger I ran the test both in debug and in release mode(.NET 2.0, 1.6 Ghz PC).

• integer division versus MulShift
• modulo operator versus MulShift

The table below gives the measurements made on my PC. For timing I used the high performancetimer of Daniel Strigl (thanx). The test exists of 1000 divides and 1000 modulos for dividers -100..100, and a range of -1000..1000. Of course you can change these values to your needs.

mode	operator	average gain %	numbers
debug	/	-12	pos + neg
release	/	90	pos + neg
debug	%	-18	pos + neg
release	%	92	pos + neg
debug	/	42	pos only
release	/	90	pos only

Because I use both negative and positive test values there is a 'complex' if then else structure in the test program to choose the right formula, especially for the modulo operator. Normally the denominator is fixed and the code can be much simpler of course. The last test of the application does a test for positive numbers only. Working with only positive numbers did also show improvements in the debug mode. Finally in the release code the overhead of handling the signs yourself seems to have no substantial influence.

As the scheduling of the OS influences the measurements there will be differences when the test is run again. Performance gains will also differ on different hardware and for different programming languages. Just measure your own.

Finale

In short a substantial gain can be made by replacing integer divisions by a multiply/shift pair. Be aware that in the debug mode the optimized code can be slower, especially if you have both negative and positive numbers and you have to handle the sign yourself.

Some items to improve the FindMulShift algorithm include:

• rangefinder, given a certain dividor what is the maximum range?,
• work out a mathematical proof of the fast verify method,
• investigate the limits of the optimization,
• investigate direct calculation of mul and shift,
• investigate doubles as divider?
• refactor ad fundum!

History

• 2007/01/27 - Version 1.00 - First version to publish.
• 2006/09/08 - Version 0.00 - Started experimenting.

Usage rights

Everybody is granted to use this code (at own risk) as long as you refer to the original work of Jeffrey Sax and this article.

You must Sign In to use this message board.

FAQ    Noise Tolerance Very HighHighMediumLowVery Low   Layout Expand Posts & RepliesThread ViewNo JavascriptNo JS + Preview   Per page 102550

Msgs 1 to 17 of 17 (Total in Forum: 17) (Refresh) FirstPrevNext

Unsigned int froofy 11:05 11 Dec '09   Is there any performant way to make this work for an unsigned int? I want divide by 100 to work for 0x80000000 (2147483648), but the generated code fails: n / 100 <==> n * 1374389535 >> 37 I think it might work if you do this: n / 100 <==> (int)(((ulong)n) * 1374389535UL >> 37) but unfortunately the JIT seems to generate a method call for the unsigned long multiplication, rather than using the MUL asm instruction like a good optimizing C++ compiler would. Sign In·View Thread·PermaLink Re: Unsigned int rob tillaart 4:48 16 Dec '09   Hi froofy, Did not investigate unsigned ints, sorry The max and mul factor are both in the range of 32 bit MAXINT, so your proposal to move to 64 bit level makes sense. Idea 1: try mapping to long instead of unsigned long. n / 100 <==> (int)(((long)n) * 1374389535L >> 37) Does it also generate a method call? Idea 2: remember 100 = 4x25 Divide the number by 4 first (shift 2) and the denominator becomes 25 Denominator: 25 Max enumerator: 536870912 ==> (max value/4) n / 25 <==> (n>>2) * 42949673 >> 30 Hopes this helps, Rob Sign In·View Thread·PermaLink Found an issue. DealsBrokeMe 16:02 29 Sep '09   Thanks for the great article. I am doing a mod6 on a large number. I get the remainder as -1, -7, -9, etc. Ex: long j = 14339; long r = j - ((j * 683) >> 12) * 6; The above code fails. My solution is: long r=j; do { r = r - ((r * 683) >> 12) * 6; } while (r < 0 || r > 5); But then it becomes time consuming. I am thinking it is overflowing somewhere causing -ve values... Sign In·View Thread·PermaLink Re: Found an issue. rob tillaart 11:45 1 Oct '09   Hi Deals, Thanks for the remark, there is an overflow indeed. The mul/shift trick works only for a certain range and the demo program tries to find the "trick" formula for a given enumerator and denominator. When I ran the demo program and fill in 6 as denominator and 14339 as the maximum enumeration value, then the demo program states: Denominator: 6 Max enumerator: 14339 // assumption this is your largest value n / 6 <==> n * 10923 >> 16 so for a modulo 6 one line in your code should change into long r = j - ((j * 10923) >> 16) * 6; And it will provide the right answer 5. Note that if the max enumerator is larger than 14339 you should rerun the demo program. If numbers become very large recall that 6=2x3 and that one can divide j by 2** first (=shift 1) before dividing by 3 (mul/shift). That would approx. double the number at which overflow occurs, but it adds an instruction so it will be a little slower but might still be faster (not tested). The line becomes: long r = j - (((j >> 1) * 10923) >> 15) * 6; // note 16 => 15 Hopes this helpes solving your problem, if not let me know. regards, Rob ** In general one could eliminate all powers of 2 in the denominator to increase the range. So if no mul/shift pair can be found, on might try to find a shift/mul/shift triple. Nice exercise to test what performance gain is left. Someday Sign In·View Thread·PermaLink Re: Found an issue. DealsBrokeMe 5:35 2 Oct '09   So in case when i don't know the max number [it is used input], is there anyway i could run this. User could enter 1Billion or 1 Trillion too. How do i make sure that the formula works fine without resorting to: if (n < 10*1000) // 10K return <> elseif (n < 1000*1000) // 1M return <> elseif (n < 1000*1000*1000) // 1B return <> else // Over 1B return <> Sign In·View Thread·PermaLink Re: Found an issue. rob tillaart 9:36 2 Oct '09   Never used this optimization trick for large numbers but you might just check against the max value the trick works for. For a modulo 6 that is approx 3,200,000,000 resulting in the following code: if (n <= 3200000000) return n - ((n * 2863311531 ) >> 34) * 6; else return n % 6; Note 1: You should make a test application (loop with 1 billion %'s and mul/shift's or so) to check if the mul/shift version of the (release!) code performs better on your deployment platform. On my current 32bit laptop it ran slower(!). Possible cause: the multiplication in the above code does 64bit math as it maximizes the range. My test in the article only covered relative small integers with no 32bit overflow on another PC/ processor. Or this laptop has a better modulo? Who knows... OTAT ==> Optimization tricks, always tricky Note 2: If the number n comes from a user you should rethink if you need (want) optimization. Typing in a number takes approx a second per digit while this optimization is about microseconds or less. Differs several orders of magnitude so to say. For me the main usage of these optimization tricks is when processing a lot of data (sound, image, video, datatables etc) or when real time processing is really an issue. regards, Rob Sign In·View Thread·PermaLink Re: Found an issue. RajeshKumar25 9:42 3 Oct '09   Thanks. I think i will go with the trick of range then ... And either use the optimized version for smaller ranges or go with straight modulo for larger ranges. Even though is a user input, the mod calc happens from 1 to , i.e. is an upper limit. [This is for a test 6K+1, 6K+5 prime sieve....] There are tons of div and mod calcs that are performed, hence was attempting to optimize it.... Will post the updated results with n=1trillion to specify which subranges works faster with optimization or without. Sign In·View Thread·PermaLink Eeevil ! fd123456 13:58 7 Jul '07   If optimization is the root of all evil, you are the devil incarnate! It's a weird, beautiful and inspiring idea. Thanks! Michel Sign In·View Thread·PermaLink Re: Eeevil ! rob tillaart 8:52 10 Jul '07   Hi Michel, I had no time yet to update the article but the trick does work for dividing with doubles too (although the range may be less). It is quite easy to patch the code for this. Imagine you have a lot of integers you have to divide by PI or E or a less famous double. It gives quite a performance speedup. regards, rob PS, the credits for the idea go to Jeffrey Sax (see URL in article) Sign In·View Thread·PermaLink OK, Now I get it... DQNOK 11:15 14 Feb '07   I spent quite a bit of time trying to figure how the algorithms you suggested could possibly be faster than a simple IDIV. I was misinterpreting you to say you had developed a general replacement for IDIV: int fastIDIV( int numerator, int denominator ); when in fact you are merely suggesting a replacement for WHEN THE DENOMINATOR IS KNOWN AHEAD OF TIME: int fastIDIVby9( int numerator ){ return numerator * 3641 >> 15; } int fastIDIVby10( int numerator ){return numerator * 6554 >> 16; } int fastIDIVby11( int numerator ){return numerator * 5958 >> 16; } etc. The AMD reference given above does cite similar algorithms that date back quite a ways (more than 10 years). It really should be noted that the CelciusToFahrenheit() function you cite (which SHOULD be called FahrenheitToCelcius since that is what the algorithm actually does) ONLY returns multiples of 5 as answers. A more correct approach would be to roll the 5 in BEFORE the shift: [OPTIMIZED Fahrenheit={-273..10000}] public int FahrenheitToCelcius(int Fahrenheit) { // @ORG: return (Fahrenheit - 32)/9 * 5; int x = Fahrenheit - 32; // use register for x if (x >=0 ) return (x * 18205 >> 15); else return -((-x) * 18205 >> 15); } Algorithmically, all we're doing is writing the fraction 5/9 as a decimal (0.5555555555), pre-multiplying that fraction by 2^15 (0.5555555555 * 2^15 = 18204.444, but rounded up to 18205), then dividing the result by 2^15 by shifting >>15. I ASSUME that the algorithm you used handles the least-significant bits correctly. That is, for fastIDIVby9 you use x * 3641 >> 15; but a naive look at the problem says that x * 7282 >> 16 might produce consistently more accurate results. It all has to do with the way integer division rounds. I assume that the folks who proposed the algorithms did the hard work of checking to make sure they got correct results. Thanks for the article. Sign In·View Thread·PermaLink 2.00/5 (1 vote) Re: OK, Now I get it... rob tillaart 7:56 15 Feb '07   Hi, When time permits I will update the article formulated a bit sharper. Should add some performance figures for the function variation too. The algorithm searches for the smallest shift value for a given range of the numerator. Rationale is that the range of integers for which it works will be largest possible without overflow. Processors often use a 32shift to optimize for the internal registers. Currently I am working on the proof for the fast verification [only checking three values of the range]. FYI, I have done a prelimenary test with replacing a division of an integer by a (known) double returning an integer with a fixed multiply shift and it seems to work equally well. Not strange but it expands the scope of the 'trick'. Thanx for the remarks, rob Sign In·View Thread·PermaLink Re: OK, Now I get it... DQNOK 8:24 15 Feb '07   If you're using a floating-point, I don't think there is any reason to use a shift at all. public int FahrenheitToCelcius( int fahrenheit) { return (fahrenheit-32) * (5.0/9.0) } Since (5.0/9.0) is a stored (computed at compile-time) constant, the routine casts (fahrenheit-32) to floating-point before the multiplication, then back to integer for the return. The question is whether the platform you're running on does the cast - multiply - cast sequence faster than the integer multiply - shift construct you proposed. BTW, I found a really good reference for this subject at http://blogs.msdn.com/devdev/archive/2005/12/12/502980.aspx[^]. It explains the details, and covers the issue I brought up regarding how to choose the right constant so that the division is CORRECT (and not just fast). Thanks again. David Sign In·View Thread·PermaLink See also: AMD's optimization guide. b647 12:04 10 Feb '07   For another source of information on the same topic, see Chapter 8 "Integer Optimizations" of the "AMD Athlon Processor x86 Code Optimization Guide", available online at: http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/22007.pdf Sign In·View Thread·PermaLink Re: See also: AMD's optimization guide. rob tillaart 7:58 15 Feb '07   True, will check the site. Seen quite some sites mentioning the trick last week . Thanx, rob Sign In·View Thread·PermaLink more consideration jeff323 4:15 8 Feb '07   (x * 3641 >> 15) * 5 ==> Y =(Y<<2 )+Y == Y * 5 this has been tested againt SGI stl hashing code,the origin is h+=x(i) * 5 Sign In·View Thread·PermaLink Quick way to check if an int is a power of 2 [modified] djlove 21:57 5 Feb '07   In your article you mention: Then it is checked if div is a power of two, this is done by checking all possible (0..63) powers in a straightforward loop. You might be interested in a quick method for finding if div is a power of two (for div >= 1) (div & (div-1)) == 0 If you think about it in binary it makes sense! Actually I just noticed that the web page you link to contains this method: Determining if an integer is a power of 2 unsigned int v; // we want to see if v is a power of 2 bool f; // the result goes here f = (v & (v - 1)) == 0; Note that 0 is incorrectly considered a power of 2 here. To remedy this, use: f = !(v & (v - 1)) && v; -- modified at 3:32 Tuesday 6th February, 2007 Sign In·View Thread·PermaLink Very nice! Grav-Vt 16:06 4 Feb '07   This is an enjoyable article, thank you. - Nick Sign In·View Thread·PermaLink

Last Visit: 20:02 9 Feb '10     Last Update: 20:02 9 Feb '10 1