How to convert from any large arbitrary base to another

Question

What Id like to do is convert a string from one "alphabet" to another, like converting numbers between bases, but more abstract and with arbitrary digits.

For example, converting “255” from the alphabet “0123456789” to the alphabet “0123456789ABCDEF” will result in “FF”. One way to do this is to convert the input string to an integer, and then back. For example: (pseudo code)

int decode(string input, string alphabet) { int value = 0; for(i = 0; i < input.length; i++) { int index = alphabet.indexOf(input[i]); value += index * pow(alphabet.length, input.length - i - 1); } return value; } string encode(int value, string alphabet) { string encoded = ""; while(value > 0) { int index = value % alphabet.length; encoded = alphabet[index] + encoded; value = floor(value / alphabet.length); } return encoded; } 

So decode("255", "0123456789") returns the integer 255, and encode(255, "0123456789ABCDEF") returns "FF" .

This works for small alphabets, but Id like to use base 26 (all uppercase letters) or base 52 (upper and lower case) or base 62 (upper case, lowercase and numbers) and values ​​that potentially exceed one hundred digits. The algorithm described above will theoretically work for such alphabets, but in practice Im works in integer overflows because the numbers get so big so fast when you start doing 62 ^ 100.

What is interesting to me if there is an algorithm for such a conversion without the need to support such giant integers? Perhaps a way to start outputting the result before processing the entire input string?

My intuition tells me that this is possible, but my math skills are missing. Any help would be appreciated.

There are several similar questions in StackOverflow, but none of them are what I'm looking for.

Answer 1

The general way to store numbers in an arbitrary database is to store it as an array of integers. The minimum number will be indicated by the base and the int array (either short or long, depending on the range of base ones you need), representing different numbers in this base.

Then you need to implement the multiplication in this arbitrary base.

After that, you can implement the conversion (clue: if x is the old base, calculate x, x ^ 2, x ^ 3, ... in the new base, then multiply the numbers from the old base by these numbers, respectively, and then add them )

Answer 2

There are algorithms that work "by numbers" and do not need integers that are too large. Take a look here .

Answer 3

Java-like pseudo-code:

 ArbitraryBaseNumber source = new ArbitraryBaseNumber(11,"103A"); ArbitraryBaseNumber target = new ArbitraryBaseNumber(3,"0"); for(int digit : base3Num.getDigitListAsIntegers()) { // [1,0,3,10] target.incrementBy(digit); if(not final digit) { target.multiplyBy(source.base); } } 

The problem that remains, of course, is to implement ArbitraryBaseNumber using the incrementBy(int) and multiplyBy(int) methods. In fact, you are doing in the code exactly what the student does when doing addition and long-term multiplication on paper. Google and you will find an example.