Convert numbers from one base to another using repeated divisions.

Question

I have a homework assignment for my programming class to implement an algorithm that can convert from bases 2 trough 16 to any other base from 2 trough 16 but with a few twists.

What I need to understand though is how do I convert from a greater base to a lesser one (ex: 16 - 5 / 12 - 4) using repeated divisions. I would prefer if the examples have un-natural bases (so no decimal and no quick conversions 2-4-6-8-16).

I simply don't understand how this works so I'd appreciate a very basic explanation (dumbed down as much as possible)

I also don't need very general explanations(at first any way) but rather a very detailed step by step example.

I tried 156 (base 16) to base 10 but I know I didn't do it right: 156 / 10 = 15 r6 15 / 10 = 1 r5 1 / 10 = 0 r1 but result should be 324 not 651 (what I got) soooo what am I doing wrong ? (I'm guessing everything)

or is it something like this ??? 156 / 10 = 0 r1 (using just first number) => 1*16+5= 21 (which then has or doesn't have to be converted to base 16 ???) 21 / 10 = 2 r1 6 / 10 = 0 r6 and this would give me 620 but not 342.

I am just 100% confused, have no idea what is going on.

Answer 1

Here are a couple of examples, the first with almost full detail, the second with less.

First I’ll convert $156_{16}$ to base ten using repeated division in base sixteen. I’ll use $A,B,C,D,E$, and $F$ for the base sixteen digits corresponding to base ten $10,11,12,13,14$, and $15$. I’ll also use a subscript $s=16$ to indicate that a number is to be interpreted in base sixteen.

Divide $156_s$ by $A_s$. Do this just as you would in base ten: $A_s$ won’t go into $1_s$, but it will go into $15_s$. In fact $15_s=1\cdot 16+5=21$, and $A_s=10$, so it goes twice. The first digit of your quotient is $2_s$, so you need to subtract $2_s\cdot A_s$ from $15_s$.

$2_s\cdot A_s=2\cdot 10=20=1\cdot16+4=14_s$, and $15_s-14_s=1_s$, so after you bring down the $6_s$, you’re left dividing $A_s$ into $16_s$.

Similarly, $16_s=1\cdot 16+6=22$, so $A_s$ goes in twice. After you repeat the previous step (with suitable minor modifications) you have your full quotient $22_s$ and overall remainder $2_s$, as shown below.

$$\begin{array}{} &&&2&2\\ &&\text{_}&\text{_}&\text{_}\\ A&)&1&5&6\\ &&1&4\\ &&-&-&-\\ &&&1&6\\ &&&1&4\\ &&&-&-\\ &&&&\color{red}2 \end{array}$$

Now divide $22_s$ by $A_s$. $22_s=2\cdot 16+2=34$, so the integer part of the quotient is $3_s$:

$$\begin{array}{} &&&3\\ &&\text{_}&\text{_}\\ A&)&2&2\\ &&1&E\\ &&-&-\\ &&&\color{red}4\\ \end{array}$$

Finally, divide this last quotient, $3_s$, by $A_s$:

$$\begin{array}{} &&0\\ &&\text{_}\\ A&)&3\\ &&0\\ &&-\\ &&\color{red}3\\ \end{array}$$

Read off the red remainders in reverse order: $156_s=342$.

---

Here’s one a little more complicated, the conversion of $2BA_s$ to base three.

$$\begin{array}{ccccc|cccc|cccc|cccc|ccc} &&&E&8&&&4&D&&&1&9&&&&8&&&\color{red}2\\ &&\text{_}&\text{_}&\text{_}&&&\text{_}&\text{_}&&&\text{_}&\text{_}&&&\text{_}&\text{_}&&&\text{_}\\ 3&)&2&B&A&3&)&E&8&3&)&4&D&3&)&1&9&3&)&8\\ &&2&A&&&&C&&&&3&&&&1&8&&&6\\ &&-&-&-&&&-&-&&&-&-&&&-&-&&&-\\ &&&1&A&&&2&8&&&1&D&&&&\color{red}1&&&\color{red}2\\ &&&1&8&&&2&7&&&1&B\\ &&&&-&&&-&-&&&-&-\\ &&&&\color{red}2&&&&\color{red}1&&&&\color{red}2 \end{array}$$

That last quotient of $2$ is less than the divisor, so the next division will have a $0$ quotient and remainder of $\color{red}2$, so I’ve skipped the step and colored the quotient instead. Reading the remainders in reverse order, we have $2BA_s=221212_t$ (where the subscript $t$ indicates base three).

Check: $$2BA_s=2\cdot 256+11\cdot16+10=698\;,$$ and $$221212_t=2\cdot 243+2\cdot81+1\cdot27+2\cdot9+1\cdot3+2=698\;.$$

Answer 2

I agree with your comment that it is easiest to, as an intermediary, convert to decimal. Note the Wikipedia link that comments on the difficulty of directly converting between two bases that aren't decimal. Computationally, as long as you don't use a recursive algorithm, the conversion should be fast enough that "inelegance" doesn't mean "slowness".

So, convert to decimal first. Reducing to a solved problem is always a good way to do.

Hope that helps, Mike

Answer 3

the issue you have is that $156_{16}/10_{10}\neq 15_{16} \ r6$ but $156_{16}/A_{16} = 22_{16} \ r2$

edit: if we do the long division: ($A_{16}*2 = A_{16}+A_{16} = (A_{16}+ 6_{16}) + 4_{16} = 10_{16} + 4_{16}=14_{16}$)

1 5 6 | A
1 4   | 22
  1 6 |
  1 4
    2

now you just have to memorize the multiplication tables of 1 through 16 in base 16 to do this rapidly

Answer 4

Uh, okay, I think I see the problem: you're seriously mixing up your bases, as well as the order of digits. So for clarity I'll use the standard notation: anytime I mean a base-16 number I'll preface it with 0x (for example 0x42, 0x7A, etc.) and otherwise you can assume I mean base 10.

So let's convert 0x156 into base 10. What you did was actually a conversion from base 16 to base 16:
0x156/0x10=0x15 r 0x6 (this gives you the lowest digit, not the highest)
0x15/0x10=0x1 r 0x5
0x1/0x10=0x0 r 0x1
When you put these three digits together you get 0x156 (not 0x651) which, unsurprisingly, is what you started with. Now let's do a correct conversion to base 10. Note that 10=0xA, so we get (as I encourage you to check):
0x156/0xA=0x22 r 0x2
0x22/0xA=0x3 r 0x4
0x3/0xA=0x0 r 0x3
so there's our answer: 342.

Complications will arise when converting from one base to a significantly smaller base (for example, base 16 to base 5) but this should at least get you started on the right track.