Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!newsread3.news.pas.earthlink.net.POSTED!not-for-mail
Message-ID: <v7ml21-ujr.ln1@lexi2.athghost7038suus.net>
From: The Ghost In The Machine <ewill@sirius.athghost7038suus.net>
Newsgroups: sci.math
Subject: An Informal Call For Program Submissions To Compute pi(n)
Date: Fri, 05 Sep 2003 08:00:11 GMT
Lines: 114
X-face: "i;@/WO(?;[KC9sW;wG/4@H[_VFFH4?QHJ#O(?m}7fQMrJ,]0THA'\|e-EPG_>56Mi}_RRhBS'a2}u_7jm)0_+'=$V#E2r4#IQE/d)yMv3_4@hl<)mA&*tDN/
User-Agent: slrn/0.9.7.4 (Linux)
NNTP-Posting-Host: 209.86.1.142
X-Complaints-To: abuse@earthlink.net
X-Trace: newsread3.news.pas.earthlink.net 1062748811 209.86.1.142 (Fri, 05 Sep 2003 01:00:11 PDT)
NNTP-Posting-Date: Fri, 05 Sep 2003 01:00:11 PDT
Organization: EarthLink Inc. -- http://www.EarthLink.net
X-Received-Date: Fri, 05 Sep 2003 01:00:14 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:35861

I seem to be collecting these things anyway, so I might as well
throw out a call for slightly more formal submissions.

Here are the requirements.

[1] The editor (me) reserves the right to edit submissions
    so that they work. :-)  I'm fundamentally lazy, of
    course, so won't attempt to completely rewrite your
    algorithm but just make sure it fits into the square
    hole documented here, if it's a round peg.

[2] The algorithm must correctly compute pi(n), where
    pi(n) is the number of primes less than or equal to n.
    For example, the values of pi(0) through pi(10) would
    be 0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4.  For practical
    reasons pi(1000000) must be computable in less than
    about a minute on a Pentium III 400 Mhz; a number of
    submissions can already compute pi(1000000) in about
    a second.  (The correct value is 78498, in case you're
    wondering.)  I'll be using GNU C++ v3.3.1 for the tests,
    with optimization; it's not the best but it's what I
    have. :-) Expect a maximum value of around 20 million
    at most; I don't have that much computing horsepower
    for this. :-)

[3] All submissions should use C or C++.  Please use
    #include <iostream> if you need std::cin, std::cout,
    etc.  Also, I don't want total obfuscation here;
    I want to be able to read them.  :-) Compilation of
    routines will use -O2 on GNU C++.

[4] The signature of pi(n), for various esoteric reasons, must be

    unsigned long long pi(unsigned long long v).

    The editor reserves the right to rename your pi() and
    define his own pi() calling yours, if necessary.  This
    should have minimal effect on runtime but I cannot be
    held responsible for errors doing so in recursive calls.

[5] The algorithm should not halt, print out, or otherwise
    do anything totally weird.  main() routines may be
    added if desired (for testing, presumably), but I
    have my own anyway; all I really do is call pi(n)
    for various values of n.  Dynamic memory allocation
    and static variables are allowed, although I may be
    calling pi() repeatedly; code accordingly.  Note that
    the implementation

    unsigned long long pi(unsigned long long v) { return 78498; }

    is not acceptable, even though I've heretofore only
    been using 1000000 in my timing tests. :-)  Also,
    I don't really want to see a binary search through
    a fixed table of primes (besides, I'm thinking of
    including that as one of my submissions anyway, so
    that would be rather pointless!).

[6] Submissions already entered will be included.
    All source code becomes publically available, though
    not public domain, copyrighted by their respective
    owners.  I'll be putting results on my webpage,
    which should include more comprehensive results than
    I've been heretofore posting (which only computes
    pi(1000000), which is one streetlight on a winding
    road).

[7] Submissions will be picked up from Usenet posts in sci.math.
    Ideally they'd be in this thread. :-)  (For those who have
    posted code snippets that I've replied to in other threads,
    thank you. :-) )

[8] I'll be cataloging these by moniker.  If you have a munged
    E-mail address, I'll use that, along with your name.
    My submissions, for example, would be
    ewill@sirius.athghost7038suus.net (The Ghost In The Machine).
    As long as I can tell you guys apart. :-)  (So far, it's
    not been a problem.)  Multiple submissions are possible;
    James Harris has 3 already, for example, and I have 4;
    I'm thinking of at least one more.

[9] I'm not sure what to do about space complexity;
    suggestions are therefore welcome.  I am thinking of
    using sbrk(0) to see memory consumption but one might
    as well observe an ant hill using the Hubble Space
    Telescope.  Issues so far include dynamic allocation
    and deallocation (for sieves) and recursive stack
    usage.  If I can do it, C++'s _Alloc class might
    be pressed into service for tracking the former.
    However, several submissions already use O(1) space
    complexity, with no recursion.  (You know who you are. :-) )
    So far, however, the fastest algorithm has O(N) space
    complexity -- my simple sieve.  But just to let you know,
    JSH has surprised me with a submission of his own that
    takes 1.25s to compute pi(1 million).  Not bad, considering.

    I may simply compile things twice, after some mods:
    an #ifdef SPACE_COMPLEXITY might take care of things here.

[10] Time complexity is for now relatively simple; I'll be using
     wallclock time, either using time(1) or time(2).  Maybe both.

[11] The winner receives -- well, maybe some recognition in the
     field of sci.math, together with a line on my webpage with
     a (hopefully pretty and colorful) graph generated from gnuplot,
     which you can print and frame on your wall if you so desire.
     (No, I don't have a color printer or a supply of frames.)

I'm hoping to be able to rank the results at the very end, complete
with source code.  Happy coding! :-)

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.