From: "Mark W. Eichin" <eichin@paycheck.cygnus.com>
Date: Sun, 20 Mar 94 14:59:30 PST
To: cypherpunks@toad.com
Subject: A Certain Monk at a certain village in Hanoi
In-Reply-To: <9403200625.AA10085@bsu-cs.bsu.edu>
Message-ID: <9403202149.AA06868@paycheck.cygnus.com>
MIME-Version: 1.0
Content-Type: text/plain



>> Of course this runs slowly and does tend to use a lot of storage.  
>> The stack really grows too large.  I'm hoping that it may be possible

That's just because it was an intuitive, but excruciatingly
inefficient, implementation. You can do towers of hanoi with *no*
stack, as long as you can loop (and even if you can't explicitly loop,
you can do it tail recursively, which this version isn't, and still
avoid using stack.) It's much harder to recognize that the code
relates to the problem... but if you treat the problem as "generate
this stream of numbers" it's not too hard to see how to do it.

The story behind the original "towers of hanoi" problem (three ivory
rods, 64 gold and silver disks) is amusing, though, in that it's an
example of using an "intractable" problem (moving the 64 rings by the
proper rules -- only stack on the immediate smaller size, only move
one at a time, and get the whole pile moved) to protect a "secret" (as
I've heard it, the world would be destroyed (or saved?) when the
operation was finished... perhaps the "secret" would be that it wasn't
going to work :-)

[how's that a desperate stretch for a cryptographic tie in?]

				_Mark_ <eichin@paycheck.cygnus.com>
				... just me at home ...