## Re: [PrimeNumbers] NewPGen Sieve Algorithm ?

Expand Messages
• ... 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
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
• ... 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
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]
• ... 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
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
• 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
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.

>
> 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
>
• ... 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
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]
• 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
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.

>
> 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
> >
>
• ... 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
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

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.