Changing a number between arbitrary bases
As an intro, I know how the numbers are represented, how to do it if I can calculate powers of the base, and then move between base $m$ to base $10$ to base $n$. I feel that this is overly "clunky" though, and would like to do it in such a way that the following conditions are met:
- No need to calculate the powers of the base explicitly
- No need for intermediate storage (i.e. no conversion to base ten required if base ten is not one of the bases)
I am pretty sure that the only operations that I strictly need to use are modulo, division and concatenation, but I can't seem to figure it out.
Any pointers?
$\endgroup$3 Answers
$\begingroup$Let $x$ be a number. Then if $b$ is any base, $x \% b$ ($x$ mod $b$) is the last digit of $x$'s base-$b$ representation. Now integer-divide $x$ by $b$ to amputate the last digit.
Repeat and this procedure yields the digits of $x$ from least significant to most. It begins "little end first."
EDIT: Here is an example to make things clear.
Let $x = 45$ and $b = 3$.
x x mod 3
45 0
15 0 (integer divide x by 3) 5 2 1 1We see that $45 = 1200_3$. Read up the last column to get the base-3 expansion you seek. Let us check.
$$1\cdot 3^3 + 2\cdot 3^2 + 0 + 0 = 27 + 18 = 45.$$
I hope this helps you.
$\endgroup$ 6 $\begingroup$You can perform base conversion directly by representing radix notation in horner (nested) form. Let's work a simply example. We convert $\:1213_{\:6}\:$ from radix $6$ to radix $8$
$$ 1{\color{red}2}{\color{blue}1}{\color{orange}3}_{\:6}\ =\ ((1\cdot 6+{\color{red}2})\:6+{\color{blue}1})\:6 + {\color{orange}3}$$
Now perform the computation inside-out in radix $8$:
$$ 1\cdot 6+ {\color{red}2} = 10)\: 6 = 60) + {\color{blue}1}) = 61)\: 6 = 446) + {\color{orange}3} = 451$$
Hence $\:1213_{\:\!6} = 451_{8}$
$\endgroup$ 4 $\begingroup$To convert from one base to another is pretty simple and will work for any base:
value = 1024
base 2: log 1024 / log 2 = 10 ; 2 ^ 10 = 1024 base = 10 ^ ( log 1024 / 10 ) = 2
base 10: log 1024 / log 10 = 3.0103 ; 10 ^ 3.0103 = 1024 base = 10 ^ ( log 1024 / 3.0103 ) = 10
base 6: log 1024 / log 6 = 3.8685 ; 6 ^ 3.8685 = 1024 base = 10 ^ ( log 1024 / 3.8685 ) = 6
base x: log VALUE / log x = y ; x ^ y = VALUE x = 10 ^ ( log VALUE / y )To do this in C++ :
#include <stdio.h> /* printf */
#include <math.h> /* log10 */
int main ()
{ double result; result = log10 (1024) / log10 (2); printf ("log10 (1024) / log10 (2) = %f\n", result ); printf ("2 ^ %f = %f\n", result, 2.0 ^ result ); return 0;
}
