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

NewPGen Sieve Algorithm ?

Expand Messages
  • Mohsen
    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
    Message 1 of 8 , Jan 6, 2013
    • 0 Attachment
      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
      ... 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 2 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 3 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 4 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 5 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 6 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 7 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 8 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.