Approximate division using multiplication and right-shift

Problem

Many processors have no native floating-point capabilities, leading to the choice between integer maths or floating-point emulation. One important range of microcontrollers, ATmega, also has no native arithmetic division operation. Thus, the Arduino project, which uses the ATmega chipset, must use a compiler that emulates both integer and floating-point division in software. In some cases, it might be better to ignore the compiler and roll your own less-accurate version of the division op.

Decimal Tricks

All numerate people have learned mental tricks to help with arithmetic division. We learn multiplication tables so that, given we know 55 is five times eleven and 66 is six times eleven, then we also know that 57 divided by 11 is slightly more than five.

5 < (57 / 11) < 6

Dividing is equivalent to multiplying by a reciprocal, and some of these reciprocals have a simple decimal expansion. For example, given we know that one-eighth is 0.125, we can assume that division by 125 is equivalent to multiplication by eight, with some shift of the decimal point.

(x / 125) == (x * 8 / 1000)

Further, some decimal expansions of reciprocals are close to being helpful. The reciprocal of 77 is around 0.01299, meaning that we can approximate a division by 77 with a multiplication by 13, followed by some shift of the decimal point.

(x / 77) =~ (x * 13 / 1000)

Binary Tricks

We can apply the "multiplication and right-shift" trick to binary division, which is slightly more useful when programming. First, of course, any division by a whole power of two is equivalent to a right-shift.

(x / 2) == (x >> 1)
(x / 4) == (x >> 2)
(x / 8) == (x >> 3)
(x / 16) == (x >> 4)
(x / 32) == (x >> 5)
...

Next, we can use approximations that give us good results within a limited range. For example, given that x is between zero and 255, and we are calculating an integer result, the following expressions are true:

(x / 3) == ((x * 171) >> 9)
(x / 5) == ((x * 205) >> 10)
(x / 6) == ((x * 171) >> 10)

Of course, if we are limiting ourselves in this way to integer maths, and 8-bit numerators, every result for divisors over 128 can be calculated with a simple comparison:

(x / 129) == (x < 129 ? 0 : 1)
(x / 130) == (x < 130 ? 0 : 1)
(x / 131) == (x < 131 ? 0 : 1)
(x / 132) == (x < 132 ? 0 : 1)
...

There are a few problems in replacing division by multiplication in this way. The best example is division by seven:

(x / 7) =~ ((x * 147) >> 10)

Now, this expression is mostly true, but starts to become inaccurate at x=209, with seven off-by-one errors in the whole range. Whether these off-by-one errors are acceptable is a matter of personal choice, but given the limitations of integer maths, it seems reasonable to sacrifice a little accuracy for speed here.

Use case

A sensor can produce a voltage on an Arduino analog pin which will be converted into an unsigned 10-bit integer. To format this value in human-readable units (centigrade, metres, hours, etc.) requires division by a constant divisor. Often, humans don't care about off-by-one errors when reading the temperature of their ovens. Using the multiply-and-shift method can reduce time and memory usage, and produce a result in a constant number of clock cycles.

Complete list of multiplications

Here's a complete list of approximate divisions in the 8-bit space. Change the Perl script for the equivalent 10-bit approximations.

Source code