How to convert from any large arbitrary base to another

Question

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

For instance, converting "255" from the alphabet "0123456789" to the alphabet "0123456789ABCDEF" would result in "FF". One way to do this is to convert the input string into an integer, and then back again. Like so: (pseudocode)

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;
}

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

This works for small alphabets, but I’d like to be able to use base 26 (all the uppercase letters) or base 52 (uppercase and lowercase) or base 62 (uppercase, lowercase and digits), and values that are potentially over a hundred digits. The algorithm above would, theoretically, work for such alphabets, but, in practice, I’m running into integer overflow because the numbers get so big so fast when you start doing 62^100.

What I’m wondering is if there is an algorithm to do a conversion like this without having to keep up with such gigantic integers? Perhaps a way to begin the output of the result before the entire input string has been processed?

My intuition tells me that it might be possible, but my math skills are lacking. Any help would be appreciated.

There are a few similar questions here on StackOverflow, but none seem to be exactly what I'm looking for.

Answer 1

A general way to store numbers in an arbitrary base would be to store it as an array of integers. Minimally, a number would be denoted by a base and array of int (or short or long depending on the range of bases you want) representing different digits in that base.

Next, you need to implement multiplication in that arbitrary base.

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