From mboxrd@z Thu Jan 1 00:00:00 1970 MIME-version: 1.0 Content-type: text/plain; charset=WINDOWS-1252; format=flowed; delsp=yes Message-id: <366359C8-D689-40E7-BE54-A5CC7B5E2145@mac.com> From: Pietro Gagliardi To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> In-reply-to: <20080606095532.GA998@shodan.homeunix.net> Content-transfer-encoding: quoted-printable Date: Fri, 6 Jun 2008 06:23:19 -0400 References: <8BE506AC-687A-4D6B-AB03-7E9B75BBB0C4@mac.com> <20080606095532.GA998@shodan.homeunix.net> Subject: Re: [9fans] Fun with libthread 1: The Sieve Topicbox-Message-UUID: b4c12966-ead3-11e9-9d60-3106f5b1d025 I forgot to mention one simple detail: when I said we set c to newc, =20 we only set sieve's copy. filter still uses the c we gave it, meaning =20= it reads numbers from counter the first time around. Martin: this was just an experiment. I'm really not sure how to count =20= timed programs. Jon Bentley showed me how to count simple algorithms. =20= I'm not so sure this is very simple at first glance. On Jun 6, 2008, at 5:55 AM, Martin Neubauer wrote: > Very amusing. However, I'm not sure what you are trying to tell us, =20= > 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 =3D 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 =20 >> 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 =20 >> 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. =20= >> The >> manual page claims it runs in time O(=E2=88=9A(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 =20= >> CPU >> cycle hog. >