Monday, January 18, 2010

Fast divide by X

A friend sent me a thread on quick divide routines for the AVR microcontroller. While the article is interesting, it is also a very poor solution.

The problem was to provide a fast result for divide by '5' in the range 0..255 (or even 0..100).
The solution was a fixed-point cludge, what was suggested was using the high byte result from: x * 51 + 1.
Unfortunately this gives the wrong result. The original concept can be made to give the correct results from 0..100 by modifying this to: x * 51 + 20
However, an even better solution is simply: (x+1)*51, which gives correct results all the way to 255.

A similar answer is possible for division by 3: (x +1)*81.

(Note: If you want to use this on the PC, don't forget to shift right by 8, eg: y = ((x+1)*81) >> 8

There are many more wonderful bithacks documented online.

1 comment:

P AL said...

Gracias por tu ayuda, una consulta? Que sucede con un número real al dividirlo por ' ' x ' se puede hacer eso? Cómo quedaría?