Author: Robert Hyatt
Date: 08:25:38 10/07/01
Go up one level in this thread
On October 07, 2001 at 10:35:47, Miguel A. Ballicora wrote: > >The point is the existance of a demonstration that 1 is impossible. The fact >that you did not see it is not exactly the point. Anyway, I think that I can >find one example of 1. At least I'll try. First, would you consider that the >following is a good sequential algorithm? > >Suppose that I have a "virtual cave" with tunnels shaped like a tree. >At the end of one of the tunnels, there is key (trasure). The goal is to >find it. So, each node is split in two (this is fork) branches. Only one leaf >has the key, all the others are empty. >Would you consider a good algorithm to traverse the tree recursively, first >to the right, when I find an empty leaf (or subtree) I return and I continue >on the left branch until I searched the whole tree or find the key? > >Regards, >Miguel > Sounds fine by me. Since there is no "ordering" possible, serendipity will solve it. Which means an average speedup of 2.0 should be possible with two threads. NO more however... And note, this idea of finding _one_ super-linear case in the above is meaningless. You must find that the _average_ speedup is super-linear, by putting the "key" in every possible location. Or at least in N random different locations where N is reasonably large. Then there will be no >2 average. Only an occasional >2 example of how serendipity can sometimes be good. The mode of proving super-linear is possible seems to be to find one possible algorithm, with one possible test-case of it, and then stopping. That won't cut it for _proving_ anything...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.