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

Re: [PrimeNumbers] NewPGen Sieve Algorithm ?

Expand Messages
  • Jens Kruse Andersen
    ... Mathematica is slow for prime work. Nobody serious uses it to search large primes. NewPGen is OK for some things but my unpublished APTreeSieve is faster
    Message 1 of 8 , Jan 6, 2013
    • 0 Attachment
      Mohsen wrote:
      > NewPGen is the fastest primorial sieve app I've every tried.
      > I couldn't understand its sieve method for k*n#+-1 and even
      > I tried to compete with it in the world class Mathematica
      > software but the tiny 200KB NewPGen is 30 times faster than
      > the fastest answer in this question
      > (http://mathematica.stackexchange.com/questions/17098/fast-sieve-implementation)
      >
      > Does anybody know its sieve algorithm for primorial numbers?
      >
      > 100K digits primorial sieving up to 100,000th prime
      >
      > NewPGen => 5 seconds
      > Fastest Mathematica Code => 150 seconds

      Mathematica is slow for prime work. Nobody serious uses it
      to search large primes.
      NewPGen is OK for some things but my unpublished APTreeSieve
      is faster for large primorials. It uses a remainder tree. It's in C and
      uses the GMP library.
      Timings are using one core of a 2.4 GHz Core 2 Duo with 32-bit Windows Vista.
      A million primes were used to get better timings.

      231001# has 100186 digits.
      Sieving k*231001#+1 for k = 1 to 10^6.
      NewPGen 2.82: 118s
      APTreeSieve: 12s

      --
      Jens Kruse Andersen
    • Mark Rodenkirch
      ... I m not familiar with APTreeSieve. Could it be implemented in a GPU? --Mark [Non-text portions of this message have been removed]
      Message 2 of 8 , Jan 6, 2013
      • 0 Attachment
        On Jan 6, 2013, at 6:03 PM, Jens Kruse Andersen wrote:
        > Mathematica is slow for prime work. Nobody serious uses it
        > to search large primes.
        > NewPGen is OK for some things but my unpublished APTreeSieve
        > is faster for large primorials. It uses a remainder tree. It's in C and
        > uses the GMP library.
        > Timings are using one core of a 2.4 GHz Core 2 Duo with 32-bit Windows Vista.
        > A million primes were used to get better timings.
        >
        > 231001# has 100186 digits.
        > Sieving k*231001#+1 for k = 1 to 10^6.
        > NewPGen 2.82: 118s
        > APTreeSieve: 12s
        >

        I'm not familiar with APTreeSieve. Could it be implemented in a GPU?

        --Mark

        [Non-text portions of this message have been removed]
      • Jens Kruse Andersen
        ... I don t know anything about GPU programming but APTreeSieve uses a lot of memory for a sieve. It s basically just TreeSieve with some added code to use the
        Message 3 of 8 , Jan 6, 2013
        • 0 Attachment
          Mark Rodenkirch wrote:
          > I'm not familiar with APTreeSieve. Could it be implemented in a GPU?

          I don't know anything about GPU programming but APTreeSieve
          uses a lot of memory for a sieve. It's basically just TreeSieve with
          some added code to use the computed remainders from the
          remainder tree to sieve an arbitrary arithmetic progression.

          --
          Jens Kruse Andersen
        • Mohsen
          I have read somewhere that NewPGen uses BSBG (Baby Step Giant Step)! Anybody knows? Although NewPGen is a native app vs Mathematica as being managed and under
          Message 4 of 8 , Jan 7, 2013
          • 0 Attachment
            I have read somewhere that NewPGen uses BSBG (Baby Step Giant Step)! Anybody knows? Although NewPGen is a native app vs Mathematica as being managed and under JVM overhead, but I should be able to sieve not faster but at least equal to NewPGen. Please help me.

            --- In primenumbers@yahoogroups.com, "Mohsen" wrote:
            >
            > NewPGen is the fastest primorial sieve app I've every tried. I couldn't understand its sieve method for k*n#+-1 and even I tried to compete with it in the world class Mathematica software but the tiny 200KB NewPGen is 30 times faster than the fastest answer in this question (http://mathematica.stackexchange.com/questions/17098/fast-sieve-implementation)
            >
            > Does anybody know its sieve algorithm for primorial numbers?
            >
            > 100K digits primorial sieving up to 100,000th prime
            >
            > NewPGen => 5 seconds
            > Fastest Mathematica Code => 150 seconds
            >
            > Thanks
            >
          • Mark Rodenkirch
            ... BSGS is typically used for k*b^n+/-c numbers. As for sieving faster with Mathematica, that is extremely unlikely. Mathematica has some specialized
            Message 5 of 8 , Jan 8, 2013
            • 0 Attachment
              On Jan 8, 2013, at 1:05 AM, Mohsen wrote:
              > I have read somewhere that NewPGen uses BSBG (Baby Step Giant Step)! Anybody knows? Although NewPGen is a native app vs Mathematica as being managed and under JVM overhead, but I should be able to sieve not faster but at least equal to NewPGen. Please help me.
              >
              BSGS is typically used for k*b^n+/-c numbers.

              As for sieving "faster" with Mathematica, that is extremely unlikely. Mathematica has some specialized routines, but not everything you do with it is highly optimized. NewPGen has code specific for k*n#+/-1 numbers, so it will be faster.

              --Mark

              [Non-text portions of this message have been removed]
            • DavidU
              A good implementation of a good algorithm is very important to speed, however I would not expect anyone to come anywhere near NewPGen speed (using the same or
              Message 6 of 8 , Jan 8, 2013
              • 0 Attachment
                A good implementation of a good algorithm is very important to speed, however I would not expect anyone to come anywhere near NewPGen speed (using the same or similar algorithms) without either their own native application with custom assembly language support or a good optimized math library likely written partly in assembly.

                I cannot address k*n#+-1 directly, but I am very familiar with NewPGen implementation of k*2^n+-1. The key computations have always been in native assembly language. The last two speed improvements were an assembly language written bitmap representation of the candidate p values, and an assembly language pipelined parallel implementation of the root calculations. This is not addressing multi-core or multi-threaded. This is parallel processing within a single x86 core.

                The future is graphic processor based calcuations, however for an x86 or x64 based application, properly written native code is significantly faster than managed or JVM in numeric calcuations. A few of those calculations lend themselves to assembly language pipelined parallel optimizations.

                NewPGen put together a good algorithm, good implementation, and good optimizations. All components working together for speed.


                --- In primenumbers@yahoogroups.com, "Mohsen" wrote:
                >
                > I have read somewhere that NewPGen uses BSBG (Baby Step Giant Step)! Anybody knows? Although NewPGen is a native app vs Mathematica as being managed and under JVM overhead, but I should be able to sieve not faster but at least equal to NewPGen. Please help me.
                >
                > --- In primenumbers@yahoogroups.com, "Mohsen" wrote:
                > >
                > > NewPGen is the fastest primorial sieve app I've every tried. I couldn't understand its sieve method for k*n#+-1 and even I tried to compete with it in the world class Mathematica software but the tiny 200KB NewPGen is 30 times faster than the fastest answer in this question (http://mathematica.stackexchange.com/questions/17098/fast-sieve-implementation)
                > >
                > > Does anybody know its sieve algorithm for primorial numbers?
                > >
                > > 100K digits primorial sieving up to 100,000th prime
                > >
                > > NewPGen => 5 seconds
                > > Fastest Mathematica Code => 150 seconds
                > >
                > > Thanks
                > >
                >
              • Jens Kruse Andersen
                ... You can Google Baby Step Giant Step. It s an algorithm for discrete logarithms. It s used for fixed k sieves , i.e forms like k*2^n+/-1 where k is fixed
                Message 7 of 8 , Jan 8, 2013
                • 0 Attachment
                  Mohsen wrote:
                  > I have read somewhere that NewPGen uses BSBG (Baby Step Giant Step)!
                  > Anybody knows? Although NewPGen is a native app vs Mathematica as
                  > being managed and under JVM overhead, but I should be able to sieve not
                  > faster but at least equal to NewPGen. Please help me.

                  You can Google Baby Step Giant Step. It's an algorithm for discrete
                  logarithms. It's used for "fixed k sieves", i.e forms like k*2^n+/-1 where
                  k is fixed and n varies. This is very different from arithmetic progressions
                  like k*n#+/-1 where n is fixed and k varies.

                  You have unrealistic expectations about the efficiency of Mathematica.
                  It has a lot of functions and makes it easy to program many problems
                  but it's not particularly fast, at least not for the operations needed to
                  search primes.
                  The 5000 largest known primes at http://primes.utm.edu/primes/ were
                  found with a variety of sieves, prp testers and primality provers, but
                  I haven't heard of anyone who used Mathematica for any of the steps.

                  --
                  Jens Kruse Andersen
                Your message has been successfully submitted and would be delivered to recipients shortly.