## Introduction

It is relatively straightforward to convert numbers up to 64 bits long (UInt64) between different bases using built-in modulus arithmetic in C#.

I had a need to convert numbers with thousands of digits between one base and another and I have written the `BaseConverter `

class to do this.

This code needs further comprehensive testing, but has appeared to work in all the cases I have required of it (where inputs are short enough to verify by other means). After all, how do you verify the correct result for thousands of digits? In practice, I worked up test cases from shorter to longer results, and checked against known correct results. You can also test it by back-converting from the output base back to the original base, but this only confirms the algorithm is symmetric, not correct. Limited cases for simple large numbers can also be checked directly with known results.

## Usage

String out_num=BaseConverter.Convert(Int32 frombase,Int32 tobase,String in_num);

The algorithm can convert a positive integer number, potentially thousands of digits long between any bases in the range from 2 to 36, including but not limited to binary, octal, decimal, hexadecimal.

The algorithm is implemented in a Visual Studio 2005 C# class with a single `static `

member function. An example call to convert a base16 (hexadecimal) number to base 2 (binary) is:

String sout=BaseConverter.Convert(16,2,"14AFE");

The answer is "`10100101011111110`

".

Another example to convert base 19 to base 7 is:

String sout=BaseConverter.Convert(19,7,"1IAHEB54638829348494387383AD12");

The answer is "`136615251021020315364261540624105412221316016`

".

## Inputs and Outputs

Because the number can be any number of digits long, I represent the input and output numbers in `String `

format. Each digit is in the range (0-Z), but of course the largest value for each digit must be less than base number for the input. So base 16 (hexadecimal) is represented by digits (0-F), base 10 by (0-9), base 2 by (0-1) and base 36 by (0-Z).

Finally, you must of course specify the base of the input number, and the required base of the output number, so the algorithm knows what conversion to apply!

## The Algorithm

The input number is converted from a `string `

to an array of integers, each array element representing a digit of the input number. The following procedure is then applied to each digit in the input number:

The power to which each digit is raised (frombase to the power of i, where i=i^{th} digit) is first calculated and converted to an integer array representation in the base of the output. Computational efficiency is gained by cumulating results from the lowest order digit to the highest order digit. (p[n]=p[n-1]*frombase). Any digits in this multiplication that are carried over to the next higher digit position are added in a recursive manner until all digits are represented by a tobase digit representation.

Each digit of the input is then multiplied by the power of this digit position and cumulated to the result. Any carry digits in the multiplication are again spread recursively into the higher order digits until all digits are valid in the output base format.

Once all the digits in the input string have been processed, the output result is converted from an integer array back to a string format.

## The Code

The code snippet to do this conversion is given below:

class BaseConverter
{
public static String Convert(int from, int to, String s)
{
if (String.IsNullOrEmpty(s))
{
return ("Error: Nothing in Input String");
}
s = s.ToUpper();
if (from < 2 || from > 36 || to < 2 || to > 36)
{ return ("Base requested outside range"); }
int il = s.Length;
int[] fs = new int[il];
int k = 0;
for (int i = s.Length - 1; i >= 0; i--)
{
if (s[i] >= '0' && s[i] <= '9') { fs[k++] = (int)(s[i] - '0'); }
else
{
if (s[i] >= 'A' && s[i] <= 'Z') { fs[k++] = 10 + (int)(s[i] - 'A'); }
else
{ return ("Error: Input string must only contain any of
0-9 or A-Z"); }
}
}
foreach(int i in fs)
{
if (i >= from) { return ("Error: Not a valid number for this input base"); }
}
int ol = il * (from / to+1);
int[] ts = new int[ol+10];
int[] cums = new int[ol+10];
ts[0] = 1;
for (int i = 0; i < il; i++)
{
for (int j = 0; j < ol; j++)
{
cums[j] += ts[j] * fs[i];
int temp = cums[j];
int rem = 0;
int ip = j;
do
{
rem = temp / to;
cums[ip] = temp-rem*to; ip++;
cums[ip] += rem;
temp = cums[ip];
}
while (temp >=to);
}
for (int j = 0; j < ol; j++)
{
ts[j] = ts[j] * from;
}
for(int j=0;j<ol;j++)
{
int temp = ts[j];
int rem = 0;
int ip = j;
do
{
rem = temp / to;
ts[ip] = temp - rem * to; ip++;
ts[ip] += rem;
temp = ts[ip];
}
while (temp >= to);
}
}
String sout = String.Empty;
bool first = false;
for (int i = ol ; i >= 0; i--)
{
if (cums[i] != 0) { first = true; }
if (!first) { continue; }
if (cums[i] < 10) { sout += (char)(cums[i] + '0'); }
else { sout += (char)(cums[i] + 'A'-10); }
}
if (String.IsNullOrEmpty(sout)) { return "0"; }
return sout;
}

## History

- 18
^{th} October, 2006: Initial post