Hello. I decided to teach myself the 33 libraries of Plan 9 (even
those that I partially know), and I started with libthread, Sape's
implementation of Newsqueak-esque threads in C.
One of Rob's favorite programs is Doug's Newsqueak Sieve of
Eratosthenes. It's a simple Newsqueak program that uses filtration to
wipe out prime numbers. I ported it to C: /n/sources/contrib/pietro/
sieve.c. The executable takes an argument determining how many prime
numbers to print; the default is 100.
sieve() is spawned with a channel that is sent the prime numbers. It
first spawns counter() with a new channel. This channel is given all
integers n where n = 2, 3, ... . We will call the original channel
"primes" and the new channel "c".
We now send primes the first value received from c. This is going to
be a prime number. Now, a new thread called filter() is called with
three components: this prime number, c, and a new channel newc. It
reads values from c, and if they are not factors of the original
prime
number, sends them via newc. This next part is magic: c becomes newc.
So the next time we get a value from c, it will give us the first
prime returned from filter. Lather, rinse, repeat. Pike's video shows
you this graphically.
So this is the part of the story subtitled "O Isn't That Big
Anymore."
This was all done yesterday, June 4, 2008. I decided to compare the
running time of the sieve to primes(1), a program that, given start
and end primes, prints all primes between start and end inclusive.
The
manual page claims it runs in time O(√(N)).
% time sieve 205963 > sieve.out
That's right -- I'm finding the first 205,963 prime numbers. It runs
from around 7:00 PM EST 4 June 2008 to around 9:00 PM or 10:00 PM 5
June 2008, when I come home from band practice, when I notice that
QEMU froze probably due to some other background processes (which is
normal behavior, unfortunately) after storing the 25,511th prime
(293,681). So to get that far, I would imagine Doug's program to be
O(N^N) or O(N!). Who knows?
Note that due to primes' syntax I can't time that until I know what
the 205,963rd prime number is.
Pietro
PS - I don't free channels, making sieve a memory hog as well as a
CPU
cycle hog.
