## Numerical conversion from binary to mixed base -- without division

### Dick Grune

Numerical conversion is usually performed using division, but in the early days not all computers had a divide instruction, and other techniques were invented. One simple and nifty algorithm is presented here; it does numerical conversion to mixed base, without using division, all in a few lines of code. I think I saw it in documentation that came with the Elliot 503 in the late 1960s, where it was used to convert pennies to pounds/shillings/pence. I don't think it was ever published; if you have information to the contrary, please let me know!

The algorithm is described here. It uses a fixed table which specifies the base for each digit, and then determines the digit by a few subtractions and additions. A simple variant of the code runs the algorithm backwards, converting numeric strings in mixed base to binary.

The C file demo.c shows how it works. For converting 5087 to decimal it produces

 ```Converting 5087 units to decimal, using nd_conv(): val = 2087, res = '3???' (val -= 3000, res += 3) val = -913, res = '6???' (val -= 3000, res += 3) val = 87, res = '5???' (val += 1000, res -= 1) val = -213, res = '53??' (val -= 300, res += 3) val = -113, res = '52??' (val += 100, res -= 1) val = -13, res = '51??' (val += 100, res -= 1) val = 87, res = '50??' (val += 100, res -= 1) val = 57, res = '503?' (val -= 30, res += 3) val = 27, res = '506?' (val -= 30, res += 3) val = -3, res = '509?' (val -= 30, res += 3) val = 7, res = '508?' (val += 10, res -= 1) val = 4, res = '5083' (val -= 3, res += 3) val = 1, res = '5086' (val -= 3, res += 3) val = -2, res = '5089' (val -= 3, res += 3) val = -1, res = '5088' (val += 1, res -= 1) val = 0, res = '5087' (val += 1, res -= 1) n_steps = 16 result = "5087" ```

The whole package (demo.c, Makefile, doc (pdf) file, table for pounds/shillings/pence conversion, efficiency measurements) can be downloaded here (zipped).

###### [Home Page]
Numerical conversion from binary to mixed base -- without division / Dick Grune / dick@dickgrune.com

... and my name is not Richard ...