20
$\begingroup$

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:

  1. No need to calculate the powers of the base explicitly
  2. 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?

3 Answers 3

28

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    1 

We 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.

  • 0
    Confused. Did you just define $x$ to be two different things? How did I get $x$'s base $b$ representation?2012-02-20
  • 0
    Oops I am thinking like a programmer. You repeat the procedure on $x//b$, where the $$//$$ means "integer divide (discard remainders)."2012-02-20
  • 0
    Wait, how do I do this for a starting base $\neq10$?2012-02-20
  • 0
    This procedure works regardless of base; however arithmetic must be executed in that base. If you come from the planet Tridigia where homonids have three fingers on each hand and work in Base 6, they would proceed in the same way, using base 6 arithmetic. This is base-invariant. Try the exercise of doing it in another base to convince yourself.2012-02-20
  • 0
    Got it, have to do the modulo in the original base. Didn't realize, sorry.2012-02-20
  • 2
    Math Gems has a nice exposition below. BTW, +1 for you Math Gems.2012-02-20
19

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

  • 4
    Nifty colors! It is helpful to the exposition.2012-02-20
  • 4
    For those of you who are slow like me the 1 * 6 + 2 = 10 means 10 in radix 8 so 8 in radix 10 ... man im slow sometimes.2017-07-05
0

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++ : http://www.cplusplus.com/reference/cmath/log10/

#include       /* printf */ #include        /* 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; } 
  • 1
    If I read this right, all you did is check how many digits an arbitrary number would have in an arbitrary base. For instance, 1024 in base 6 will need ceil(3.8) = 4 digits. 1024 in base 6 is 4424.2017-12-16
  • 0
    v = value; b = basis; p = floor(log(v)/log(b)) = exponent; d = floor(v/b^p) = digit; v -> v - d * b ^ p; for each new digit, update p, d and v, until, in case of integers, v = 0. However, this same scheme actually works for any v>0 and any b>0 except for 1. If you want to actually write it out as a string, though, it's a little more complicated. Gotta be careful to add 0s and the decimal point in appropriate places. And with reals, it's not necessarily gonna converge to v=0, so then you'll have to specify some cutoff precision.2017-12-16
  • 0
    I just used the change of base formula: http://www.mathwords.com/c/change_of_base_formula.htm log2 1024 = log10 1024/log10 2 = 10; 2^10 =1024 (bin: 1 with 8 0's) log2 2048 = log10 2048/log10 2 = 11; 2^11 = 2^10 + 2^10 = 2(1024)=2048 (bin: 1 with 9 0's) log2 1448.155 = log10 1448.155/log10 2= ~10.5 = (2^10)(2^0.5) =1448.155 (bin: 10110101000) = 2^3+2^5+2^7+2^8+2^10=1448 Using this formula is how you represent a number in an arbitrary base. For example: 2^A = 1024; A=log10 1024/ log10 2=10 B^C = 1024; B=10^((log10 C)/C)=2 (It's just basic algebra)2018-04-03