- Mohsen wrote:
> NewPGen is the fastest primorial sieve app I've every tried.

Mathematica is slow for prime work. Nobody serious uses it

> 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

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

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