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

Re: [PrimeNumbers] Erroneous Information

Expand Messages
  • Jud McCranie
    ... I keep my list up to 2^32 on disk, even though I think it would be faster to generate them. (At some point it becomes slower to generate them.) The
    Message 1 of 8 , Mar 5, 2001
    • 0 Attachment
      At 07:47 AM 3/5/2001 -0500, Jack Brennen wrote:

      > "The problem with answering this question is small primes are too
      > easy to find. The can be found far faster than they can be read from
      > a hard disk, so no one bothers to keep long lists (say past 10^9).
      > Long lists just waste storage, and on the Internet, they just waste
      > bandwidth."

      I keep my list up to 2^32 on disk, even though I think it would be faster
      to generate them. (At some point it becomes slower to generate them.) The
      reason I do that rather than generate them each time is for
      reliability. If I'm looking at primes of a certain type, I read them in
      and check. I think this is saver than changing the generating program each
      time. Also the program to read them in is a lot shorter and less prone to
      error than the generating program.

      +--------------------------------------------------------+
      | Jud McCranie |
      | |
      | 137*2^261147+1 is prime! (78,616 digits, 5/2/00) |
      +--------------------------------------------------------+
    • Ben Bradley
      ... I ve got something similar on my website - a short description of primes, with C source to programs to generate and read primes in a successive-differences
      Message 2 of 8 , Mar 5, 2001
      • 0 Attachment
        At 11:50 AM 3/5/01 -0500, Jud McCranie wrote:
        >At 07:47 AM 3/5/2001 -0500, Jack Brennen wrote:
        >
        >> "The problem with answering this question is small primes are too
        >> easy to find. The can be found far faster than they can be read from
        >> a hard disk, so no one bothers to keep long lists (say past 10^9).
        >> Long lists just waste storage, and on the Internet, they just waste
        >> bandwidth."
        >
        >I keep my list up to 2^32 on disk, even though I think it would be faster
        >to generate them. (At some point it becomes slower to generate them.) The
        >reason I do that rather than generate them each time is for
        >reliability. If I'm looking at primes of a certain type, I read them in
        >and check. I think this is saver than changing the generating program each
        >time. Also the program to read them in is a lot shorter and less prone to
        >error than the generating program.

        I've got something similar on my website - a short description of
        primes, with C source to programs to generate and read primes in a
        successive-differences format. My format uses four bits to store the
        difference between the majority of primes under 2^32 (and multiples of
        four bits for the rest). For this range, the file format takes an average
        of about (I forget the exact numbers) five bits per prime.
        I heard and read several places that it's faster to generate primes
        in RAM with a sieve than to read them from a file, which I never
        understood, because my programs read the disk format and recreate
        the primes in about half the time it takes to generate them in RAM.
        One caveat, the programs don't work well with numbers near 2^32. :(
        -----
        This post (except quoted portions) Copyright 2001, Ben Bradley.
        http://listen.to/benbradley
      • Jud McCranie
        At 03:16 PM 3/5/2001 -0500, Ben Bradley wrote: I heard and read several places that it s faster to generate primes ... It is up to a point, and that point
        Message 3 of 8 , Mar 5, 2001
        • 0 Attachment
          At 03:16 PM 3/5/2001 -0500, Ben Bradley wrote:
          I heard and read several places that it's faster to generate primes
          >in RAM with a sieve than to read them from a file,


          It is up to a point, and that point depends on the speed of your CPU and
          disk drive. Reading from the file is pretty much linear in the number of
          primes, which is sub-linear for primes below a limit, whereas a sieve is
          super-linear, so for large enough numbers, the sieve will take longer. On
          my machine, reading primes < 2^32 from disk is about twice as fast as my sieve.


          +--------------------------------------------------------+
          | Jud McCranie |
          | |
          | 137*2^261147+1 is prime! (78,616 digits, 5/2/00) |
          +--------------------------------------------------------+
        • Phil Carmody
          A carefully constructed dump of a sieve will beat most run-length compression schemes, even with huffman (or other entropy) compresion. For broad ranges, I d
          Message 4 of 8 , Mar 5, 2001
          • 0 Attachment
            A carefully constructed dump of a sieve will beat most run-length compression schemes, even with huffman (or other entropy) compresion.
            For broad ranges, I'd use a 480/2310 comb to the sieve.
            For small ranges (a million primes) a 8/30 comb is fine.
            With the right code, I guestimate that generating primes should be faster than reading them off disk still, but it's not by a huge margin. Race Dan Bernstein's Primegen and Eratspeed against your hard disk for primes up to a billion if you don't believe me. (there are links on the primepages)

            However, my current sieving job is generating 17 digit numbers, and I store the deltas, which average around 7-8 digits. This gives me roughly 2:1 compression. I then BZIP2 them, which gives an almost exact log(10)/log(256) ratio, as the numbers are essentially unpredictable. Even then, I think I could fill a CD in a month.

            Twins fall into this latter catagory, and their density means that hard disk storage is worthwhile.

            Phil

            Mathematics should not have to involve martyrdom;
            Support Eric Weisstein, see http://mathworld.wolfram.com
            Find the best deals on the web at AltaVista Shopping!
            http://www.shopping.altavista.com
          Your message has been successfully submitted and would be delivered to recipients shortly.