Integer Base Calculation in Reverse

December 1, 2009 11:29 AM

Math question: Converting a number to a different base is easy enough, but how do I convert it backwards if I already know the end result? In other words, if I know that the number in base 32 is "12", then what is the original number in letters and numbers?

By trial and error I find that the answer is "c". How is the answer calculated? What is the name for this calculation? I am coding in Ruby so it would be wonderful if someone knows of a shortcut already in that language.

posted by cmcmcm to technology (12 answers total)

What happens when you try to convert to base 10 (or whatever its original base may be)?
posted by valadil at 11:33 AM on December 1, 2009

I'm taking a guess on what's actually happening here:

The "C" you're referring to here is the hexadecimal (base 16) number. So C in hex is 12 in decimal (base 10) -- you count 8, 9, A (10), B (11), C (12).

In the general case, just remember that each column in your number represents the base to some power. So in base 10, 12 is 1 times 10 to the power of 1 (10) + 2 times 10 to the power of 0 (or one). 10 + 2 = 12. In base 32, 12 is 2 times 32 + 2, or 64 + 2 = 66. In general we humans work with base 10 numbers, although base 16 is very common in computing.

Is it possible that you're converting 12 from base 10 to base 16? That would explain 12 transforming into C. Base 32 is very uncommon, but you might be confusing this with a 32-bit binary number, which is very common in programming languages too.
posted by shaun at 11:36 AM on December 1, 2009

Unless you are talking about Base32, which is a number encoding system and not an actual integer base, which will then follow a completely different set of rules.
posted by shaun at 11:39 AM on December 1, 2009

Except of course I did the arithmetic incorrectly. "12" in base 32 is 1*32 + 2 = 34 in decimal. Sorry about the confusion.
posted by shaun at 11:46 AM on December 1, 2009

If I understand you correctly, you're saying that 12₁₀ = C₃₂, and you want to know how to do that, right?

The digits in base n go from 0 to n-1, so the digits in base 32 go from 0 to 31 (represented as T). Non-negative integers 31 or smaller become a single-digit number in base 32, so the conversion is pretty direct there. A₃₂=10₁₀, B₃₂=11₁₀, ... T₃₂=31₁₀.

To convert numbers larger than 31₁₀ to base 32, there are several possible algorithms; what I present below is just one of them.

Divide the number by 32, taking the remainder; the remainder corresponds to the rightmost digit of the number. Take the quotient and repeat the process for the next-rightmost digit, and continue until the quotient is less than 32, which corresponds to the leftmost digit.

Example: to convert 2009₁₀ to base 32: 2009 divided by 32 is 62 with a remainder of 25. 25 corresponds to O in base 32, so O is the rightmost digit. Now repeat the process with 62; 62 divided by 32 is 1, with a remainder of 30; 30 corresponds to S, so S is the next-rightmost digit. And 1 is less than 32, so 1 is the leftmost digit, and the process stops there. 2009₁₀=1SO₃₂.

(That's without addressing the question of why you'd want to convert to base 32, which, as shaun notes, is pretty uncommon as a base to work in.)
posted by DevilsAdvocate at 11:58 AM on December 1, 2009

Oh, and the term for this is simply "base conversion." This term applies to converting from base-10 and also converting to base-10 and also converting between two bases neither of which are base-10, because mathematically speaking, there is nothing special about base-10.
posted by DevilsAdvocate at 12:09 PM on December 1, 2009

As DevilsAdvocate said above, this type of conversion is called "base conversion" or "radix conversion" and the math is the same whether converting from base-10 to base-32, base-32 to base-10, or base 14 to base 19. This seems like a good overview:

http://www.deimel.org/comp_sci/conversion.htm

As for programming this, I have an implementation for the TI-89 calculator that could be used as an example. MeMail me if you're interested and I'll dig it up when I get home.
posted by waxboy at 12:23 PM on December 1, 2009

Argh, T is the 20th letter of the alphabet. I was thinking it was the 21st. The basic idea of my first comment is right, but some of the details are wrong. Digits go from 0 to U in base 32. 30 corresponds to T in base-32, and 2009₁₀=1TO₃₂.
posted by DevilsAdvocate at 12:29 PM on December 1, 2009

No, I'm still wrong. I should have just written out the entire base-10/base-32 conversion for digits from 10 to 31 in full to start with:

10-A
11-B
12-C
13-D
14-E
15-F
16-G
17-H
18-I
19-J
20-K
21-L
22-M
23-N
24-O
25-P
26-Q
27-R
28-S
29-T
30-U
31-V

Digits in base-32 go from 0 to V. 25 corresponds to P; 30 corresponds to U. 2009₁₀=1UP₃₂.
posted by DevilsAdvocate at 12:33 PM on December 1, 2009

12 in decimal would be represented as c in base-16 or base-32. I don't know what you mean by "the answer is c". As shaun points out, 12 in base-32 is 34 in decimal or 22 in base-16. I don't know of any base in which base-32 12 in would be represented as 'c'.
posted by mr_roboto at 12:35 PM on December 1, 2009

As usual, Ruby makes this easy.

irb(main):006:0> "MCMVIII".to_i 32
=> 24049076818
irb(main):007:0> 24049076818.to_s 32
=> "mcmviii"

(I was just being a smartass by choosing a base32 string that's also means something in Roman numerals. Ignore that.)
posted by Zed at 1:48 PM on December 1, 2009 [1 favorite]

Brute force is a fine way to what you want since the search space is tiny. A slight improvement would be to use a binary search. If you want to do it mathematically...

Suppose you have 3 digits, ABC and their value is x (base 10). You are searching for the base z. Then the equation you must solve is:

Az^2 + Bz + C = x

So it's a simple quadratic. If you have more digits you get into more general polynomial solving which means you might have been better off using the binary search I mentioned above.
posted by chairface at 4:41 PM on December 4, 2009