Say we encode the string $BCA$ in the following way: \begin{align*}BCA &= 2 \times 26^2 + 3 \times 26^1 + 1 \times 26^0 \\ &= 1456 \end{align*} Is it possible to get back to the string $BCA$, given only the number $1456$?
Factoring a number to get an encoded string
2 Answers
Yes, it is possible as Mark has shown you one way to get the string digits from the least significant (that is getting $A$ first then $C$ and then $B$ finally).
But you have to be careful in using this method of encoding, because you are using base $26$, the number could be large if you are dealing with say strings of length $10$.
Another way to get back the strings is by calculating
$ \left \lfloor log_{26} 1432 \right \rfloor = 2 $
This tells you that the highest power of $26$ is $2$.
Start dividing by $26^2$ to get the most significant digit, i.e.
$ \left \lfloor \frac{1431}{26^2} \right \rfloor = 2 \tag{1}$
and from $(1)$ you know that most significant digit is $B$. The remaining number is
$ 1431 - 2 \times 26^2 = 1431 - 1352 = 79$
To find the next significant digit
$ \left \lfloor log_{26} 79 \right \rfloor = 1 $
and
$ 79 = \bf{3} \times 26 + \bf{1}$
Therefore you get the digits from the most significant to least as $B$, $C$ and $A$.
Yes. (But note that 1456 is not correct; $2\cdot26^2 + 3\cdot26 + 1 = 1431$, not $1456$.)
First, divide your number, 1431, by 26, giving quotient, 55, and a remainder, 1. The remainder of 1 means that the last letter is A
.
Now divide the quotient 55 by 26, giving a quotient of 2 and a remainder of 3. The remainder, 3, says that the next-to-last letter is C
.
Finally, divide the quotient 2 by 26, giving a quotient of 0 and a remainder of 2. This says that the next previous letter is B
.
Now the quotient is 0, so we are done.
-
0Decoding algorithms in general has to work both ways (left to right or right to left). Instead of re-inventing a new algorithm one could also use Base-32. (http://stackoverflow.com/questions/641361/base32-decoding) – 2012-05-10