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]

---

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