So I’ve done some hands-on work with converting integers from one base to another using the well-known method of division and taking the remainder. The most generic algorithm involves dividing the number recursively, and looking up the digits of the target base using the remainder. For example, let’s say I wanted to convert 72310 from base-10 notation to base-16 (hexadecimal) notation: $$ 723_{10} \div 16_{10} = 45_{10}\ r3_{10} \\ 45_{10} \div 16_{10} = 2_{10}\ r13_{10} \\ 2_{10} \div 16_{10} = 0_{10}\ r2_{10} $$ The remainders are 310, 1310, and 210, and using the digits { 016, 116, 216, 316, 416, 516, 616, 716, 816, 916, a16, b16, c16, d16, e16, f16 }, the base-16 representation of 72310 would be 2d316.
If I wanted to convert base-16 to base-2, it would be a simple matter of mapping each base-16 digit to a string of base-2 digits. For example, suppose I wanted to convert 2d316, I would build a table mapping each of the base-16 digits to 4 base-2 digits like this: $$\\ 0_{16} \rightarrow 0000_{2} \\ 1_{16} \rightarrow 0001_{2} \\ 2_{16} \rightarrow 0010_{2} \\ 3_{16} \rightarrow 0011_{2} \\ 4_{16} \rightarrow 0100_{2} \\ 5_{16} \rightarrow 0101_{2} \\ 6_{16} \rightarrow 0110_{2} \\ 7_{16} \rightarrow 0111_{2} \\ 8_{16} \rightarrow 1000_{2} \\ 9_{16} \rightarrow 1001_{2} \\ a_{16} \rightarrow 1010_{2} \\ b_{16} \rightarrow 1011_{2} \\ c_{16} \rightarrow 1100_{2} \\ d_{16} \rightarrow 1101_{2} \\ e_{16} \rightarrow 1110_{2} \\ f_{16} \rightarrow 1111_{2} $$ Without any knowledge of the digits before or after, I can convert each digit independently and get 0010110100112 in base-2. This is advantageous for computer applications when all the digits cannot be known in advance or held in memory to be processed since the process is bijective.
But if I had an arbitrarily-long string of digits (such as an array of bytes in computer memory), what is another method to convert the digits to an arbitrary base without division? Applying division requires the entire string of digits from start to finished to be available all at once, and in a scenario such as real-time encoding of a stream of bytes on a computer, not all the digits will be available. Knowing only a slice of the string, can I map the available digits to digits in any other base?
So far, I’ve put some thought into this and I’m almost certain that it cannot be done. Here’s a simple example:
In a test scenario, suppose my program is initially supplied with the hexadecimal digits { 016, 016, 016, 016 } over a network connection by another computer A. My program must pass the digits to another computer, B after converting the digits to decimal. Because of memory constraints, however, I can only process 2 hexadecimal digits at a time.
My program, upon receiving { 016, 016, 016, 016 }, will forward 4 digits { 010, 010, 010, 010 } to computer B since 4×log(16)÷log(10)=4.8.
However, upon receipt of a 5th digit { 116 } the program assumption that all the prior digits convert to 010 becomes wrong, because while 000016 is 000010, the lengthening of the hexadecimal integer to 1000016 means that the decimal representation must be 6553610. The first 4 digits sent to computer B should have been { 610, 310, 510, 510 } and not { 010, 010, 010, 010 }, but this error was realized after the fact.
Going back to the code, the programmer ponders: how many digits of a string must I receive in base X before my program can convert the digits to base Y independently of any digits that come before or after? He figures out that this is an easy problem if he’s converting between bases with something in common like base-256 (28) to base-32 (25) or base-64 (26) or base-8 (23), but not when converting between bases like base-25 (52) to base-9 (32); not when log(original_base)÷log(new_base) is a irrational number.
Is there any method of converting integers from one base to another by digits independently or even groups of digits without knowing all the digits in advance, or have I already exhausted all the methods available? Base-85 encoding software seem to deal with the problem by chunking strings into groups of 32 binary digits, which map to 5 base-85 digits with a small overhead (the last 142,085,829 values of a 5-digit base-85 encoding do not map to any 32-digit binary value, but all 32-digit binary values have a base-85 representation).
(I do not come from a mathematical background, so please dumb it down for me.)