Loading ...
Sorry, an error occurred while loading the content.

Suggested (?) 2-bits per prime storage scheme

Expand Messages
  • James Merickel
    This is as much a question as a suggestion.  One way of storing all primes to a certain point is by using a foreshortened Eratosthenes sieve (along with some
    Message 1 of 4 , Aug 2, 2014
    • 0 Attachment
      This is as much a question as a suggestion.  One way of storing all primes to a certain point is by using a foreshortened Eratosthenes sieve (along with some benchmark values) to reconstruct the meaning of a string of T/F values, where the numbers evaluated are those which pass divisibility to the point where heuristic probability reaches 1/2.  Would this (type of) storage scheme be of value, or is there some sense that the time to reconstruct the meanings of the bit string is not worth a savings of memory?  
       
      I've thought of other simple ways of storing the primes, such as by a compression of those among the numbers of proper congruence class modulo 37#.  Is there any more-or-less standard way of doing things in this regard?
       
      I note that Prime number - Wikipedia, the free encyclopedia does not refer to any really large database at present.  Is a bigger one publicly available (as it seems to me should be the case)?  Is there any interest in a collaboration to build a truly massive database?  
       
      JGM
    • Andrey Kulsha
      Is there any interest in a collaboration to build a truly massive database? No. It s faster to generate primes than to download them. A good generator is
      Message 2 of 4 , Aug 2, 2014
      • 0 Attachment
        Is there any interest in a collaboration to build a truly massive database?
         
            No. It's faster to generate primes than to download them. A good generator is http://primesieve.org/ for example.
         
            Best regards,
         
            Andrey
      • James Merickel
        I m sure this is true, but I m not imagining their being used by repeated calls to a web source.  They could be saved to disk for repeated use (or the
        Message 3 of 4 , Aug 4, 2014
        • 0 Attachment
          I'm sure this is true, but I'm not imagining their being used by repeated calls to a web source.  They could be saved to disk for repeated use (or the source could sell disks or other storage media near cost).  Web call-ups could be useful in certain limited cases also, as when primes are wanted by their indices (direct calculation being prohibitive).  If stored in the kind of compressed manner suggested or others, the time for download would be cut substantially (In fantasy, if all primes under 10^18 were stored using the suggested compression (which isn't properly a simple compression--requiring determination of candidates by computation, but it should be substantially faster than naïve generation of primes), the storage of the largest primes is cut by a factor of 30 from full representation of each prime.
          JGM 

          From: Andrey Kulsha <andrey_601@...>
          To: James Merickel <moralforce120@...>
          Cc: PrimeNumbers@yahoogroups.com
          Sent: Saturday, August 2, 2014 3:02 PM
          Subject: Re: [PrimeNumbers] Suggested (?) 2-bits per prime storage scheme

          Is there any interest in a collaboration to build a truly massive database?
           
              No. It's faster to generate primes than to download them. A good generator is http://primesieve.org/ for example.
           
              Best regards,
           
              Andrey


        • paulunderwooduk
          Looking at the table on primesieve - Fast prime number generator http://primesieve.org/ http://primesieve.org/ primesieve - Fast prime number generator
          Message 4 of 4 , Aug 4, 2014
          • 0 Attachment
            Looking at the table on primesieve - Fast prime number generator

             

             for 2^32 or 203,280,221 primes which would supposedly fir on your 2 bits per prime CD. CD? Did you say DVD? What about a 1TB SSD? That is 10^12. Right? Well according to the table on primesieve's site you can generate with a good quad machine 346,065,536,839 in 926.83 seconds or about 15 minutes. How long is it going to take for your CD/DVD/SSD to read and decompress your 2 bits per prime map, given the limitations of the amount of RAM in your system?

            Paul
          Your message has been successfully submitted and would be delivered to recipients shortly.