If one has a number in radix $b$: $(d_nd_{n-1}\ldots d_0)_b$, and wants to change to radix $p$, how could one achieve that without passing from $b$ to $10$ and then from $10$ to $p$?

I thought I had solved it using the nested form of the number,i.e. $d_0 +b(d_{1}+b(d_{2}+b(\ldots)))$, and then changing radix from the inside, but I realised that this form of the number is in base $10$. Actually the definition is in base $10$: $$d_nb^n+\ldots+d_1b+d_0,$$

So I'm really having trouble with comming up with a solution to the problem of changing radix without using base $10$. Can you give me any hints? Thanks!

• So, represent all your $d$'s and $b$ in radix $p$, and do all your arithmetic in base $p$. – J. M. is a poor mathematician Jul 11 '15 at 4:16
• one main problem is that we think of $b^k$ in base 10, for example convert to binary, the columns are given by 1,2,4,8,16,32,... which is base 10. – JonMark Perry Jul 11 '15 at 4:26

There's nothing special about base ten, except our cultural familiarity with the digits $0 \dots 9$. The process for converting from base $a$ to base $b$ is the same as that of converting from base $a$ to base ten or base ten to base $b$.

Given a number $N_a$ in base $a$, one way to obtain $N_b$ in base $b$ is to repeatedly perform long division in base $a$.

First calculate $N_a \div b_a$, obtaining an integer part $\lfloor N \div b\rfloor_a$ and a remainder $(N \bmod b)$. The remainder is the one's place of the result in base $b$. Take the quotient and repeat the process of long division to obtain the next digit. Repeat until the dividend is zero.

That's the naive way, but it's a bit of work. Each long division requires one step per digit of $N_a$, and we need one division per digit of $N_b$. Each long division step involves several digits, specifically the length of the representation $b_a$. Since the number of digits is represented by the $\log_n$ function, the total work is $O\left( \log_a b \cdot \log_a N \cdot \log_b N \right) = O\left( \frac{\ln^2 N \cdot \ln b}{\ln^2 a \cdot \ln b} \right) = O\left( {\log_a}^2 N \right)$. In other words, it goes up quadratically with the length (in digits) of the original number, but it does not depend on $b$.

Other algorithms exist, but I'm not sure if any are better. If you can increase $b$ without difficulty, then you can convert first from base $a$ to base $c = b^n$, and then to base $b$, taking advantage of the fact that each digit in $c$ corresponds to a sequence of $n$ digits in base $b$. For example, computer programmers familiar with hexadecimal (base 16) will often deal with that instead of binary, since it's easier for the human brain. This doesn't represent a genuine reduction in complexity, though; it's really just shifted into the subtraction operations.

Numbers do not have a base; a given radix representation of a number does. For example, there is a certain number of dots below. $$\LARGE\bullet\quad \bullet\quad \bullet\quad \bullet\\ \LARGE\bullet\quad \bullet\quad \bullet\quad \bullet\\ \LARGE\bullet\quad \bullet\quad \bullet\quad \bullet$$ To adapt a section from Lockhart's Lament:

Twelve does not "start with a one" or "end with a two". Twelve itself doesn't start or end, it just is. (What does a pile of dots "start" with?) It is only the Hindu-Arabic decimal place-value representation of twelve that starts with a 1 and ends with a 2.

So you're incorrect when you say that $$d_nb^n+\ldots+d_1b+d_0$$ is "in base $10$", this is simply the number that the representation $(d_nd_{n-1}\ldots d_0)_b$ corresponds to. You many then proceed to divide this number by $p$, take the remainder and quotient, divide that quotient by $p$, etc. to get the representation of the number in base $p$, and all of this is done without any mention of $10$.

• So if I want to convert $132_8$ to base $7$, I divide $132_8/7=14_8$ remainder $6$, $14_8/7=1$ remainder $5$, so $132_8=156_7$. If you can do arithmetic in the bases you are fine. If not, go through base $10$. – Ross Millikan Jul 11 '15 at 4:34
• @Ross: Indeed, but when it comes to doing an actual computation the bases $b$ and $p$ are presumably given in a human-comfortable base (such as base $10$) so that when we are computing the number $$d_nb^n+\ldots+d_1b+d_0$$ we are doing so in a human-comfortable base (such as base $10$). My answer was more focused on describing abstractly what is necessary to convert from base $b$ to base $p$. – Zev Chonoles Jul 11 '15 at 4:42
• I didn't say it was the easy way. I did the computations in base $8$.I was just trying to give a concrete example to show one can convert between bases without going through base $10$ to support your answer. – Ross Millikan Jul 11 '15 at 4:46

In the general case, there is not much to be gained by not going through base $10$. We can use $mod$ to determine the necessary values, but this is effectively using base $10$ by proxy.

If the two bases are related, i.e. $b_1|b_2$ we can make some progress, but we hit the same problem as before with the $b_2/b_1$ being not nice.

If $b_1^k=b_2$ we can make rapid progress however. Each $b_2^x$ represents a sum of $b_1^y$'s, and so we can directly convert from one to the other. For example consider base $8$ to base $2$:

$6723_8 \to (110)(111)(010)(011)_2 \to 110111010011_2$

$1011011_2 \to (001)(011)(011)_2 \to 133_8$

If $b_1^j=b_2^k$ we can also make progress.

An example is to convert from base $8$ to base $4$. This line shows the first step, but is not the answer.

$574035_8 \to (22)(13)(20)(00)(12)(11)_4$

From the right-hand side, the method for determining the pairs alternates between the normal conversion of a digit $d_8\to d_4$ and converts double the digit, for example $5_8=11_4 \to 22$ in pair formation, and $7_8=13_4\to (26)\to 32$.

To convert we need to add pairs together starting from the right-hand side. This is because the 1 column in base $8$ spills into the 4 and 1 columns in base $4$. And the 8 column in base $8$ spills into the 16 and 4 columns in base $4$. And the 64 column in base $8$ spills into the 256 and 64 columns in base $4$. And so on. So $(12)(11)\to (131)$. That is every pair produces $3$ digits towards the answer, relative to the bases being $2^3$ and $2^2$. There are no carries because the sum parts consists of either $0$ or $2$ from the left pair, and $0$ or $1$ from the right pair.

$(22)(13)(20)(00)(12)(11)_4 \to (233)(200)(131)_4 \to 233200131_4$

To convert from base $4$ into base $8$ we reverse the process, which we can do because the middle digits from each triple is uniquely defined.

$32012_4 \to (032)(012) \to (02)(12)(00)(12) \to (01)(12)(00)(12) \to 1606_8$

halving alternate pairs.

• "We can use mod to determine the necessary values, but this is effectively using base 10 by proxy." … unless you don't use base 10. – Potatoswatter Jul 11 '15 at 6:51
• @Potato, I'm seeing how people can get confused; they think that the arithmetic with all the carrying and borrowing has to be done in decimal base when the same concepts exactly carry over to other bases. – J. M. is a poor mathematician Jul 11 '15 at 6:56
• @Potatoswatter; if you think more naturally in base 103...everything we do is in base 10 - i can't see how to avoid this (i bet you thought i meant base 28, i mean base 26) – JonMark Perry Jul 11 '15 at 7:02
• @JonMarkPerry Not everything we do is in base 10. The rules of place-value arithmetic are the same no matter the base. A good answer to this question should mention why place-value arithmetic is a good choice in the first place (efficient representation of numbers as a sequence of symbols from a finite set) and then present an algorithm for converting one place-value representation to another. – Potatoswatter Jul 11 '15 at 7:08
• @Potatoswatter; what do you mean by base 10? 1000? 995353? (btw this is my answer so you don't need to @ me) – JonMark Perry Jul 11 '15 at 7:10