Converting numbers between Number Bases

Question

I'm working on a program that converts between number bases. For example Octal is 8, decimal is 10. Letters A to Z could be considered as base 26.

I want to convert a number like "A" into 0, Z into 25, "AA" into 27 and "BA" into 53.

Before I start coding I'm doing it on paper so I understand the process. To start out I'm trying to convert 533 to base 26.

What algorithm is best for doing this?

Answer 1

Let's take a step back for a second, and look at decimal.

What does a number like "147" mean? Or rather, what do the characters '1', '4' and '7', when arranged like that, indicate?

There are ten digits in decimal, and after that, we add another digit to the left of the first, and so on as our number increases. So after "9" = 9*1, we get "10" = 1*10 + 0*1. So "147" is 1*10^2 + 4*10 + 7*1 = 147. Similarly, we can go backwards - 147/10^2 = 1, which maps to the character '1'. (147 % 10^2) / 10 = 4, which maps to the character '4'. And 147 % 10 = 7, which maps to the character '7'.

This works works for any base N - if we get the number 0, that maps to the first character in our set. The number 1 maps to the second character, and so on until the number N-1 maps to the last character in our set of digits.

Answer 2

What language are you writing this in? If you're doing this in Perl you can use the CPAN module Math::Fleximal that I wrote many years ago while I was bored. If you're using a language with infinite precision integers, then life becomes much easier. All you have to do is take characters, convert them into an array of integers, then do the calculation to turn that into a number.

Answer 3

You convert 20 and 13 to the symbols that represent 20 and 13 in your base 26 notation. It sounds like you are using the letters of the alphabet so, that would be UN (where A is 0 and Z is 25).

Answer 4

You need to assign a "digit" to each letter, like:

A =  0     N = 13
B =  1     O = 14
C =  2     P = 15
D =  3     Q = 16
E =  4     R = 17
F =  5     S = 18
G =  6     T = 19
H =  7     U = 20
I =  8     V = 21
J =  9     W = 22
K = 10     X = 23
L = 11     Y = 24
M = 12     Z = 25

Then, your {20,13} becomes UN.

Converting back is UN -> {20,13} -> (20 * 26 + 13) -> 52.

By way of further example, let's try the number 10163, just plucked out of the air at random.

Divide that by 26 until you get a number less than 26 (i.e., twice), and you get 15 with a fractional part of 0.03402366.

Multiply that by 26 and you get 0 with a fractional part of 0.88461516.

Multiply that by 26 and you get 23 (actually 22.99999416 on my calculator but, since the initial division was only two steps, we stop here - the very slight inaccuracy is due to the fact that the floating point numbers are being rounded).

So the "digits" are {15,0,23} which is the "number" PAX. Wow, what a coincidence?

To convert PAX back into decimal, its

 P * 262 + A * 261 + X * 260

or

  (15 * 676) + (0 * 26) + 23
= 10140      + 0        + 23
= 10163