Please feel free to share this newsletter with friends and colleagues.
Visit us here to subscribe
to this newsletter.
|
July 31, 2003 - - Volume 2, Number 7
Lance Armstrong, Ho Chi Minh, and Really Big Numbers
by Mark Altenbernd
Why Would I Want A Tour Of Hanoi?
Lance Armstrong has just won Le Tour de France for the fifth
time in a row, riding triumphantly into Paris, the home of La Tour
Eiffel, venturing nowhere near La Tour de Hanoi. Such is the contribution
of gender to language.
In 1883, the French mathematician Edouard Lucas invented
La Tour de Hanoi - the Tower Of Hanoi - a mathematical game based on
an old Hindu legend. In the legend, young monks were presented with 3
vertical spindles, one of which contained a stack of 64 gold disks, and
the other two of which were unoccupied. The disks were graduated in size,
with each one slightly smaller in diameter than the one immediately beneath
it - thus the largest disk was on the bottom, the smallest on the top.
The object of the game is to move all of the disks to one of the unoccupied
spindles, in the fewest moves possible, while maintaining the top-to-bottom
small-to-large order. There are only two rules: 1. A move involves transferring
a single disk from one spindle to another; and 2. No disk may ever rest
on top of a smaller disk. Seems simple enough, yeah? But the number of
moves required to transfer 64 disks is, quite literally, astronomical.
If the young monks worked steadily, efficiently, and without error, transferring
a disk every second, they would no longer be young when they completed
their task. In fact, they would be more than 580-billion years old. (Reflect
that the current age of the universe is estimated to be somewhere in
the neighborhood of 15-billion years.)
Care to try your hand at the game? This
French-language site -- http://javaboy.free.fr/tourdehanoi/ -- has perhaps the best of
several Internet-based implementations of La Tour de Hanoi. If you can
master
a minimal French vocabulary, comprising words such as "disks", "reset", "autosolve", "speed", "timer",
and "moves", you should be able to enjoy and learn from this
site. By the way, when Lucas specified the game, he reduced the number
of disks to just 8, requiring a minimum of 255 moves. At the javaboy
site mentioned above, you can choose the number of disks in a range of
3 to 12, requiring from 7 to 4095 moves.
Can you predict the minimal number of moves required for
a given number of disks? Yes, and the algorithm is remarkably simple:
(2-to-the-n) minus 1, where n is the number of disks to be transferred.
People with a nodding familiarity with computer architecture will recognize
a relationship between The Tower of Hanoi and digital computers. Most
contemporary desktop computers are based on a 32-bit data word, meaning
that a word can take on 2-to-the-32, or 4,295,967,296, different values
(those of us with geekal aspirations might refer to this as "4 gigavals".)
This is equivalent to saying that it would take at least 4,295,967,296
moves to transfer 32 disks in the Tower Of Hanoi game. With a 64-bit
data word, and there are computers with words of that size, the potential
number of values becomes 4-gigavals times 4-gigavals, or a number so
large that even geeks don't have a name for it. It's a very
large number, so large, in fact, that if you had a data word with a starting
value of 0 and you added one to it every second, it would take more than
580-billion years to fill the word to its maximal value.
And just for the record . . .
Since the early 1960s, most mainframe computers have been
designed with a 32-bit data word. For most business applications, that
has provided more than adequate range and precision for mathematical
expressions. Many scientific applications, however, require greater precision,
and so-called "scientific machines" typically have a wider
data word. Indeed the first Illiac computer, built for scientific research
at the University of Illinois in the 1950s, had a total memory size of
just 4000 words (as compared with millions of words commonly available
on today's low-end personal computers), but the size of those words
was 40 bits, offering 16 times the precision of 32-bit machines. By today's
standards, the machine was slow, cumbersome, and difficult to program.
But in the end it was much faster than hand calculation, and it provided
a very high order of accuracy.
The World's Most Powerful Computer, as the Cray X1 proudly
proclaims itself, offers programmers a choice of either 32-bit
or 64-bit computation. As a massively parallel processor,
it also offers up to 4,096 (2-to-the-12)
computers contained in 64 (2-to-the-6) water(H2O)-cooled
cabinets, all interconnected and working co-operatively on
shared memory. That memory
can be as large as 65,536 (2-to-the-16) giga(2-to-the-30)-bytes,
which is the same as 2-to-the-46 bytes, which is approximately
7.03687-times-10-to-the-13 bytes. (Geeks call that "one hell of
a lot of memory" and accountants
sometimes say that it is "overkill for Quickbooks".) The Cray
Supercomputer is a highly specialized machine, a parallel
processor, or vector processor, that is used for highly specialized
applications, such as weather system simulation and medical
research. On
its Web site,
Cray says: "Computational simulation is accepted today as the third
element of science, complementing theory and experimentation." If
you are interested in this kind of thing, it's worth a
visit to their site You would think that this is just about
the biggest, coolest thing there is in the world of computers
and computation.
But wait! There's more!
Way back in medieval times, before the ascent of the Plantagenets
and the Wars Of The Roses, back in the late 1970s, Intel
was designing its first general-purpose adult microprocessor, one that
could be more
than an embedded processor in a machine tool or robotic system.
The microprocessor was the 8086. Intel also gave it a runt brother, the
8088. The 8086 was
a full16-bit machine, having 16-bit registers and a 16-bit
data bus. The 8088 also had 16-bit registers but only an 8-bit bus, for
reasons
having to do with maintaining compatibility with external
devices, chiefly disk drives, that could work only with 8-bit buses.
(While a 16-bit register
ordinarily would permit the system to have just 64 kilobytes
- 2-to-the-16, or 65,536 - of memory, the Intel engineers used an amusing
ruse, known
as "segmented memory architecture", that permitted the system
to address a full one-megabyte (2-to-the-20) of RAM. Those
who have written assembly-language programs for the segmented memory
model understand
the bitter irony of the word "amusing".) Because of the much
wider availability of 8-bit peripherals, IBM chose the 8088
as the processor for its first Personal Computer in the early 1980s.
Even though the 808x computers could address a 20-bit address
space, its 16-bit registers limited it to an upper value of just 65,535,
and those were integer values only, completely insufficient even for
Quickbooks. Early language compilers worked around this limitation by
simulating large "real" numbers, those with a decimal point
and fractional portion, in software. But that expedient solution was
slow and limited in its accuracy, making the processor inadequate for
many important applications. In order that its new microprocessor family
should be able to grow among these other applications, Intel designed
a companion processor, or math co-processor (which it called the iAPX87
Numeric Data Processor, or NDP, but which was generally know as the 8087,
or simply the 87). Even the first IBM PC had a socket in the system board
to accept the NDP. When it was installed, real or floating-point computation
became instantly available on the computer, as long as the language compiler,
or the human assembly-language programmer, issued the correct floating-point
instructions.
The NDP had a stack of 8 internal registers in which all
computation took place. Data had to be loaded from memory into the registers,
but once there, computation was blindingly fast, since its hardware implementation
of the floating-point instruction set took the place of all of the slow
and painful software simulation of real numbers that was required without
the NDP. Speed increases could be several orders of magnitude, depending
on the nature of the application that was running.
But the really amazing thing about the NDP is that the stack
of internal registers all have a data format that Intel calls Temporary
Real. It has a data width of 80 bits - eight-oh - eighty - count 'em!
That's 65,536 (2-to-the-16 - is that number beginning to look familiar?)
times the accuracy of that crummy old 64-bit register, the one that could
count at a rate of one per second for the next 580-billion-plus years.
(Two-to-the-80. That's 38,010,880-billion, a number which has a
name, I suppose, but which, until now, I have never had the need to learn.
Let's see, that would be 38,010,880-billion, or 38,010.88 trillion,
or 38.01088 zillion, right?) Yikes! Why is that necessary? Well, the
point of the extra precision is to maintain accuracy of results across
many, many, many computations. The NDP was envisioned for computation-intensive
scientific applications. The extra bits are insurance against that old
bugaboo, Error Due To Rounding. That kind of insurance is important when
you are trying to do something like navigate a spacecraft across tens-of-millions
of miles and land it within a few hundred feet of its target on Mars.
Note that the 80-bit width is internal to the NDP only. When it stores
numbers back into RAM for further use by an application, it stores a
number not more than 64 bits wide, and possibly as narrow as only 16
bits.
As time passed, Intel designed successor processors: the
80286, the 80386, and the 80486, each faster, smaller, more powerful,
and less expensive than its predecessor. And each generation also had
an NDP: the 80287, 80387, and 80487. And interestingly, at some point
Intel decided to integrate the NDP into the base processor. That actually
happened with the 80486, but for misbegotten marketing reasons, there
were both a 486 with fully integrated NDP, and a 487 - don't ask.
So today your Intel-based machine, with a Pentium or related processor,
has an integrated NDP with a stack of 80-bit registers, offering far
greater range and precision than contemporary IBM mainframes or even
the Cray X1 Supercomputer. Right there, on your desk, in your lap.
So now, if you like, you can select one of those registers
and add one to it at the rate of 65,536 times per second, every second
for the next 580-billion-plus years. Although I wouldn't count on
anyone's being around to witness the completion. Except, of course, Lance
Armstrong.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
We can help
Believe it or not, this article is really about backing up
your computer systems and building for yourself a recoverable
environment .http://www.Altenbernd.Com/OurServices/RecoverableEnvironment.asp.
How could that be? Well, the Tower Of Hanoi provides an important
conceptual foundation for the efficient use of backup media
and the long-term archiving
of critical data. But media rotation is only one of a number
of issues attendant on the surprisingly complex issue of
creating a recoverable environment. To learn more about the
underlying issues and
how we can
help you address them, call us at (800) 557-7634. Or visit
our Web site to learn more about how we can help you plan,
implement, and manage an
effective backup strategy: http://www.Altenbernd.Com.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
Contact
Us