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

Re: [PrimeNumbers] NewPGen Sieve Algorithm ?

Expand Messages
  • 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 1 of 8 , Jan 8, 2013
    View Source
    • 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 2 of 8 , Jan 8, 2013
      View Source
      • 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 3 of 8 , Jan 8, 2013
        View Source
        • 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.