Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!elnk-pas-nf1!elnk-nf2-pas!newsfeed.earthlink.net!newshub.sdsu.edu!headwall.stanford.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail
Message-ID: <7675c585.0309152041.240124b5@posting.google.com>
From: herb@perftech.com (herb@perftech.com)
Newsgroups: sci.math
Subject: Re: Last Call For Primecounters
Date: 15 Sep 2003 21:41:48 -0700
References: <m7bc31-pkc.ln1@lexi2.athghost7038suus.net>
Lines: 111
Organization: http://groups.google.com/
NNTP-Posting-Host: 67.11.196.64
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1063687309 2557 127.0.0.1 (16 Sep 2003 04:41:49 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 16 Sep 2003 04:41:49 GMT
X-Received-Date: Mon, 15 Sep 2003 21:41:50 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:38203

The Ghost In The Machine <ewill@sirius.athghost7038suus.net> wrote in message news:<m7bc31-pkc.ln1@lexi2.athghost7038suus.net>...
> It's been an interesting and slightly weird contest so far,
> and I'll definitely have to write a blurb on memoization
> somewhere in the results.  (To put it crudely, to memoize
> a function, usually recursive, means to add a cache
> thereto, so that a result isn't computed more than once.
> The speedup can be amazing.)
> 
Second version. Additional memoization only.

Herb Savage

/* Written by: Herb Savage    */
/* Date:       15 Sep 2003    */
/* Purpose:    Computes pi(X) */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define TRUE  1
#define FALSE 0

int prime(unsigned x) {
   unsigned i,t;
   if (x < 2)
      return FALSE;
   if (x == 2)
      return TRUE;
   if (!(x & 1))
      return FALSE;
   i = 3;
   for (;;) {
      t = x / i; 
    if (t < i) break;
      if (t * i == x) 
         return FALSE;
      i += 2;
      }
   return TRUE;
   }

unsigned nextPrimeM(unsigned x) {
   if (x < 2)
      return 2;
   if (!(x & 1))
      x--;
   while (!prime(x += 2));
   return x;
   }

#define np_cache_size 10000
unsigned np_cache[np_cache_size];

unsigned nextPrime(unsigned x) {
   if (x < np_cache_size) {
      if (!np_cache[x])
         np_cache[x] = nextPrimeM(x);
      return np_cache[x];
      }
   return nextPrimeM(x);
   }

unsigned pi_n(unsigned x, unsigned y);
unsigned pi_nM(unsigned end, unsigned maxP) {
   unsigned others,p,primes;
   others = end - 1;
   if (others < 1)
      return 0;
   p = 0;
   primes = 0;
   for (;;) {
      p = nextPrime(p);
    if ((p * p > end) || (p >= maxP)) break;
      if (p == 2)
        others -= (others + 1) / 2;
      else if (p == 3)
        others -= (others + 2) / 3;
      else
        others -= pi_n(end/p,p) - (primes - 1);
      primes++;
      }
   return primes + others;
   }

#define pi_cache_size 100
unsigned pi_cache[pi_cache_size][pi_cache_size];

unsigned pi_n(unsigned x, unsigned y) {
   if (x < pi_cache_size && y < pi_cache_size) {
      if (!pi_cache[x][y])
         pi_cache[x][y] = pi_nM(x,y);
      return pi_cache[x][y];
      }
   return pi_nM(x,y);
   }

unsigned long long pi(unsigned long long v) {
   return pi_n(v,v);
   }

int main(int argc, char *argv[]) {
   unsigned n;
   if (argc != 2)
      exit(1);
   sscanf (argv[1], "%u", &n);
   printf ("%llu\n", pi(n));
   exit(0);
   }
---------------------------------end program