Change of radix without using radix 10 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!
 A: 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$.
A: 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.
