tomclegg.net |
Binary Posted April 29, 2001 Mostly Mozart is sponsored by Comfort and Joy, a unique children's store, and today's show is going to be about binary numbers, like 0... and 1. But first -- there's the matter of when to listen to Mostly Mozart. Get your pen and paper; this is going to be even more confusing than Mostly Mozart itself. If today is Sunday, then starting next week, you will have to listen at 3:00, one hour later than usual. If you're listening on Tuesday night, well, you must have taped my show because it's not being broadcast on Tuesdays any more. If you're listening on Thursday afternoon at 2:00, then congratulations, you caught the first ever Thursday episode of Mostly Mozart. So once again, starting this week you can hear Mostly Mozart at 2:00 every Thursday and 3:00 every Sunday. OK, got that? Good, then let's get on with the show. I've never been able to convince myself that computer science has anything to do with science. But it's called computer science, and I know something about it, so it does get the occasional spot on Mostly Mozart. Surely you've heard of binary numbers. If not, you've probably heard the term "bit" used as an abbreviation for "binary digit." You can't even go into a computer store without seeing all kinds of stuff about 56 kilobit modems, 100 megabit ethernet, and 64 bit graphics cards. One bit, one binary digit, is somewhere you can put either a zero or a one. You only have two choices, which is why it's called binary. Just like you've got two wheels on your bicycle, two different lenses on your bifocals, and two legs on yourself, since you're a biped. Before I get into any more detail, I'd like to refresh your memory about decimal numbers and decimal digits. There are ten decimal digits: 0 1 2 3 4 5 6 7 8 9. If you want to count past 9, you have to use two digits instead of one. Which ones, well, I hope you guessed "1 0." The 1 in the decimal number "1 0" is worth ten. To decimate is to reduce to one tenth; a decimetre is a tenth of a metre; a decahedron is a polygon with 10 sides; and a decanter is something entirely different. Aside from the fact that there are 10 decimal digits and only 2 binary digits, decimal and binary numbers work exactly the same way. You carry when you add, and borrow when you subtract; and you can do long multiplication and long division with binary numbers, just like you can with decimal numbers. Binary numbers represent the degenerate case: the simplest possible example. When you multiply decimal numbers, you have to know things like what is 8 times 9, and 7 times 6, and 3 times 8. When you multiply binary numbers, all you need to know is 0 times 0, 1 times 0, 0 times 1, and 1 times 1. And in case you're driving right now, I'll calculate those for you: they're all zero, except 1 times 1, which is 1. It is possible to count in unary, using only the digit "0". It goes something like this: 0; 00; 000; 0000; 00000; and so on. It's not very efficient. For example, my age in unary is 0000 0000 0000 0000 0000 0000 000. In binary, it's the much more manageable number 11011. And for those of you who are already counting with sixteen hexadecimal digits, it's just "1b." Which happens to be the ASCII code for "escape," and also 3 cubed. So in base 3 it would be 1000. But I digress. The 1 in decimal "1 0" is worth ten, because decimal means base 10. So if binary means base 2, you can probably guess what the 1 is worth in the binary number "1 0". We're going to have a short break and listen to some Mozart piano pieces, and then I'll tell you a bit more about the many and varied powers of 2. --- Comfort and Joy is happy to sponsor Mostly Mozart. On today's episode we are discovering the many and varied powers of 2. The powers of 2 are 1, 2, 4, 8, ....... and in case you're wondering, that list of numbers is the only part of the show that I didn't have to write down. Such is the power of 2. The tenth power of 2, which is 1024 in case you weren't taking notes, is close enough to 1000 that computer people use the prefix "kilo" to mean 1024. The twentieth power of two, 1,048,576, is pretty close to a million, so we use "megabit" to mean 2^{20} bits. Except hard disk manufacturers, who are the only people on earth who claim that a gigabyte is exactly 1 billion bytes. Earlier in the show I said my age in binary was 11011. That my age is 5 digits long might lead you to believe that binary numbers are inefficient. But it never gets any worse than that. It takes about 3.3 bits to represent one decimal digit. When you get past 10 digits, it doesn't really matter how many you have as long as you don't get any of them wrong. And that's why computers like binary numbers; because it's harder to get things wrong if you only have two choices. Telling zero and one apart can be a lot easier than telling 1 from 7, depending on your handwriting. Likewise, computers run on electricity, and they generally represent 1 and 0 as any voltage above or below a certain point. Positive voltages mean 1, negative voltages mean 0. This is far easier than measuring each digit against a scale of 10 different voltages. Perhaps you were amused that I know the first twenty powers of two off the top of my head. If so, you'll be even more amused if I tell you that 2^{24} is 16,777,216. 2^{32} is one I don't know off the top of my head, but I should, since so much stuff runs on 32 bits these days. It's usually enough to know that it's 4.294 billion. Which simply means that a 32 bit microprocessor can access 4 gigabytes of memory. It also means that if you choose a name from a phone book with 4 billion entries, then I can find that name in 32 guesses or less. Each time I guess a name, you have to give me one of three answers: too high, too low, or exactly right. I was thinking of doing this demonstration on the air, but in order to do that I need you to go and find your 2001 Better Book, pick a name, and phone me at 352-3706. So if you're listening on Sunday, go get your Better Book, and call me at 352-3706. Do it now, while I'm talking. The number again is 352-3706, and it's important that you call because otherwise I can't do my demonstration! The Better Book only has a few thousand names in it, not 4 billion, so I should need less than 20 guesses. The algorithm I'll use is called "binary search" because each time I guess, I eliminate half of the possible answers. When I start, I have the entire white pages section to choose from. So I'll guess somewhere in the middle, and depending on whether you tell me "too low" or "too high", I'll eliminate either the left or the right half of the book. That phone number again is 352-3706, and if you're listening on Sunday then calling me is mandatory. And if you don't call right now, I'll repeat what I said earlier about what time you can hear Mostly Mozart next week. All right, you asked for it... If today is Sunday, then starting next week, you will have to listen at 3:00, one hour later than usual. If you're listening on Tuesday night, well, you must have taped my show because it's not being broadcast on Tuesdays any more. If you're listening on Thursday afternoon at 2:00, then congratulations, you caught the first ever Thursday episode of Mostly Mozart. So once again, starting this week you can hear Mostly Mozart at 2:00 every Thursday and 3:00 every Sunday. --- So, you've chosen a secret name in the 2001 Better Book? Each time I give you a name, you have to tell me either "earlier" meaning that your secret name is earlier in the alphabet, or "later" if your secret name is later in the alphabet. I'll need no more than 20 guesses. (as it turned out, I got it on my 9th guess) |