After the Decimal

This week, Dad asked me to find an algorithm for turning base 10 decimals into binary.  He's so annoying.

To review what binary is, we first need to review base 10.  We have a counting system called base 10, where we organize our things into piles of 10's using digits 0, 1, 2, 3, 4, 5, 6, 7, 8, & 9.  Once we get too many of those piles, we group 10 of them together and call them "hundreds."  And we organize those into bigger piles of 10 hundreds, and those are called "thousands."  This goes on for quite some time - enough to take care of our counting needs, anyway.  We stop understanding numbers easily by one million, which is why we haven't already started a revolution, despite the fact that one person in our country has a trillion dollars.

10³ - one thousand

10⁶ - one million

10⁹ - one billion

10¹² - one trillion
10¹⁵ - one quadrillion
10¹⁸ - one quintillion
10²¹ - one sextillion

10²⁴ - one septillion
10²⁷ - one octillion
10³⁰ - one nonillion
10³³ - one decillion

But the choice of the number "10" and the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, & 9 aren't based on some sort of universal truth, and in fact, they're a bit random.  Binary or base 2 is what we call it when we start organizing our things into piles of 2 instead.  We only need two digits when we do that, so we use 0 and 1.  We can group those piles of 2 into bigger piles of two 2's, and the unit 2² is like our hundreds unit.  The unit 2³ is like our thousands.

Let's explore the number: 111,111.

In base 10, that number means 1 pile of 10⁵ + 1 pile of 10⁴ + 1 pile of 10³ + 1 pile of 10² + 1 pile of 10¹ + 1 pile of 10⁰.  In base 2, it means 1 pile of 2⁵ + 1 pile of 2⁴ + 1 pile of 2³ + 1 pile of 2² + 1 pile of 2¹ + 1 pile of 2⁰.  (Notice that 10⁰ = 2⁰ = 1.)

Now consider this number: .111

In base 10, that's one tenth and one one-hundredth and one one-thousandth.

Another way to look at this is one 10^-1 + one 10^-2 + one 10^-3.

In base 2, that's one half and one fourth and one eighth, or one 2^-1 + one 2^-2 + one 2^-3.

So back to Dad's question.  Let's turn some long ugly number with a decimal into binary.

I'll choose 654.32̅1̅.

(If you were dying to convert an irrational number into binary and found yourself reading this post, I'm sorry to tell you that you'll have to round.  Life is full of disappointments, and you may as well get used to it now.)

The first step is to work on the part to the left of the decimal.

We can call that the before-the-decimal algorithm.

Divide 2 into the integer and write the remainder in the ones (2⁰) unit.

654/2 = 327 R 0

0.

That's the whole algorithm, so now we'll repeat it for the next unit to the left.

Divide 2 into the new number (327) and write the remainder into the 2's (2¹) unit.

327/2 = 163 R 1

10.

The next remainder goes into the 4's (2²) unit.

163/2 = 81 R 1

110.

8's (2³) unit.

81/2 = 40 R 1

1,110.

16's (2⁴) unit.

40/2 = 20 R 0

01,110.

32's (2⁵) unit.

20/2 = 10 R 0

001,110.

64's (2⁶) unit.

10/2 = 5 R 0

0,001,110.

128's (2⁷) unit.

5/2 = 2 R 1

10,001,110.

256's (2⁸) unit.

2/2 = 1 R 0

010,001,110.

512's (2⁹) unit.

2/1 = 0 R 1

1,010,001,110.

That takes care of the part before the decimal, but before we go on, we ought to check our work.

512 + 128 + 8 + 4 +  2 = 654

Now we turn our attention to the part after the decimal.

It is: .32̅1̅

Did you know that any repeating decimal can be expressed as a fraction?

Let's do that; I know a trick.

First, name your repeating decimal.  I'll call this one x.

x = .32̅1̅

Then multiply it by 10^whatever so you're set up to subtract and erase the repeating part.

100x = 32.12̅1̅

so

100x - x = 31.8

and

99x = 31.8

which means

x =  318/990 = 106/330 = 53/165

We're all ready to get started!

The after-the-decimal algorithm is quite similar to the before-the-decimal one.

We'll be working from the unit nearest the decimal and then moving to the right.

Multiply the fraction by 2.

If the result is ≥ 1, put a 1 in the halves (2^-1) unit, and if it is not, put in a 0.

Once the fraction becomes greater than 1, subtract 1 to find the new fraction.

We start with the 1/2's or (2^-1) unit with the fraction 53/165.

53*2/165 = 106/165 < 1

1,010,001,110.0

1/4's (2^-2) unit.

106*2/165 = 212/165 ≥ 1

1,010,001,110.01

1/8's (2^-3) unit.

47*2/165 = 94/165 < 1

1,010,001,110.010

1/16's (2^-4) unit.

94*2/165 = 188/165 ≥ 1

1,010,001,110.0101

1/32's (2^-5) unit.

23*2/165 = 46/165 < 1

1,010,001,110.01010

1/64's (2^-6) unit.

46*2/165 = 92/165 < 1

1,010,001,110.010100

1/128's (2^-7) unit.

92*2/165 = 184/165 ≥ 1

1,010,001,110.0101001

1/256's (2^-8) unit.

19*2/165 = 38/165 < 1

1,010,001,110.01010010

1/512's (2^-9) unit.

38*2/165 = 76/165 < 1

1,010,001,110.010100100

1/1024's (2^-10) unit.

76*2/165 = 152/165 < 1

1,010,001,110.0101001000

1/2048's (2^-11) unit.

152*2/165 = 304/165 ≥ 1

1,010,001,110.01010010001

That looks like a pretty good place to stop, so we can truncate and call it a day.

I would have stopped at the 1/512's (2^-9)  unit, but I thought I'd wait for the next 1 to lock in that 2,048th.

As Skeletor says, "Until we meet again!"