LINQ List.AsParallel with boolean return

Question

I've got a static List<long> primes of all known primes up to a certain point, and a function like this:

static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    foreach (long q in primes)
    {
        if (p % q == 0)
            return false;

        if (q >= rootP)
            return true;
    }

    return true;
}

which could be parallelised like this:

static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    primes.AsParallel().ForAll(q =>
        {
            if (p % q == 0)
                return false;

            if (q > rootP)
                break;
        });

    return true;
}

However, this gives a compile-time error saying some return types in my block aren't implicitly convertible to the delegate return type.

I'm somewhat new to LINQ, especially PLINQ. This, to me, seems like a good candidate for parallelism, since the checking of each known prime against the candidate prime is an independent process.

Is there an easy way to fix my block so that it works, or do I need to attack this problem in a completely different way?

Answer 1

Syntax-wise, you're making two mistakes in your code:

1. A return in a lambda doesn't return from the enclosing method, just from the lambda, so your return false; wouldn't work correctly.
2. You can't break out of lambda. Even if that lambda is executed in a loop, that loop is basically invisible to you, you certainly can't control it directly.

I think the best way to fix your code is to use a LINQ method made exactly for this purpose: Any(), along with TakeWhile() to filter out the primes that are too large:

static bool IsPrime(long p)
{
    double rootP = Math.Sqrt(p);

    return !primes.AsParallel().TakeWhile(q => q > rootP).Any(q => p % q == 0);
}

But there is also a flaw in your reasoning:

This, to me, seems like a good candidate for parallelism, since the checking of each known prime against the candidate prime is an independent process.

It's not as simple as that. Checking each prime is also an extremely simple process. This means that the overhead of simple parallelization (like the one I suggested above) is likely to be bigger than the performance gains. A more complicated solution (like the one suggested by Matthew Watson in a comment) could help with that.

Answer 2

This is a solution to your problem:

static List<long> primes = new List<long>() {
  2,3,5,7,11,13,17,19,23
};

static bool isPrime(long p) {
  var sqrt = (long)Math.Sqrt(p);
  if (sqrt * sqrt == p)
    return (false);
  return (primes.AsParallel().All(n => n > sqrt || p % n != 0));
}

It even tries to reduce parallelism for quadratic numbers and will stop checking more candidates as soon as the first is found which is

Answer 3

The error occurs because if your condition

p % q == 0

is true the closure will return false and when

q > rootP

it breaks and returns nothing. This will work in PHP but not in .NET :P

A lambda is a full anonymous function and return types allways have to be consistent.

You have to redesign your code here. You have done it right in your non-parallelised example... Just replace break with return true (it won't be prettier then, but it should work).

Answer 4

It maybe easier to use Parallel.For instead

static volatile bool result = true;
static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    Parallel.For(0, primes.Count, (q, state) =>
        {
            if (p % q == 0)
            {
                result = false;
                state.Break();
            }

            if (q > rootP)
                state.Break();
        });

    return result;
}