Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Base conversion
Posted:
Nov 6, 2000 5:07 PM


Thank you, very Interesting.
I think I found perhaps an easier method in the end. I convert to base 9 then convert to base 8. It's slightly tricky, but ok with some practice. The trick to the conversion is the fact that 1/9 = 0.111111... Here's how I do it for 237 :
2 2 3 5 1 7 12
In the above I keep a rolling sum in the second column (ie 2, 2+3, 2+3+7). Then repeatedly add any carries  with the proviso that any carries from the bottom row are both added to the previous row and the bottom row:
2 2 = 2 3 6 = 5 + 1 7 3 = 1 + 2
This gives the remainder (3) after dividing by 237 by 9. That would give the digit in the units column of the base 9 number. Then continue in this manner disregarding the remainder at each stage :
2 2  2 2  2 3 6  6 8  7 3 
The final base 9 figure is 283, which you can check by 3 + (8x9) + (81x2) = 237.
All you have then to do, is do exactly the same process again, but convert the base 9 number into base 8. It does mean you have to add base 9  but that's not too taxing. From base 8 you can easily get the binary number.
What do you think?
"William L. Bahn" <wbahn@uswest.net> wrote in message news://t0drevjggvcqb5@corp.supernews.com... > Do repeated division by 16. The remainder at each step is the next LSB in > hex notation. Converting from hex to binary is trivial. > > Dividing by a twodigit number by hand is quite a bit more involved for most > people than dividing by a singledigit number, so you can also divide by 8. > > For very large numbers, you can work in steps. Divide by 1024 (which is > fairly easy since it is very close to 1000 so you can take good guesses at > what each digit in the quotient is. Just remember that each remainder is 10 > bits. > > Example: > > Convert 8756733219 to binary > > 8756733219 / 1024 = 8551497r291 > 8551497 / 1024 = 8351r73 > 8351 / 1024 = 8r159 > 8 / 1024 = 0r8 > > So the binary representation is related to: > [8][159][73][291] > > Where each number in square brackets is written as a 10bit binary number. > > We then use the same procedure, only use a divisor of 8 or 16, to break > these down: > > 291 / 8 = 36r3 > 36 / 8 = 4r4 > 4 / 8 = 0r4 > > [291] = [(4)(4)(3)] > > Each number in () is in "octal" and is written as a 3bit value. The result > is left extended with zeros if necessary to get the full ten bits. If there > are 4 (), then the first one will be at most a (1) which will be written as > a onebit value (since the other none bits are already spoken for). > > 73 / 8 = 9r1 > 9 / 8 = 1r1 > 1 / 8 = 0r1 > > [73] = [(1)(1)(1)] > > 159 / 8 = 19r7 > 19 / 8 = 2r3 > 2 / 8 = 0r2 > > [159] = [(2)(3)(7)] > > 8 / 8 = 1r0 > 1 / 8 = 0r1 > > [8] = [(1)(0)] > > So we have: > > 8756733219 = [8][159][73][291] > = [(1)(0)][(2)(3)(7)][(1)(1)(1)][(4)(4)(3)] > > The conversion between octal and binary is straightforward: > > (0) => 000 > (1) => 001 > (2) => 010 > (3) => 011 > (4) => 100 > (5) => 101 > (6) => 110 > (7) => 111 > > 8756733219 = [(1)(0)][(2)(3)(7)][(1)(1)(1)][(4)(4)(3)] > = > [(001)(000)][(010)(011)(111)][(001)(001)(001)][(100)(100)(011)] > > Now all you have to do is remember to pad each set of ten bits to the full > ten bit width and you have your answer (leading zeros in the final result > can be left off): > > 8756733219 = > [0000(001)(000)][0(010)(011)(111)][0(001)(001)(001)][0(100)(100)(011)] > 8756733219 = 1000001001111100010010010100100011 > > > We can verify this very easily by breaking it into hex (groups of four bits) > starting from the right: > > 1000001001111100010010010100100011 > > 209F12523h (F in hex = 15 in decimal which is 1111 in binary) > > Now we can convert to decimal by starting with the left most digit. At each > step we multiply the result of the previous step by 16 and add the next > digit. > > 2*16+0 = 32 > 32*16+9 = 521 > 521*16+15 = 8351 > 8351*16+1 = 133617 > 133617*16+2 = 2137874 > 2137874*16+5 = 34205989 > 34205989*16+2 = 547295826 > 547295826*16+3 = 8756733219 > > Which is our initial value. > > The mathematical reasons why all of the above work is very straight forward > but can be a little subtle. Try to figure it out. In the process, you will > learn quite a bit about number bases and algorithm development. > > Guillermo Phillips wrote in message > <973441417.528.0.nnrp10.c2debf68@news.demon.co.uk>... > >Anyone know of an elegant method for converting the base 10 representation > >of a number into binary just using pencil and paper? > > > > >



