Click here to Skip to main content
12,699,807 members (37,639 online)
Click here to Skip to main content
Add your own
alternative version

Stats

105.6K views
1.5K downloads
46 bookmarked
Posted

Optimizing integer divisions with Multiply Shift in C#

, 2 Feb 2007
Rate this:
Please Sign up or sign in to vote.
An article on improving the performance of an algorithm by replacing integer divisions

screenshot of the demo application

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.

modeoperatoraverage gain %numbers
debug/-12pos + neg
release/90pos + neg
debug%-18pos + neg
release%92pos + neg
debug/42pos only
release/90pos 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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

rob tillaart
Web Developer
Netherlands Netherlands
No Biography provided

You may also be interested in...

Pro
Pro

Comments and Discussions

 
Questionlove it Pin
Hua Yujun7-Dec-12 5:45
memberHua Yujun7-Dec-12 5:45 
GeneralWhy the worry about overflow/maximum numerator/having the minimal values? Pin
SimmoTech5-May-11 5:10
memberSimmoTech5-May-11 5:10 
GeneralRe: Why the worry about overflow/maximum numerator/having the minimal values? Pin
rob tillaart5-May-11 22:04
memberrob tillaart5-May-11 22:04 
GeneralRe: Why the worry about overflow/maximum numerator/having the minimal values? Pin
SimmoTech5-May-11 23:04
memberSimmoTech5-May-11 23:04 
GeneralUnsigned int Pin
froofy11-Dec-09 11:05
memberfroofy11-Dec-09 11:05 
GeneralRe: Unsigned int Pin
rob tillaart16-Dec-09 4:48
memberrob tillaart16-Dec-09 4:48 
GeneralFound an issue. Pin
DealsBrokeMe29-Sep-09 16:02
memberDealsBrokeMe29-Sep-09 16:02 
GeneralRe: Found an issue. Pin
rob tillaart1-Oct-09 11:45
memberrob tillaart1-Oct-09 11:45 
GeneralRe: Found an issue. Pin
DealsBrokeMe2-Oct-09 5:35
memberDealsBrokeMe2-Oct-09 5:35 
GeneralRe: Found an issue. Pin
rob tillaart2-Oct-09 9:36
memberrob tillaart2-Oct-09 9:36 
GeneralRe: Found an issue. Pin
RajeshKumar253-Oct-09 9:42
memberRajeshKumar253-Oct-09 9:42 
GeneralEeevil ! Pin
fd1234567-Jul-07 13:58
memberfd1234567-Jul-07 13:58 
GeneralRe: Eeevil ! Pin
rob tillaart10-Jul-07 8:52
memberrob tillaart10-Jul-07 8:52 
GeneralOK, Now I get it... Pin
DQNOK14-Feb-07 11:15
memberDQNOK14-Feb-07 11:15 
GeneralRe: OK, Now I get it... Pin
rob tillaart15-Feb-07 7:56
memberrob tillaart15-Feb-07 7:56 
GeneralRe: OK, Now I get it... Pin
DQNOK15-Feb-07 8:24
memberDQNOK15-Feb-07 8:24 
GeneralSee also: AMD's optimization guide. Pin
b64710-Feb-07 12:04
memberb64710-Feb-07 12:04 
GeneralRe: See also: AMD's optimization guide. Pin
rob tillaart15-Feb-07 7:58
memberrob tillaart15-Feb-07 7:58 
Generalmore consideration Pin
jeff3238-Feb-07 4:15
memberjeff3238-Feb-07 4:15 
GeneralQuick way to check if an int is a power of 2 [modified] Pin
djlove5-Feb-07 21:57
memberdjlove5-Feb-07 21:57 
GeneralRe: Quick way to check if an int is a power of 2 Pin
John Paul Walker25-Apr-11 11:19
memberJohn Paul Walker25-Apr-11 11:19 
GeneralRe: Quick way to check if an int is a power of 2 Pin
djlove25-Apr-11 22:25
memberdjlove25-Apr-11 22:25 
GeneralRe: Quick way to check if an int is a power of 2 Pin
John Paul Walker26-Apr-11 21:07
memberJohn Paul Walker26-Apr-11 21:07 
GeneralRe: Quick way to check if an int is a power of 2 Pin
djlove28-Apr-11 6:46
memberdjlove28-Apr-11 6:46 
GeneralVery nice! Pin
Grav-Vt4-Feb-07 16:06
memberGrav-Vt4-Feb-07 16:06 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170118.1 | Last Updated 2 Feb 2007
Article Copyright 2007 by rob tillaart
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid