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?
