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

Re: [PrimeNumbers] Calculate first 3.2 trillion primes in 39 hours on standard PC

Expand Messages
  • Phil Carmody
    ... I think the results of a willy-waving contest nearly a decade ago between Terje Mathisen and James Van Buskirk on c.l.a.x, concluded that about an order of
    Message 1 of 7 , Mar 5, 2013
    • 0 Attachment
      Jack Brennen wrote:
      > Looks like you can extrapolate that implementation to get the first
      > 3.2 trillion primes in about 5-6 hours on an Intel i7-920, assuming
      > sufficient RAM available.

      I think the results of a willy-waving contest nearly a decade ago between Terje Mathisen and James Van Buskirk on c.l.a.x, concluded that about an order of magnitude faster than that speed should be possible. If you're James, that is. Tomas e Silva's sieve uses pretty much the same algorithm, but he hasn't optimised it quite as much. (James is an extreme optimiser, very few people can optimise as much!)
      http://www.ieeta.pt/~tos/software/prime_sieve.html

      Phil
    • Ben Buhrow
      ... Nearly two orders of magnitude is possible. YAFU and primesieve both compute pi(x) to 3.2e12 using the sieve of Eratosthenes in about 30 minutes on my
      Message 2 of 7 , Mar 6, 2013
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...> wrote:
        >
        > Jack Brennen wrote:
        > > Looks like you can extrapolate that implementation to get the first
        > > 3.2 trillion primes in about 5-6 hours on an Intel i7-920, assuming
        > > sufficient RAM available.
        >
        > I think the results of a willy-waving contest nearly a decade ago between Terje Mathisen and James Van Buskirk on c.l.a.x, concluded that about an order of magnitude faster than that speed should be possible. If you're James, that is. Tomas e Silva's sieve uses pretty much the same algorithm, but he hasn't optimised it quite as much. (James is an extreme optimiser, very few people can optimise as much!)
        > http://www.ieeta.pt/~tos/software/prime_sieve.html
        >
        > Phil
        >

        Nearly two orders of magnitude is possible. YAFU and primesieve both compute pi(x) to 3.2e12 using the sieve of Eratosthenes in about 30 minutes on my machine (a pretty fast server). They are both threadable too - with 4 threads YAFU takes about 8 minutes.

        - ben.
      • Ben Buhrow
        ... Apologies, I was confusing pi(1e14) ~= 3.2e12 with pi(3.2e12). After running some experiments, it looks like the two programs I mentioned will take about
        Message 3 of 7 , Mar 6, 2013
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "Ben Buhrow" <bbuhrow@...> wrote:

          >
          > Nearly two orders of magnitude is possible. YAFU and primesieve both compute pi(x) to 3.2e12 using the sieve of Eratosthenes in about 30 minutes on my machine (a pretty fast server). They are both threadable too - with 4 threads YAFU takes about 8 minutes.
          >
          > - ben.
          >

          Apologies, I was confusing pi(1e14) ~= 3.2e12 with pi(3.2e12). After running some experiments, it looks like the two programs I mentioned will take about 18 hrs for pi(1e14), so more like a factor of 2.
        • James Firth
          Thank you Ben. I have already optimised down to 18 hours for pi(1e14) however primesieve is consistently running at least 4 times faster on my machine. I am
          Message 4 of 7 , Mar 6, 2013
          • 0 Attachment
            Thank you Ben.

            I have already optimised down to 18 hours for pi(1e14) however primesieve is consistently running at least 4 times faster on my machine.

            I am aware that I might be using an odd method to stitch together my sieve segments.  Some Javascript here (when you click on the demo link) explains how I have calculated my boundaries:
            http://www.daltonfirth.co.uk/tuts/js/prime-finder/prime-finder.html

            I am not seeing the efficiency improvements the primesieve author gets when the sieve memory fits into the L2 cache; I will probably have to switch to Tomás Oliveira e Silva's bucket method.

            I had a hunch my method, which allows starting on a prime's square for starting values greater than seg_start/start_val, might be efficient, but alas...

            I might try improving the storage compression, I'm currently using modulo 30, but I doubt I'll find another 4x optimisation in my code.

            JDF

            --- In primenumbers@yahoogroups.com, "Ben Buhrow"  wrote:

            >
            > Nearly two orders of magnitude is possible.  YAFU and primesieve both compute pi(x) to 3.2e12 using the sieve of Eratosthenes in about 30 minutes on my machine (a pretty fast server).  They are both threadable too - with 4 threads YAFU takes about 8 minutes.
            >
            > - ben.
            >

            Apologies, I was confusing pi(1e14) ~= 3.2e12 with pi(3.2e12).  After running some experiments, it looks like the two programs I mentioned will take about 18 hrs for pi(1e14), so more like a factor of 2.
          Your message has been successfully submitted and would be delivered to recipients shortly.