Tuesday, October 23, 2007

Elizabeth does mathematics

Over the years, my daughter, Elizabeth, has shared with me an interest in mathematics. Here is a republishing of a discovery of hers. Mathematics is not just about solving problems set by other people. It is also about discovery and invention.

On March 11, 2002, Elizabeth discovered that the difference between two [consecutive] square numbers is the sum of their square roots.

Another way of looking at this is:

(x + 1)2 = x2 + 2x + 1 = x2 + (x + (x + 1))

This can be generalized:

(x + k)2 = x2 + 2kx + k2 = x2 + k(x + (x + k))

In particular, if x=48 and k=4, we get:

522 = (48 + 4)2 = 482 + 4(48 + (48 + 4)) = 2304 + 4(100) = 2704

Another way of looking at this is geometrically:

As a practical example, we know that 202 is 400.

So, what is 252?

By Elizabeth's law, the difference between the two squares must be 5 (that is, 25-20) times their sum.

In other words, 25 squared must be 400 + 5(20 + 25).

Regrouping, this is 400 + 5 x 20 + 5 x 25.

So, 252 is 400 + 100 + 125 = 625.

Fun, huh?

Just noticed that another way of writing this is: 400 + (25-20)(25+20), which has a kind of pleasing symmetry.

Thursday, October 18, 2007

Powers of two

Several years ago, when memory sizes were measured in Kilobytes and hard drive capacity in Megabytes, I came up with this trick for knowing the powers of two.

As an aside, my first personal computer (an Apple ][, acquired in 1979) came with 4K bytes of memory and no disk drive at all (a cassette tape interface was all there was for storage). I spent a couple of hundred dollars to upgrade the memory to 16K bytes. My first IBM-compatible PC (1988) had 256K (bytes) of memory and a 20Mbyte hard drive. How times have changed!

The (Intel) processor in an IBM PC could only use 16 bits to form a memory address. It turns out that this is enough capacity for there to be a unique address for each of 64 Kilobytes (about 64 thousand bytes).

Each bit can have only one of two possible values, typically written as zero or one. Here is a little table showing how many different bit combinations there are for different numbers of bits:

1 bit gives you two possible values (0 and 1)
2 bits give you four possible values (00, 01, 11 and 10)
3 bits give you eight possible values (000, 001, 011, 010, 110, 111, 101 and 100)
and so on

In each case, I have been able to show all of the possible bit patterns. But the number of possible bit patterns doubles each time we add on an additional bit. The numbers get big quite quickly, and it would soon become very tedious to write out all of the possible bit patterns.

Mathematicians would express this relationship--number of bits and the number of possible bit patterns--using powers of two. The sidebar shows a chart from 0 bits through 9 bits.

You'll recognize three of these lines from the earlier table (showing 2, 4 and 8 possible values, for 1, 2 and 3 bits, respectively).

Above those lines, there is a bit of an oddity for zero bits, allowing only one pattern.

Now, if you want to learn my little memory trick, you will have to memorize these ten lines. This effort will be well repaid, as this will allow you to mentally state memory or disk sizes from the smallest to the largest in use today.

Where things get interesting is at 10 bits, which allow us to produce 1024 possible bit patterns.

What is interesting about this is that 1024 is the number commonly known as "Kilo". And, this is really quite close to one thousand.

Now, the power of 2, as represented by the exponent--the number shown attached to the upper right hand corner of the 2--can be interpreted as the number of bits that we have available for producing possible bit patterns. The other number--after the equals sign--is the number of possible bit patterns.

If you've studied powers and exponents, you'll know that you can add exponents (on the left) by multiplying numbers on the right of the equal sign. So, for example 2 to the 16 will be equal to 1024 (2 to the power 10) times 64 (2 to the power 6). This yields the number 65536, but which is more commonly expressed as 64K.

This is just another way of saying that 16 bits allow us to have a distinct address (bit pattern) for each of 64 Kilobytes. This is approximately 64 thousand bit patterns, because 2 to the power 10 is approximately one thousand. Similar approximations hold for 2 raised to 20, 30, 40, etc.

As it happens, 10 bits allow us about a thousand possible bit patterns, 20 bits allow about a million possible bit patterns, 30 bits allow about a billion possible bit patterns, and so on.

Now we are ready for the trick. When you have some number of bits (between none and 69), you can combine what you know from these two figures.

Let's try a few examples. If you have 24 bits, that would be about 16 million possible bit patterns. The "16" comes from the first figure, where 2 raised to 4 gives us 16. The "million" comes from the second table where 2 raised to 20 gives us about a million. Of course, 24 is just 4+20, so the law of exponents will be satisfied. This is also written "16M" or "16 megs" or "16 megabytes".

If you have 32 bits, that would be about 4 billion possible bit patterns. This is also written 4G, or "4 gigs" or "4 gigabytes".

Now, what if you have 64 bits? Would that be twice as many possible bit patterns as 32 bits? No, 64 bits would be about 16 thousand quadrillion possible bit patterns.

It works the other way, too. How many bits would you need for twice as many bit patterns as you get from 32 bits? Well, 32 bits gives us about 4 billion patterns, so we need about 8 billion bit patterns. Using the two figures, we can see that it will take 33 bits to give us about 8 billion bit patterns.

Did anyone actually get this far? Hope you find this useful.