## Monday, June 15, 2009

### "Fast" division

This is mostly a note-to-self on how to divide a number in base b with some integer n using nothing but "fast" operations like addition, subtraction and shifting (occasionally multiplication) -- if you bake them together, you typically end up with something of linear complexity or slightly better:

To divide a number in base b with some integer n, find the recursive relationship

1/n = 1/b + (b-n)(1/b)(1/n)

Where 1/b of course can be expressed as a digit shift. So, to express division by 3 in a way that is convenient to a binary computer, you get the relationship

1/3 = 1/2 - 1/2 * (1/3) => 1/3 = 1/2 - 1/4 + 1/8 - 1/16 + 1/32 - 1/64 ...

Conversely, to express division by 2 that is convenient to a trinary computer, you get

1/2 = 1/3 + 1/3 * (1/2) => 1/2 = 1/3 + 1/9 + 1/27 + 1/81 + 1/243 + 1/729 + ...

So now you know... It's pretty easy to vectorize the algorithm you get out of this, but you need to tip-toe around the minefield that is the decimal parts (well, actually, calculate their carry and add that to the integer part) to avoid rounding errors.