hwbehrens hwbehrens - 26 days ago 9
C++ Question

Exotic base conversion without an intermediate value?

I was just implementing an arbitrary base converter, and I had a moment of curiosity: is there a generalizable base conversion approach that works with any possible range of base inputs (excluding base 0), AND does not use an intermediate value in a more convenient base?

When writing a base conversion function, particularly one that goes from an arbitrary base to another arbitrary base, it can easily be implemented by first converting the number to decimal, and then re-converting it to the target number. You can also pretty easily bypass the intermediate value step arithmetically, provided you're in the range of base [1,10].

However, it seems to become trickier when you expand the range. Consider the following examples (primes seem like they might narrow the possible approaches a bit?):


  • base 7 to base 33

  • base -3 to base 13

  • base -16 to base 16



I didn't see much conversation about this question here, or elsewhere on Google; most either had a narrower range of bases or used an intermediate value. Any ideas?

Answer

The generalized algorithm to perform a base conversion of a value V with n digits in base B to an equivalent value V' in base B' is as follows:

Let d(0),d(1),...d(n-1) be the digits of V in base B. Using a translation table, we convert these digits to a sequence of digits d'(0),d'(1),...,d'(n) where each d'(i) is the original d(i) digit, but expressed in the new base B'

Then, V' is defined by:

V' = d'(0)*B^0 + d'(1)*B^1 + d'(2)*B^2+.....+d'(n-1)*B^(n-1)

Now here's the catch (and the reason you need an intermediate value): not only all values of the above formula have to be expressed in base B', but all the operations (addition and multiplication) have to be performed using aritmetic in base B'

For example: how to convert the number V = 201 expressed in base 3 to base 2 without converting it first to base 10.

The digits of V expressed in base 3 are d(0)=1, d(1)=0, d(2)=2 Converted to base 2, d'(0)=1, d'(1)=0, d'(2)=10 The original base is 3, but the general conversion formula need it to be expressed in the target base (2), so we'll use the value B=11 Then:

V' = d'(0)*B^0 + d'(1)*B^1 + d'(2)*B^2+.....+d'(n-1)*B^(n-1)

Putting values and operating in base 2

V' = 1 + 0 + 10*(11^2) = 1 + 10*11*11 = 1 + 10010 = 10011

So, 201(3 = 10011(2

Proof:

201(3 = 2*3^2 + 0 + 1 = 19
10011 = 1 + 2 + 16 = 19