🚀 go-pugleaf

     The problem with Ray's algorithm is that every processor is going to
receive N broadcasts (somewhat fewer, since some numbers are already crossed
out) to cross out the multiples of that number. And it will have to examine
N/p numbers to determine if it's a multiple. And the first number found to
be a multiple will have to be obtained by doing at least one division/modulo.

     How about this, starting at the first element of the list, a processor
traverses the list, crossing out all multiples of the first number. As the
list is processed, all numbers not crossed out are broadcast to the next
processor in the "pipeline", to form it's list. The next processor repeats
this procedure on the smaller list, and so on.

     Granted, since the last processor receives a smaller list, it spends
much of it's time idling. The total time is N plus the time it takes for
the last number to propogate through all the processors. If N is greater
than p, then things slow down somewhat. The pth processor must wait until
processor zero is done, before sending it's list. I guess this makes the
execution time N^2/p.

     To give credit where it's due, I didn't think this algorithm up. A
friend and coworker, Joe Golton, did.

						George (and Joe)
[  This analysis brings up a question about "good."  In the third
generaton mentality, "idle" == "bad."  Is that still true?  Or are there
better measures?
		Steve Stevenson - the moderator
]