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 ([EMAIL PROTECTED]) 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.
