Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 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?

share|improve this question
add comment

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
Confused. Did you just define $x$ to be two different things? How did I get $x$'s base $b$ representation? –  soandos Feb 20 '12 at 2:10
    
Oops I am thinking like a programmer. You repeat the procedure on $x//b$, where the $$//$$ means "integer divide (discard remainders)." –  ncmathsadist Feb 20 '12 at 2:16
    
Wait, how do I do this for a starting base $\neq10$? –  soandos Feb 20 '12 at 2:25
    
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. –  ncmathsadist Feb 20 '12 at 2:27
2  
Math Gems has a nice exposition below. BTW, +1 for you Math Gems. –  ncmathsadist Feb 20 '12 at 2:39
show 1 more comment

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

share|improve this answer
2  
Nifty colors! It is helpful to the exposition. –  ncmathsadist Feb 20 '12 at 2:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.