hwbehrens - 6 months ago 32

C++ Question

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
```