## 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)
{
int x = celcius - 32;
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.