Numerical conversion from binary to mixed base -- without divisionDick GruneNumerical 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
The whole package (demo.c, Makefile, doc (pdf) file, table for pounds/shillings/pence conversion, efficiency measurements) can be downloaded here (zipped).
Numerical conversion from binary to mixed base -- without division /
Dick Grune /
dick@dickgrune.com
|