6
\$\begingroup\$

I know prime number programs have been beaten to death. I have been programming for eight years (not that long, but I'm not in my 20s yet and I got a programming job straight out of high school so I'm not doing too shabby). Everyone's first instinct is the "Naive" approach (nested loops, check for divisors), and I wrote my fair share of prime number programs. Over the years, those programs have gotten faster and faster, but I now believe I have reached the fastest possible C# implementation of a prime number finder. It uses a prime sieve and has a small memory footprint. I was wondering if there are any optimizations that anybody else can think of?

List<int> Primes = new List<int>();
Primes.Add(2);

int half = count/2 + 1;
bool[] nums = new bool[half];

for (int i = 0;i<half;i++)
{
    if (!nums[i])
    {
        int number = i * 2 + 3;
        Primes.Add(number);
        for (int j = i + number; j < half; j += number)
        {
            nums[j] = true;
        }
    }
}
return Primes;
\$\endgroup\$
  • \$\begingroup\$ Are you familiar with the Sieve of Atkin? \$\endgroup\$ – Greg Hewgill Jun 9 '14 at 21:48
  • \$\begingroup\$ I am, however I'm not yet sure of WHY its faster. I've read that it can be slower depending on the implementation, so I'm still doing research in this area... \$\endgroup\$ – John Davis Jun 10 '14 at 13:05
  • \$\begingroup\$ @JohnDavis - Your code above returns primes past the limit. I'm assuming that count is the upper limit. With a count of 10, your function returns 2,3,5,7,11,13. \$\endgroup\$ – hatchet Jun 10 '14 at 16:31
  • 1
    \$\begingroup\$ @hatchet Thanks, nice catch. However, changing "int half = count/2+1" to "int half = count/2-1" fixes that, but thats not the reason for a 25% speed boost for Atkin. \$\endgroup\$ – John Davis Jun 10 '14 at 19:27
3
\$\begingroup\$

There is an optimization you can still take advantage of. When you mark your prime multiples, you do not need to mark prime multiples that are less than prime * prime. This is because all smaller multiples are the prime number times some number that is either a smaller prime, or a composite of smaller primes. But earlier loops that processed those primes will have already marked those.

As an example, when number is 5, your code will start the inner loop with j=6 (which represents 15). That will already have been marked when the inner loop ran for the prime number 3. You only need to start at j=11 (which represents 25). Not only will this save you spending time re-marking already marked composites, you will not even need to run the inner loop once your prime number has reached the square root of the limit. However, in testing, the cost of doing the square root made it slightly better to just test against a literal value of the square root of Int32.MaxValue.

Here is your code with three lines modified to take this additional optimization. In my test, it is only a little faster for small limits, but the advantage increases as the limit increases. For large limits it is around 18% faster.

    List<int> Primes = new List<int>();
    Primes.Add(2);

    int half = count / 2 + 1;
    bool[] nums = new bool[half];
    var limit = 46340; //(int)Math.Sqrt(int.MaxValue);
    for (int i = 0; i < half; i++) {
        if (!nums[i]) {
            int number = i * 2 + 3;
            Primes.Add(number);
            if (number <= limit) {
                for (int j = ((number * number)/2) -1; j < half; j += number) {
                    nums[j] = true;
                }
            }
        }
    }
    return Primes;

This doesn't fix the small edge problem in your code that sometimes includes primes past the limit. You could make an additional possible optimization by just blasting through the rest of the nums array the first time you exceed limit rather than repeat the (number <= limit) test multiple times.

\$\endgroup\$
  • \$\begingroup\$ I fixed the "past bound" problem (see my comment on my post). This is exactly the thing that I'm looking for - the reason my code was slower. My results are the same as yours - however your modified code (and now my modified code) beats the Sieve of Atkin. Is this because the Atkin code provided is not optimized? \$\endgroup\$ – John Davis Jun 10 '14 at 19:34
  • \$\begingroup\$ I haven't played with the Sieve of Atkin, so I can't speak to speed comparisons to it. \$\endgroup\$ – hatchet Jun 10 '14 at 19:49
  • \$\begingroup\$ From what I read, the Sieve of Atkin employs wheel-factorization, however I still can't understand the other answer is any different form mine. \$\endgroup\$ – John Davis Jun 10 '14 at 19:58
  • \$\begingroup\$ I think the other answer is essentially the same algorithm as yours, with some implementation differences. For example, he initializes the list to a capacity that is an estimate of the number of primes there will be. That saves a little time by avoiding List grows. You could do something similar by just initializing like this: Primes = new List<int>(Math.Min(1000,(count+1)/2)). That can shave a couple percent more from your time. Most list grows are on the low end (4, 8, 16, 32, ...). Using a floating point equation to estimate the capacity can consume a lot of the time you're hoping to save. \$\endgroup\$ – hatchet Jun 10 '14 at 20:51
2
\$\begingroup\$

For building a list of prime numbers This code is about 25% faster in my tests:

EDIT: Minor point: My research has led me to the conclusion this is based on the Sieve of Sundaram.

public static List<int> ESieve1(int upperLimit)
{

    int sieveBound = (int)(upperLimit - 1) / 2;
    int upperSqrt = ((int)Math.Sqrt(upperLimit) - 1) / 2;
    List<int> numbers = new List<int>((int)(upperLimit / (Math.Log(upperLimit) - 1.08366)));
    bool[] PrimeBits = new bool[sieveBound + 1];
    numbers.Add(2);
    for(int i = 1; i <= upperSqrt; i++)
    {
        if(!PrimeBits[i])
        {
            int inc = 2 * i + 1;
            for(int j = i * 2 * (i + 1); j <= sieveBound; j += inc)
            {
                PrimeBits[j] = true;
            }
            numbers.Add(inc);
        }
    }
    for(int i = upperSqrt + 1; i <= sieveBound; i++)
    {
        if(!PrimeBits[i])
        {
            numbers.Add(2 * i + 1);
        }
    }
    return numbers;
}

This uses offset to the index to find the prime number rather than using the index directly.

Whereas just checking for prime not building a list and optimizing the code comes out very fast:

public static bool[] ESieveA(int upperLimit)
{
    int sieveBound = (int)(upperLimit - 1);
    int upperSqrt = (int)Math.Sqrt(sieveBound);
    bool[] PrimeBits = new bool[sieveBound + 1];            
    PrimeBits[0] = true;
    PrimeBits[1] = true;
    for(int j = 4; j <= sieveBound; j += 2)
    {
        PrimeBits[j] = true;
    }
    for(int i = 3; i <= upperSqrt; i += 2)
    {
        if(!PrimeBits[i])
        {
            int inc = i * 2;
            for(int j = i * i; j <= sieveBound; j += inc)
            {
                PrimeBits[j] = true;
            }
        }
    }
    return PrimeBits;
}

This optimizes by setting multiples of 2 first, then all the rest are odd so the outer loop can skip the even numbers and the inner loop only needs to set the odd multiples.

\$\endgroup\$
  • \$\begingroup\$ Very nice code. I'm still reading over it to figure out WHY it is faster, but it definitely beats mine. \$\endgroup\$ – John Davis Jun 10 '14 at 13:05
  • \$\begingroup\$ @tinstaafl - your ESieve1 code has a minor bug. It includes a prime twice with some (but not all) upperLimits. For example, given upperLimit of 10 returns 2, 3, 3, 5, 7. An upper limit of 200 returns the prime number 13 twice. \$\endgroup\$ – hatchet Jun 10 '14 at 16:29
  • \$\begingroup\$ @hatchet - Sorry I accidentally submitted an old version. I've corrected it now. \$\endgroup\$ – tinstaafl Jun 10 '14 at 17:28
  • \$\begingroup\$ Please explain your code. I'm itching to give it a +1, but code dumps aren't code reviews. \$\endgroup\$ – RubberDuck Jun 10 '14 at 17:36
  • 1
    \$\begingroup\$ @ckuhn203 - Added some explanation. \$\endgroup\$ – tinstaafl Jun 10 '14 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.