Overflow exception while performing parallel factorization using the .NET Task Parallel Library (TPL)

Question

Hello, I'm trying to write a not so smart factorization program and trying to do it in parallel using TPL. However, after about 15 minutes of running on a core 2 duo machine, I am getting an aggregate exception with an overflow exception inside it. All the entries in the stack trace are part of the .NET framework, the overflow does not come from my code. Any help would be appreciated in figuring out why this happens.

Here's the commented code, hopefully it's simple enough to understand:

class Program
{
    static List<Tuple<BigInteger, int>> factors = new List<Tuple<BigInteger, int>>();

    static void Main(string[] args)
    {
        BigInteger theNumber = BigInteger.Parse(
            "653872562986528347561038675107510176501827650178351386656875178" +
            "568165317809518359617865178659815012571026531984659218451608845" +
            "719856107834513527");
        Stopwatch sw = new Stopwatch();
        bool isComposite = false;
        sw.Start();

        do
        {
            /* Print out the number we are currently working on. */
            Console.WriteLine(theNumber);

            /* Find a factor, stop when at least one is found
               (using the Any operator). */
            isComposite = Range(theNumber)
                          .AsParallel()
                          .Any(x => CheckAndStoreFactor(theNumber, x));

            /* Of the factors found, take the one with the lowest base. */
            var factor = factors.OrderBy(x => x.Item1).First();
            Console.WriteLine(factor);

            /* Divide the number by the factor. */
            theNumber = BigInteger.Divide(
                            theNumber, 
                            BigInteger.Pow(factor.Item1, factor.Item2));

            /* Clear the discovered factors cache, and keep looking. */
            factors.Clear();
        } while (isComposite);

        sw.Stop();
        Console.WriteLine(isComposite + " " + sw.Elapsed);
    }

    static IEnumerable<BigInteger> Range(BigInteger squareOfTarget)
    {
        BigInteger two = BigInteger.Parse("2");
        BigInteger element = BigInteger.Parse("3");
        while (element * element < squareOfTarget)
        {
            yield return element;
            element = BigInteger.Add(element, two);
        }
    }

    static bool CheckAndStoreFactor(BigInteger candidate, BigInteger factor)
    {
        BigInteger remainder, dividend = candidate;
        int exponent = 0;
        do
        {
            dividend = BigInteger.DivRem(dividend, factor, out remainder);
            if (remainder.IsZero)
            {
                exponent++;
            }
        } while (remainder.IsZero);
        if (exponent > 0)
        {
            lock (factors)
            {
                factors.Add(Tuple.Create(factor, exponent));
            }
        }
        return exponent > 0;
    }
}

Here's the exception thrown:

Unhandled Exception: System.AggregateException: One or more errors occurred. ---
> System.OverflowException: Arithmetic operation resulted in an overflow.
   at System.Linq.Parallel.PartitionedDataSource`1.ContiguousChunkLazyEnumerator.MoveNext(T& currentElement, Int32& currentKey)
   at System.Linq.Parallel.AnyAllSearchOperator`1.AnyAllSearchOperatorEnumerator`1.MoveNext(Boolean& currentElement, Int32& currentKey)
   at System.Linq.Parallel.StopAndGoSpoolingTask`2.SpoolingWork()
   at System.Linq.Parallel.SpoolingTaskBase.Work()
   at System.Linq.Parallel.QueryTask.BaseWork(Object unused)
   at System.Linq.Parallel.QueryTask.<.cctor>b__0(Object o)
   at System.Threading.Tasks.Task.InnerInvoke()
   at System.Threading.Tasks.Task.Execute()
   --- End of inner exception stack trace ---
   at System.Linq.Parallel.QueryTaskGroupState.QueryEnd(Boolean userInitiatedDispose)
   at System.Linq.Parallel.SpoolingTask.SpoolStopAndGo[TInputOutput,TIgnoreKey](QueryTaskGroupState groupState, PartitionedStream`2 partitions, SynchronousChannel`1[] channels, TaskScheduler taskScheduler)
   at System.Linq.Parallel.DefaultMergeHelper`2.System.Linq.Parallel.IMergeHelper<TInputOutput>.Execute()
   at System.Linq.Parallel.MergeExecutor`1.Execute[TKey](PartitionedStream`2 partitions, Boolean ignoreOutput, ParallelMergeOptions options, TaskScheduler taskScheduler, Boolean isOrdered, CancellationState cancellationState, Int32 queryId)

   at System.Linq.Parallel.PartitionedStreamMerger`1.Receive[TKey](PartitionedStream`2 partitionedStream)
   at System.Linq.Parallel.AnyAllSearchOperator`1.WrapPartitionedStream[TKey](PartitionedStream`2 inputStream, IPartitionedStreamRecipient`1 recipient, BooleanpreferStriping, QuerySettings settings)
   at System.Linq.Parallel.UnaryQueryOperator`2.UnaryQueryOperatorResults.ChildResultsRecipient.Receive[TKey](PartitionedStream`2 inputStream)
   at System.Linq.Parallel.ScanQueryOperator`1.ScanEnumerableQueryOperatorResults.GivePartitionedStream(IPartitionedStreamRecipient`1 recipient)
   at System.Linq.Parallel.UnaryQueryOperator`2.UnaryQueryOperatorResults.GivePartitionedStream(IPartitionedStreamRecipient`1 recipient)
   at System.Linq.Parallel.QueryOperator`1.GetOpenedEnumerator(Nullable`1 mergeOptions, Boolean suppressOrder, Boolean forEffect, QuerySettings querySettings)
   at System.Linq.Parallel.QueryOpeningEnumerator`1.OpenQuery()
   at System.Linq.Parallel.QueryOpeningEnumerator`1.MoveNext()
   at System.Linq.Parallel.AnyAllSearchOperator`1.Aggregate()
   at System.Linq.ParallelEnumerable.Any[TSource](ParallelQuery`1 source, Func`2 predicate)
   at PFact.Program.Main(String[] args) in d:\myprojects\PFact\PFact\Program.cs:line 34

Any help would be appreciated.

Thanks!

EDIT

Following Simon's reply, I ran the code again, this time with a catch(AggregateException x) clause, and I examined all the elements in the InnerExceptions collection. There were exactly 2 elements (I assume that's one for each thread of execution, since I have 2 CPU cores, TPL would optimize to use only 2 threads). Both exceptions were identical (both were OverflowException)... So that's not the answer.

SOLUTION

Henk's answer turns out to be correct, and here's the semi-official link from a microsoft blog confirming that: What's New in Beta 2 for PLINQ

Answer 1

This is largely a guess because haven't yet ran your code for 15 minutes to test it =;-) but given that you are getting an overflow exception, could it be that the value of exponent is growing larger than 2,147,483,647.

int exponent = 0;

perhaps make it:

BigInteger exponent = 0;

I would expect to see the CheckAndStoreFactor method on the stack trace of one of the inner exceptions though. (Remember AggregateException has an InnerExceptions property which could contain multiple inner exceptions.)

Answer 2

Looking through your stacktrace, near the top, I see this:

at System.Linq.Parallel.PartitionedDataSource`1.
  ContiguousChunkLazyEnumerator.MoveNext(T& currentElement, Int32& currentKey)
at System.Linq.Parallel.AnyAllSearchOperator`1.
  AnyAllSearchOperatorEnumerator`1.MoveNext(Boolean& currentElement, Int32& currentKey)

Now this looks like the TPL enumerator is using Int32 for it's own internal bookkeeping, and you just may be doing more than Int32.MaxValue iterations...

To be sure you would have to look at the IL of the generated statemachine for the iterator block.