3
\$\begingroup\$

What a difference 1 bit makes! This very fast, simple sieve of Eratosthenes quickly finds 32 bit primes. It uses a memory efficient BitArray for odd numbers – but the BitArray is at the maximum allowable length of an array. While it borrows heavily from its 31 bit counterpart, Sieve31, this sieve has some interesting differences for tweaked performance. Sieve32 is one of the more uncommon uint based sieves.

Background

See link for Sieve31 which is a 31 bit sieve returning IEnumerable<int>.

See link for Microsoft Magic Numbers for a list of some primes (you must search the page for “prime”). This link has other interesting things in it.

public static class Sieve32
{
    public static IEnumerable<uint> Primes(uint upperLimit)
    {
        if (upperLimit < 2)
        {
            throw new ArgumentException("Upper Limit be must greater than or equal to 2.");
        }
        yield return 2;
        if (upperLimit == 2)
        {
            yield break;
        }
        // Check odd numbers for primality
        const uint offset = 3;
        Func<int, uint> ToNumber = delegate(int index)   { return (2U * (uint)index) + offset; };
        Func<uint, int> ToIndex  = delegate(uint number) { return (int)((number - offset) / 2U); };
        var bits = new BitArray(ToIndex(upperLimit) + 1, defaultValue: true);
        int upperSqrtIndex = ToIndex((uint)Math.Sqrt(upperLimit));
        for (int i = 0; i <= upperSqrtIndex; i++)
        {
            // If this bit has already been turned off, then its associated number is composite. 
            if (!bits[i]) continue;
            uint number32 = ToNumber(i);
            // The instant we have a known prime, immediately yield its value.
            yield return number32;
            // Small memory trade-off for better performance.
            // Cast once to int before going inside the loop.  Saved me 8 seconds.
            // A billion casts here or there can really start to add up.
            int number31 = (int)number32;
            // However, any multiples of number are composite and their respective bits should be turned off.
            for (int j = ToIndex(number32 * number32); (j > i) && (j < bits.Length); j += number31)
            {
                bits[j] = false;
            }
        }
        // Output remaining primes once bit array is resolved:
        for (int i = upperSqrtIndex + 1; i < bits.Length; i++)
        {
            if (bits[i])
            {
                yield return ToNumber(i);
            }
        }
    }
}

Deliberate Coding Against Standard Practices

For Sieve31, both the index to the BitArray and the prime numbers are int. So bouncing back and forth between a number scale and bit indices is seamless. It also employed fairly standard coding practices.

For Sieve32, the prime numbers are now uint so walking over the BitArray is a little different and sometimes confusing working with a mixture of int for indices and uint for numbers. Bouncing back and forth between a number scale and the bit indices requires some careful consideration.

I deliberately use var sparingly here. In fact it’s referenced only once. I use some explicit variable declarations when I want to highlight specific attention to a variable. I want Sam the Maintainer to fully see that I am putting special emphasis for him to pay attention the type of a given variable.

The coding style would be summarized as: var is when (1) its type is obvious and also when (2) the variable declared does not need special emphasis as to its type.

I also have 2 copies of the same value. One value is int and the other is uint. This is deliberate because it saves 8 seconds in performance. Consider this snippet of code:

// variable 'i' is an int
var number = ToNumber(i);
yield return number;
for (var j = (uint)ToIndex(number * number); (j > i) && (j < bits.Length); j += number)
{
    bits[(int)j] = false;
}

There’s 2 spots where performance degrades in the above. The first should be obvious: the explicit conversion/cast inside the loop body. The second spot is obscured by implicit casting: it’s the for condition. Since j is a uint and both i and bits.Length are int, they are all cast to long for comparison. Repeatedly.

Usually this isn’t a big deal. But do it a billion times, and it really starts to add up. That’s why I went against standard coding practices and chose to use:

// variable 'i' is an int
uint number32 = ToNumber(i);
yield return number32;
int number31 = (int)number32;
for (int j = ToIndex(number32 * number32); (j > i) && (j < bits.Length); j += number31)
{
    bits[j] = false;
}

Kind of hard to argue with sacrificing a mere 4 bytes to save 10 seconds.

Example Usage

Here’s a simple example that counts the number of primes found and tracks the largest one.

int count = 0;
uint largest = 0;
var primes = Sieve32.Primes(uint.MaxValue);
foreach (var prime in primes)
{
    count++;
    largest = prime;
}

Worst Case Scenario: uint.MaxValue

The BitArray will is at just 1 bit shy of an array’s allowable length! It requires 256 megabytes. This will yield 203,280,221 primes.

If you want to store the primes to a List<uint>, the code is quite easy:

var primeList = Sieve32.Primes(uint.MaxValue).ToList();

The resulting list would require 776 megabytes, in addition to the 256 for the BitArray. Bottom line: to output all 32 bit primes requires 1 gigabytes of memory! This takes about 75 seconds on my laptop. . Since BitArray is not thread safe, this is close to the best I can hope for on a single thread.

An indexed list is nice but limited by memory

Due to the memory requirements, it wouldn’t surprise me if many readers could not produce a full list. If you dump it to a list, then the internal BitArray is regenerated for each foreach loop.

A Challenge Problem

Given an extremely large uint upper limit, perhaps anything over 3 billion, build a random list of 100 primes. You cannot hardcode any known prime counts.

Short, Easy Solution

The easiest solution is to use the recommended indexed list, if memory allows.

private IList<uint> GetRandom100Easy(uint upperLimit)
{
    var answer = new List<uint>();
    var primeList = Sieve32.Primes(upperLimit).ToList();
    var random = new Random();
    for (var i = 0; i < 100; i++)
    {
        var index = random.Next(primeList.Count);
        answer.Add(primeList[index]);
    }
    return answer;
}

Longer, Low Memory Solution

If you don’t have sufficient memory to produce the largest possible list of 32 bit primes, the solution is a lot longer and slower, as it requires two-passes over the enumerable collection. For the 2nd pass, you can exit early once the full answer is known.

private IList<uint> GetRandom100LowMemory(uint upperLimit)
{
    // To produce this answer without a list of primes requires two-passes.
    // The 2nd pass can exit early.
    var primes = Sieve32.Primes(upperLimit);
    // Fully loop over to get count
    var primeCount = 0;
    foreach (var prime in primes)
    {
        primeCount++;
    }
    // Initialize dictionary of 100 random sequences.
    IDictionary<int, uint> dict = new Dictionary<int, uint>();
    var random = new Random();
    for (var i = 0; i < 100; i++)
    {
        dict.Add(random.Next(primeCount) + 1, 0u);
    }
    // For early loop termination, find max sequence.
    var maxSequence = dict.Keys.Max();
    // Loop again to assign primes to dict.
    var sequence = 0;
    foreach (var prime in primes)
    {
        sequence++;
        if (dict.ContainsKey(sequence))
        {
            dict[sequence] = prime;
            if (sequence == maxSequence)
            {
                break;
            }
        }
    }
    return dict.Values.ToList();
}

Questions

Being this is CR, there is always an implied question of “Do you have any constructive comments?”

Are there better ways to address the challenge problem while keeping the sieve simple?

\$\endgroup\$
3
\$\begingroup\$

Short because from phone...

  • use TryGetValue() instead of ContainsKey() for the dictionary.

  • use a class level random rather than a method level random.

  • why do you throw an ArgumentException for a upperLimit < 2 instead of "yielding" a break ? I guess the messagepart of the exception is just a typo.

\$\endgroup\$
  • \$\begingroup\$ Only the 3rd bullet item refers to the sieve. I throw the exception as a slap in the face that only numbers >= 2 can be considered prime, although yield break works equally well but with less friction. Good tip. \$\endgroup\$ – Rick Davin Jun 2 '15 at 22:55
  • \$\begingroup\$ The first 2 bullet items refer to the solutions to the challenge problem. I was lazy with random in order to provide an answer that was self contained. But you're right - random should be class level. And the TryGetValue() is a rock solid tip. Just read more about it on SO. Thanks again. \$\endgroup\$ – Rick Davin Jun 2 '15 at 22:58

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.