Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: The sieve of Xuedong Luo (Algorithm3) for generating prime numbers

by Anonymous Monk
on Jun 11, 2015 at 17:45 UTC ( #1130070=note: print w/replies, xml ) Need Help??


in reply to The sieve of Xuedong Luo (Algorithm3) for generating prime numbers

Algorithm3 packs the sieve more tightly than regular odds-only (ie. in wheel6 formation, 2 bits per 6 numbers). Other than that, it's pretty much straight-up Eratosthenes. The clever flip-flops (k = 3 - k and ij = t - ij) disappear when the loops are unrolled (by hand or by compiler).

All in all, I don't expect this algorithm to hold much interest.

Replies are listed 'Best First'.
Re^2: The sieve of Xuedong Luo (Algorithm3) for generating prime numbers
by danaj (Friar) on Jun 12, 2015 at 23:58 UTC

    Using a mod-6 wheel is quite common. ntheory (aka Math::Prime::Util) uses a mod-30 wheel which is nice because their are 8 candidates per block, which packs nicely in a byte. The Sieve of Atkin is a twist on mod-30 (among other things, it's mod-60 which lets it skip 2,3,5). Terje Mathisen wrote a neat little monolithic mod-30 sieve in 1998 you can find on the net. I've seen a mod-2310 sieve but it seems very unwieldy for very little gain. PrimeSieve has 3 sieves for use at different sizes. A mod-30 sieve for small sizes, a mod-210 wheel for medium, and an optimized version of Oliveira e Silva's sieve for large sizes.

    Quesada and Van Pelt wrote about a mod-30 sieve in 1996 (they cite Luo's 1989 paper), Sorenson in 1991. He even has a section discussing their agreements and disagreements with Luo's paper as well a Pritchard's earlier paper. Sorenson has a paper on Arxiv from March 2015 that I've been meaning to look at, though I don't think it will change anything (e.g. "The proof is a bit artificial and of theoretical interest only. Coding this in practice seems daunting."). People are still working on these things.

    There is no question that primesieve is fast. It's great stuff, and Kim is a sharp developer who has been working on this for many years. He also has a slightly different target -- at large sizes the TOeS algorithm uses a lot of memory. I have tried to keep memory use more constrained. This comes up a lot with tables and precalculation, where I really can't do too much, as most users will probably never even call whatever function I'm optimizing, and I get a lot of feedback about trying to keep the initial size down. primesieve, and its sister project primecount, strive to be fast and offer C and C++ APIs.

Re^2: The sieve of Xuedong Luo (Algorithm3) for generating prime numbers
by Laurent_R (Canon) on Jun 12, 2015 at 20:57 UTC
    Hmm, I had never heard before about Xuedong Luo, nor about "Algorithm3".

    But when I was in my first year in technical high school (first university year) in computer science, back in 1989-1990, I was given a homework assignment to implement a prime number algorithm in Pascal (I remember it was in Pascal, but it might have been in Basic or in C, the two other languages we had to work with at the time). My first implementation was just a standard Eratosthenes sieve just using odd numbers both for numbers to be examined and for candidate divisors (with a special case for 2, the only even number that is prime).

    In that assignment, I then noticed that the algorithm was getting really slow when getting around the 1,000,000 mark (if I remember correctly the timing, hardware of the time was really not like today, especially with my budget PC then). So I offered at least two possible performance optimizations:

    - discarding even numbers and multiples of 3;

    - choosing possible divisors only among the primes found so far;

    If I remember correctly, I obtained the maximum possible mark for that homework assignment.

    But if the real advantage of Algorithm3 is just discarding not only odd numbers but also multiples of 3, then I could almost claim to be a co-discoverer (I am of course just joking, I've never published on that, and I am fairly sure some other people thought about that possibility before). But, still, same idea, same period. And I am almost sure that I still have that assignment paper copy in my archives, with the annotations from my professor at the time (at least I still had it very recently, I don't think I have thrown it away in between).

    I might try to post the Pascal abridged source code tomorrow, if I remember.

      That is awesome. I like Algorithm3 a lot. It is exciting to know that someone else attempted to make the sieve of Eratosthenes faster. Beautiful minds.

Re^2: The sieve of Xuedong Luo (Algorithm3) for generating prime numbers
by marioroy (Parson) on Jun 12, 2015 at 20:58 UTC

    I applaud Xuedong Luo, Laurent_R, and others for taking the sieve of Eratosthenes and creating a faster and more compact algorithm.

      Ooh, I clicked on the wrong reply link. I met to reply above to Laurent_R.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1130070]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2022-05-27 16:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you prefer to work remotely?



    Results (97 votes). Check out past polls.

    Notices?