hwbehrens - 1 year ago 70
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?

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download