From: terje.mathisen@nospicedham.tmsw.no   
      
   Robert Wessel wrote:> My question is, what exactly is the point?  It's   
   trivial, but you're> stuck needing 512MB of disk and address space, plus   
   the I/O for that> every time the program loads.   
      
   That was exactly my question as well: A table lookup is completely   
   trivial, and including the even values is just dumb.   
      
   >   
   > I'd call that two instructions, but that's just me.   
   >   
   > If you don't mind making the test four instructions, you could store   
   > only a bitmap of the odd numbers.   
      
   Right.   
   >   
   > Considering the cost of a page I/O, even to SSD, you might well be   
   > better off just testing against the 6542 primes (which, if my   
   > calculations are correct, is the number of primes below sqrt(2**32)).   
   > That would only take a 13kb table to store.  And if there's a fair   
   > fraction of non-primes being tested, that will usually fail after only   
   > the first few tests anyway.   
      
   For a general program you should probably start with a few fast checks,   
   then a seach following that. If you use a bitmap covering groups of 30   
   (2*3*5) numbers, you immediately get rid of 24 of those 30 values as   
   potential primes. Using a full bitmap gets you a similar compression ratio.   
      
   It is only when you need to test a _lot_ of numbers below 2^32, and most   
   of them will be "nearly prime", that you should consider a bitmap approach.   
      
   >   
   > Loading a large table might well be the fastest solution if you   
   > actually have a very large number of values to test, but in that case,   
   > you'd be much better off with a sequential read into memory, that sort   
   > of random access into the mmapped file is going to be slow.   
      
   Yeah, if you will test a bunch of unsorted inputs just do a read() of   
   the entire table, then for each candidate do a div/mod 30 (reciprocal   
   mul!) to calculate the byte number and offset.   
      
   The offset value is used in a second 30-byte table which gives the bit   
   offset for potential primes and -1 for the rest.   
      
   Terje   
      
      
   --   
   -    
   "almost all programming can be viewed as an exercise in caching"   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)