Re: [9fans] Fun with libthread 1: The Sieve

[Martin Neubauer <m.ne@gmx.net>]

Very amusing. However, I'm not sure what you are trying to tell us, besides
that you haven't understood what the O(...) means.

* Pietro Gagliardi (pietro10@mac.com) wrote:
> 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.