Re: NewPGen Sieve Algorithm ?
- 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 email@example.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 firstname.lastname@example.org, "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
- Mohsen wrote:
> I have read somewhere that NewPGen uses BSBG (Baby Step Giant Step)!You can Google Baby Step Giant Step. It's an algorithm for discrete
> 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.
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
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