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^{46} 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^{0} to 2^{11}. 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^{2} 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 |