From: Pietro Gagliardi <pietro10@mac.com>
To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net>
Subject: [9fans] Fun with libthread 1: The Sieve
Date: Thu, 5 Jun 2008 23:09:04 -0400 [thread overview]
Message-ID: <8BE506AC-687A-4D6B-AB03-7E9B75BBB0C4@mac.com> (raw)
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.
next reply other threads:[~2008-06-06 3:09 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-06-06 3:09 Pietro Gagliardi [this message]
2008-06-06 9:55 ` Martin Neubauer
2008-06-06 10:19 ` roger peppe
2008-06-06 10:23 ` Pietro Gagliardi
2008-06-06 11:29 ` Martin Neubauer
2008-06-06 14:00 ` roland.kaufmann
2008-06-06 19:02 ` Pietro Gagliardi
2008-06-06 19:28 ` erik quanstrom
2008-06-06 15:35 ` Russ Cox
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=8BE506AC-687A-4D6B-AB03-7E9B75BBB0C4@mac.com \
--to=pietro10@mac.com \
--cc=9fans@9fans.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).