Base Conversion of Very Long Positive Integers

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:

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

• 18^th October, 2006: Initial post