Calculation of prime numbers making use of Parallel.ForEach

Question

In my spare time I decided to write a program that would systematically identify prime numbers from 2 to 18,446,744,073,709,551,615. This is for fun and learning, as I know it will take too long to actually ever reach the upward value, but I'm using this to explore parallel processing. I know this is not a traditional question but I very much would like the critique of my peers. I know this can been torn apart, so please do, but if you do, do so constructively.

The program is designed to run until the user hits the esc key; at which time it will generate a file with all of the prime numbers discovered. The path to this file needs to be configured to a value for your directory structure. When I restart the program it will accept, as an argument, a primes text file, reading it in and starting from where it left off. The parallel processing portion and implementing the sieve for finding primes is what I was interested in woodshedding.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading.Tasks;

namespace Prime
{
    public class Program
    {
        public static void Main(string[] args)
        {
            List<UInt64> primes = new List<UInt64>();
            primes.Add(2);
            UInt64 numberToCheck = 3;

            if (args.Count() > 0)
            {
                numberToCheck = ReadPrimesToList(args[0].ToString(), out primes) +2;
            }

            try
            {
                bool quit = false;
                Console.WriteLine("Prime Number Search");

                while (!quit)
                {
                    if (Console.KeyAvailable)
                        quit = Console.ReadKey().Key == ConsoleKey.Escape;

                    Console.Write("Processing: " + numberToCheck);

                    if (CheckForPrime(numberToCheck, primes))
                    {
                        primes.Add(numberToCheck);
                        Console.WriteLine(" Prime Found!");
                    }
                    else
                        Console.WriteLine(" Not Prime :(");

                    if (numberToCheck < UInt64.MaxValue)
                        numberToCheck+=2;
                    else
                        break;
                }

                Console.WriteLine("Exiting");
                WritePrimesToFile(primes);
                Console.WriteLine("< Press Any Key To Exit >");
                Console.ReadKey();
            }
            catch
            {
                if (primes.Count > 0)
                    WritePrimesToFile(primes);
            }
        }

        private static UInt64 ReadPrimesToList(string fileName, out List<UInt64> primes)
        {
            primes = new List<UInt64>();
            FileInfo file = new FileInfo(fileName);
            StreamReader reader = new StreamReader(file.OpenRead());

            String lineIn = String.Empty;
            while (!reader.EndOfStream)
            {
                lineIn = reader.ReadLine();
                String[] numberStrings = lineIn.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
                foreach (String numberString in numberStrings)
                {
                    primes.Add(UInt64.Parse(numberString));
                }
            }

            return primes[primes.Count() - 1];
        }

        private static void WritePrimesToFile(List<UInt64> primes)
        {
            String dateAndTime = DateTime.Now.ToString("yyyyMMddhhmm");
            String fileName = String.Format(@"<substitute your path here>\primes [{0}].txt", dateAndTime);
            FileInfo file = new FileInfo(fileName);
            using (StreamWriter writer = file.CreateText())
            {
                int maxLength = primes[primes.Count - 1].ToString().Length;

                String line = String.Empty;
                const int maxColumn = 16;
                int column = 0;


                foreach (UInt64 number in primes)
                {
                    string numberString = number.ToString();
                    int numberLength = numberString.Length;

                    line += numberString.PadLeft(maxLength, ' ') + ((column < (maxColumn-1)) ? " " : String.Empty);

                    column++;

                    if (column == maxColumn)
                    {
                        writer.WriteLine(line);
                        line = string.Empty;
                        column = 0;
                    }
                }

                if (line.Length > 0)
                    writer.WriteLine(line);

                writer.Flush();
                writer.Close();
            }
        }

        private static bool CheckForPrime(UInt64 numberToCheck, List<UInt64> primes)
        {
            if ((numberToCheck % 2) == 0)
                return false;

            UInt64 halfway = (UInt64)(Math.Ceiling((float)numberToCheck / 2F));

            bool isprime = false;
            UInt64 factor = 0;

            Parallel.ForEach<UInt64>(primes, (prime, loopState) =>
            {
                if (prime > halfway)
                {
                    isprime = true;
                    loopState.Stop();
                }

                if ((numberToCheck % prime) == 0)
                {
                    factor = prime;
                    isprime = false;
                    loopState.Stop();
                }
            });

            return (isprime && factor == 0);
        }
    }
}

Answer 1

Answers so far failed to inform you that this code is completely wrong:

if (prime > halfway)
{
    isprime = true;
    loopState.Stop();
}

You can't do that on Parallel.Foreach - there's no guarantee as to the order of execution. That's the whole point of the parallel loop!

if (prime > halfway)
{
    loopState.Break(); // join all 'previous' jobs 
    return; // terminate *this* job, not caring about others
}

Another serious flaw is the condition itself - that fails as soon as checking 3. Should be:

if (prime >= halfway)

Another important thing, is that for this specific task, plain good ol` sequential for(...) is very likely to outperform the parallel version.

My results for 1234567890, tested on Mono: (stupid me)

My results for 2^31 - 1, tested on Mono:

parallel: 5.3873 [ms], returned True
sequential: 1.0157 [ms], returned True
2147483647 : True

EDIT: I see some reports suggesting the Parallel.ForEach implementation on Mono is exceptionally slow - would be nice to have some alternative results from win dudes.

Note about 'hitting memory boundry':

I hit the memory limits running from 2 to 1339484197

Let's make a fun math game:

1. The number of primes less than N is approximated by N / ln(N).
2. Our maximum list capacity is 2GB (32/64 bit alike). If you run on 32 bit, your whole process available memory is 2GB altogether. So you cannot even have that.
3. We're using long, so each prime occupies 8 bytes.
4. And to add more evil, we didn't allocate list size in advance, so we're operating on doubling mode. That means every time we have 2^N elements, we're allocating space for 2*2^N more, thus momentarily using 3x the space needed for the actual list. So what happened here?
5. We were at N = 1339484197, so the list had ~ N/ln(N) elements => ~ 64M primes
6. Each prime takes 8 bytes, so we're eating ~500MB of memory.
7. Now we add on more item and need to double, so we have to allocate 1GB more. That's 1.5GB altogether. Too much.
8. Now to the good news: We can get x3 primes more just by passing a MAX_SIZE to the List c'tor. Indeed, we can get x6, as one side implication of the above math game, is that we can safely use UInt32.

Answer 2

Console.Write is horribly slow. I mean it's not that bad, but it's worse than you might think.

Try something like:

if((numberToCheck + 1) % 1000 == 0)
   Console.Write("Processing: " + numberToCheck);

I've had many cases where updating the console less often resulted in a massive speed boost. A good rule is not to update the console more than a few times per second.

Answer 3

For checking a the primeness of several numbers, you should use Sieve of Eratosthenes. It is two simple loops you can parallelize, and the time complexity is just O(n log(n) log log (n)).

Also, as Hannesh said, writing to the console is incredibly slow, I guess you should probably avoid writing "Processing some number" and just wrute the last number processed at the end.

Console functions also create a bottleneck, specially if you check them after every number, I would check numbers in batches of 1000 or 10000 before asking if the user is pressing a key.

Answer 4

Here is a super cute realization which I've seen in a book. If you wish you could optimize it.

IEnumerable<int> numbers = Enumerable.Range(3, 100000);
var parallelQuery =
    from n in numbers.AsParallel()
    where Enumerable.Range(2, (int)Math.Sqrt(n)).All(i => n % i > 0)
    select n;

int[] primes = parallelQuery.ToArray();

Answer 5

Hmmmm... To speed it up, I'd look into alternate Prime Number tests, like Miller Rabin Test or AKS Test

Here is a sample of code for the Miller Rabin algorithm written in C#. Maybe it can be parallelized and work faster than the method you currently have?

Answer 6

You could consider tweaking the prime test to bail out as soon as you reach a prime that is >= sqrt(numberToTest). The proof (very loosely) is that a composite number can always be written as the product of two integer factors, each > 1. Of the two factors, one must be necessarily <= the other. Thus you can stop testing when you reach the worst-case upper bound which is the square root of the test number. Other more efficient means exist for testing primes, but this tweak requires remarkably little code.

Here's a summary of my tweaks:

• Removed "halfway" and "factor" variables & their use. They may have had value for debugging purposes, but they seem to detract from the overall goal of the method.
• Defaulted isprime to true - if we make it all the way through the candidate factors without finding one that is divisible, then isprime = true is the correct value to return.
• Avoided computing the square root of numberToCheck by changing the condition to first square the candidate factor and compare the result with numberToCheck in the LINQ Where call. This could eat up time when testing much larger numbers if the repeated multiplications outweigh the cost of computing an integer square root.
• The manner I chose to filter the primes using the LINQ Where could have a negative performance impact based on how the TPL parititions the work. I recall reading a post from the TPL team that they partition the work differently for indexable IEnumerables, and I wanted to provide the link here, but I am having trouble locating it. In short, this might offset the performance improvement bailing out earlier might provide.

Regardless, here are the above tweaks (untested):

private static bool CheckForPrime(UInt64 numberToCheck, List<UInt64> primes)
{
    if ((numberToCheck % 2) == 0)
        return false;

    bool isprime = true;

    Parallel.ForEach(primes.Where(prime => prime*prime < numberToCheck),
        (prime, loopState) =>
        {
            if ((numberToCheck % prime) == 0)
            {
                isprime = false;
                loopState.Stop();
            }
        });

    return isprime;
}