Previous lecture

Table of contents

Next lecture

I reminded people of the three assignments currently open: "breaking RSA" and RSA communication (both on the web), and preparing the policy statements.

I was worried about the students' reception of Ms. Fefferman's possibly too technical lecture. I did ask them, "Why are you [students] here?" After some discussion, I asserted that it was to learn from maniacs, well, let us say cutting-edge researchers. I characterized Ms. Fefferman as one such, and said that it takes experience to disguise the excitement and enthusiasm that involvement in such a creative enterprise engenders. A young person generally can't dissimulate as well as an old codger.

So back to the the daily grind. I remarked that we were going to study how to count and how to do arithmetic. We were not going to discuss the important ethnographic ideas of doing this in different societies. For that I recommended The Universal History of Numbers by Georges Ifrah which has lots of material, especially on non-Western European cultures.

I recalled how we computed A⁴⁶ via a succession of squaring and multiplications by A to reduce the number of multiplications necessary. So I wrote this completely, then multiplied out the "nested" squarings and got 46 written as a sum of powers of 2. What information was contained in this? The facts that it was powers of 2 was easily understood. The presence or absence of specific powers of 2 was the important aspect. We could indicated such presence or absence by creating a list of 1's and 0's. This was another system of "positional notation" called the binary system. I wrote a list of powers of 2 on the board, from 2⁰ to 2¹¹. I asked the students write the number "81" (decimal) in binary. They did.

Then I started to discuss addition in binary. After seeing that the sum of 46 and 81 was 127, a rather special binary number, I switched to 83. We added 83 and 46 in binary, with special comments as to carrying. Then we multiplied 83 and 46 in binary, again being careful with the carries.

There were lots of questions, which I found quite agreeable. I remarked that this system was much easier to remember than decimal, because it had very simple addition and multiplication tables. Computers almost all use binary arithmetic -- the addition/multiplication "tables" are easy and small (not 10 by 10 as they are for decimal). I admitted that I was simplifying a bit (some computers may group binary digits together as "hexadecimal"). Historically, the first computer I programmed on actually used arithmetic close to decimal (it used BCD, binary coded decimal) and there have been computers built which used base 3, ternary.

The 0's and 1's are called "BITs", BInary digITs.

People further observed that numbers were longer in binary than in decimal, so some of the advantage of binary simplicity was lost in the disadvantage of having to deal with longer numbers. I asked, "How much longer?" For example, consider the number (written in decimal) 572,838. How many bits would its binary expansion have? I asked if the binary expansion could have 200,000 bits. I was told, "No," but there was some silence when I asked why this was so. Gradually we saw that 10 (ten, decimal) needed 4 bits, 10² might need 8, etc., so that the number above would likely need no more than 4 times 6 = 24 bits. Again, the discomfort of some students in manipulating exponents was nearly palpable.

I gave out some binary homework [PDF|PS|TeX].

Previous lecture

Table of contents

Next lecture