Monday, August 10, 2009

Towers of Hanoi

The Towers of Hanoi is a classical computer science problem to demonstrate recursivity. Both how it can help by being the simplest solution, and how it can hurt by massively sucking resources. Recursive programs refer to themselves, each time growing larger and larger until the end conditions are met. The recursive version is always simpler, but uses more memory because it has to be loaded over and over. The non-recursive version is harder to write, but will only need to load up once and will operate efficiently after that.
The problem of the Towers posits a Buddhist temple, in Hanoi, Vietnam, that has system of three giant poles, and an enormous stack of 64 stone (or gold) disks, each larger than the other. The monks are given the task of moving all of the disks from the first pole to the third one, with two rules. One, they can only move one disk at a time, and two, they cannot place a larger disk on a smaller one. (Oh, and three: disks must move to one of the poles. No fair holding them between moves.) Legend has it that the world will end when they finish their task, so no hurry, guys.
In any case, mathematicians have proved that all cases with an even number of disks, it takes a minimum of number of moves to solve, where "n" is the number of disks.
2^n-1 moves are required
Wikipedia's mathematicians have determined that if the monks move one disk per second (which becomes increasingly unlikely as the disks get larger), it would take 600 billion years to solve. Exponents grow very very fast. Wikipedia's article on the subject also includes a picture of a simplified wooden version, for visualization, which is nice.
In any case, the proper solution is recursive: First move the top section to pole three, then start moving the end, then stack everything on pole three, moving back and forth as to not violate the second rule. Yes, a good programmer can rewrite a non-recursive version of this that will not use a ridiculous amount of memory, but the increased complexity is mind-boggling.
So why is this important? Well, back in the 70s, the very best way to sort lists of information was discovered. It's called quicksort. Quicksort sorts long lists faster than any other method, with one problem: It's by default recursive. Any list long enough to be noticably sorted faster by quicksort would suck up all memory long before it finished sorting. Yes, a good programmer can rewrite it so as not to be recursive, but it's harder.
I suppose this also exists in other fields, where a difficult simplification makes things run better, and one must consider if it's worth doing that.

No comments:

Related Posts Plugin for WordPress, Blogger...