2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ So, represent all your $d$'s and $b$ in radix $p$, and do all your arithmetic in base $p$. $\endgroup$ – J. M. is a poor mathematician Jul 11 '15 at 4:16
  • $\begingroup$ 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. $\endgroup$ – JonMark Perry Jul 11 '15 at 4:26
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ross Millikan Jul 11 '15 at 4:34
  • $\begingroup$ @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$. $\endgroup$ – Zev Chonoles Jul 11 '15 at 4:42
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jul 11 '15 at 4:46
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "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. $\endgroup$ – Potatoswatter Jul 11 '15 at 6:51
  • $\begingroup$ @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. $\endgroup$ – J. M. is a poor mathematician Jul 11 '15 at 6:56
  • $\begingroup$ @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) $\endgroup$ – JonMark Perry Jul 11 '15 at 7:02
  • $\begingroup$ @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. $\endgroup$ – Potatoswatter Jul 11 '15 at 7:08
  • $\begingroup$ @Potatoswatter; what do you mean by base 10? 1000? 995353? (btw this is my answer so you don't need to @ me) $\endgroup$ – JonMark Perry Jul 11 '15 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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