Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Base conversion
Replies: 9   Last Post: Nov 15, 2000 12:42 PM

 Messages: [ Previous | Next ]
 Guillermo Phillips Posts: 37 Registered: 12/8/04
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 two-digit number by hand is quite a bit more involved for

most
> people than dividing by a single-digit 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 10-bit 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 3-bit 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 one-bit 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
> 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:
>
> 10|0000|1001|1111|0001|0010|0101|0010|0011
>
> 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.nnrp-10.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?
> >
> >

>

Date Subject Author
11/5/00 Guillermo Phillips
11/5/00 Randy Poe
11/6/00 William L. Bahn
11/6/00 Guillermo Phillips
11/6/00 Lynn Killingbeck
11/6/00 Rolf Kleinknecht
11/6/00 a14a
11/7/00 Steve Lord
11/9/00 David Turner
11/15/00 Siegbert Steinlechner