13,140,591 members (48,180 online)
alternative version

#### Stats

52.8K views
20 bookmarked
Posted 18 Oct 2006

# Base Conversion of Very Long Positive Integers

, 18 Oct 2006
 Rate this:
An algorithm to convert an integer from one base to another

## 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=ith 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:

```//Copyright Andrew Jonkers 2006-
//convert a positive integer in base:from  to another base (allowable bases from 2 to 36)
//the number can be any number of digits long
//input and output in string format
//(e.g. digits in base 2="0-1", base 16="0-F", base 20="0-J" etc
class BaseConverter
{
//Convert number in string representation from base:from to base:to.
//Return result as a string
public static String Convert(int from, int to, String s)
{
//Return error if input is empty
if (String.IsNullOrEmpty(s))
{
return ("Error: Nothing in Input String");
}
//only allow uppercase input characters in string
s = s.ToUpper();

//only do base 2 to base 36 (digit represented by characters 0-Z)"
if (from < 2 || from > 36 || to < 2 || to > 36)
{ return ("Base requested outside range"); }

//convert string to an array of integer digits representing number in base:from
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"); } //only allow 0-9 A-Z characters
}
}

//check the input for digits that exceed the allowable for base:from
foreach(int i in fs)
{
if (i >= from) { return ("Error: Not a valid number for this input base"); }
}

//find how many digits the output needs
int ol = il * (from / to+1);
int[] ts = new int[ol+10]; //assign accumulation array
int[] cums = new int[ol+10]; //assign the result array
ts[0] = 1; //initialize array with number 1

//evaluate the output
for (int i = 0; i < il; i++) //for each input digit
{
for (int j = 0; j < ol; j++) //add the input digit
// times (base:to from^i) to the output cumulator
{
cums[j] += ts[j] * fs[i];
int temp = cums[j];
int rem = 0;
int ip = j;
do // fix up any remainders in base:to
{
rem = temp / to;
cums[ip] = temp-rem*to; ip++;
cums[ip] += rem;
temp = cums[ip];
}
while (temp >=to);
}

//calculate the next power from^i) in base:to format
for (int j = 0; j < ol; j++)
{
ts[j] = ts[j] * from;
}
for(int j=0;j<ol;j++) //check for any remainders
{
int temp = ts[j];
int rem = 0;
int ip = j;
do  //fix up any remainders
{
rem = temp / to;
ts[ip] = temp - rem * to; ip++;
ts[ip] += rem;
temp = ts[ip];
}
while (temp >= to);
}
}

//convert the output to string format (digits 0,to-1 converted to 0-Z characters)
String sout = String.Empty; //initialize output string
bool first = false; //leading zero flag
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"; } //input was zero, return 0
//return the converted string
return sout;
}```

## History

• 18th October, 2006: Initial post

## Share

 Engineer Australia
I am a programmer with a degree in chemical engineering. I know my way around PLC's and real-time programming, and also develop visual studio applications in C#, C++, and specialsed engineering functions for use behind Excel. I have over 20 years experience in programming personal computers, PLC's, and industrial automation.

## You may also be interested in...

 First Prev Next
 Thanks for this, works great! Stevo Z17-Mar-12 4:04 Stevo Z 17-Mar-12 4:04
 Allowable bases from 2 to 64 Midax8-Dec-11 10:20 Midax 8-Dec-11 10:20
 output length computation : m.gcombes26-Mar-09 16:03 m.gcombes 26-Mar-09 16:03
 C++ Version plus some fixes. [modified] altera19-Nov-08 9:36 altera 19-Nov-08 9:36
 Nice work Member 394977916-Oct-08 4:12 Member 3949779 16-Oct-08 4:12
 A simple check for correctness on very large numbers VBWizard11-Apr-08 19:34 VBWizard 11-Apr-08 19:34
 C# code rplazzotta31-Mar-08 4:56 rplazzotta 31-Mar-08 4:56
 Re: C# code [modified] Jeltz12-Apr-08 7:09 Jeltz1 2-Apr-08 7:09
 A great help ! Black Horus18-Apr-07 8:41 Black Horus 18-Apr-07 8:41
 Very Dificalt NeO[LiG]27-Oct-06 20:49 NeO[LiG] 27-Oct-06 20:49
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Sep-17 1:19 Refresh 1