Converting between number systems without using mid-conversion

Question

I've searched a lot about this but I couldn't find any thread. Is there any tutorial, course or whatever that explains how to convert from any number system to some other number system (for example ternary to binary or base-7 to base-15 or any combination)? The reason I'm asking is because on the test that I have coming up, you can be asked to convert from any number system to another WITHOUT converting to decimal system in between. So, is there a universal algorithm or a few algorithms universal for specific cases? Or is there a different algorithm for every single combination? I already know how to convert some of the most used systems, for example binary to hex or hex to octal or octal to binary etc; but things that confuse me are those examples that I've given which use ternary or base-4 or anything else. In addition to this, I've tried searching for specific cases but all I get are algorithms with mid-conversion to decimal, and I can't use that. So, does anyone have any resource they might share? Thanks in advance.

Answer 1

There are two basic methods to find the radix expansion of a positive integer. In the first method you need to repeatedly divide by the target radix keeping track of the remainders as digits. In the second method you assume that you have a representation of it in a source radix and you repeatedly multiply by the source radix and add digits while doing the arithmetic in the target radix.

An example may help make this clear. Suppose $A=13$ and we want the binary expansion. We repeatedly divide by $2$ and use the remainders to build up the binary expansion giving $A=1101_2.$ Now suppose we want the ternary expansion of this using base $3$ arithmetic. We build up the number using the source radix $2$ which is the reverse of the process which got the expansion.

$$A_0 = 0,\; A_1=2\cdot A_0+1,\ A_2=2\cdot A_1+1,\ A_3=2\cdot A_2+0,\ A_4=2\cdot A_3+1=13.$$

Doing the same arithmetic in base 3 the computation is

$$A_0\! =\! 0_3,A_1\!=\!2\!\cdot\! 0_3\!+\!1\!=\!1_3, A_2\!=\!2\!\cdot\!1_3\!+\!1=10_3,A_3=2\!\cdot\!10_3\!+\!0=20_3,A_4=2\!\cdot\! 20_3\!+\!1=111_3.$$

which gives the correct answer as it should.

There are other variations on the first method which are more general in that they work for more general number representation systems, but I don't want to confuse you with the details of them.