Converting numbers to another radix

• Download source - 2.75 Kb

Introduction

This article presents the Radix class that can be used to represent integer numbers in an arbitrary base.

Background

A few months ago, my friend Jack had an interesting mathematic question: 'Can you provide me with a pair of positive integers which, added together, is the reverse of the product of the two numbers?' Give it a try before reading on:

Some pairs were easily found:

0 + 0 = R(0 * 0)        0 = R(0)
2 + 2 = R(2 * 2)        4 = R(4)
24 + 3 = R(24 * 3)      27 = R(72)
...?

Are there more?

To make a long story short, I built an application to scan a subset of the integer range to know if there were certain patterns. Meanwhile, Jack derived a mathematical proof for the set of pairs that fulfilled the equation. There is an unlimited number of solutions. This proof is far too long to present here. Drop me a mail if you are interested.

We also investigated if there were more solutions and if the numbers would have an arbitrary number of zero's prefixed to it. There were even more solutions to this equation, as there emerged more patterns while scanning a part of the integer range. The next question was if there also existed solutions in other number bases, e.g., in base 2, 3, 4 et cetera. A quick scan through the documentation found no converters other than the Convert class:

Convert.ToString(Int32, Int32);

See the Convert class in MSDN. This method only supports base 2, 8, 10 and 16. As we wanted to explore other bases as well, it meant writing a new class which I called Radix.

How the Radix class works

The class has only static members, and the two most important calls are:

string Encode(long x, long radix);
void Decode(string val, long radix, out long rv);

With these two methods, all bases between 2 and 36 are supported. Bases lower than 10 don't use all digits, bases higher than 10 use additional capital characters. Base 11 uses the digits {0,..,9,A}, base 36 uses {0,..,9,A,..,Z}, and base 20 uses {0,..,9,A,..,J}.

As an example, to generate the first hundred numbers in base 13, one could use this loop:

for (int i=0; i<100; i++)
{
    Console.WriteLine(Radix.Encode(i,13));
}

The workhorse of the encoding function is a loop that does a remainder or modulo calculation. This remainder r is the digit that needs to be represented. For this, the digit array is used as a lookup table. Note that the return value string rv is built from back to front.

static string digit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
     ...
while (t > 0)
{
    // split of one digit
    long r = t % radix;
    // convert it and add it to the return string
    rv = digit[(int)r] + rv;
    t = (t-r)/radix;
}

Points of Interest

The Radix class is not tuned for performance and it is not tested for every possible value but it worked well for its purpose. Still there were two challenges, first, how to represent numbers in a base larger than 36, and second, how about doubles, can they be represented in any base too?

For the first problem, an array of numbers is used, which represents the factors for the powers of the radix. E.g., the number 123 is written as [(10),1,2,3] as it is 1 x 10^2 + 2 x 10^1 + 3 x 10^0. Similarly, the number 27 can be represented in base 4 as [(4),1,2,3] as it is 1 x 4^2 + 2 x 4^1 + 3 x 4^0. To handle symbolic versions of numbers, the encode and decode functions are overloaded.

For the second problem, how to represent doubles in other bases, I added encode and decode functions to the class. When a value is compared after a encode/decode step, they are not exactly the same, but this is quite common when comparing doubles as computers cannot represent them exactly. The usage is similar to the long encode/decode.

History

• 2005/12/10 - version 1.00 published on CodeProject.
• 2005/09/29 - started with the Radix class.