Incorrect Math Result

The algorithm is logically incorrect for a general associative reduction; it only happens to work for some inputs by coincidence.

Key issues:

1. Mixing odd-element handling into array[0] repeatedly
   • When count is odd, this line runs:

          if (r == 1)
              array[0] = func(array[0], source[count - 1]);
     

     That folds the last element into array[0] once.
   • Inside the loop, whenever length is odd, this runs again:

          if (length % 2 == 1)
              array[0] = func(array[0], array[length - 1]);
     

     This keeps reusing array[0] as a special accumulator while also treating it as a normal element in the pairwise combine step. That double role breaks the invariant that each element participates exactly once.
2. Pairwise combine loop assumes length is even
   • The loop:

          for (int index = 0; index < length; index++)
          {
              if (index % 2 == 0)
              {
                  int setIndex = index / 2;
                  int getIndex = index + 1;
                  int input1 = array[index];
                  int input2 = array[getIndex];
                  int result = func(input1, input2);
                  array[setIndex] = result;
              }
          }
     

     assumes that for every even index, index + 1 is a valid partner. When length is odd, index + 1 for the last even index is out of the logical range of elements that should be combined in this pass. The code tries to compensate by pre-folding the last element into array[0], but that interacts badly with the reuse of array[0] in the same pass.
3. length is halved blindly
   • After each pass:

          length = length / 2;
     

     This is correct only if the pass always reduces length elements to exactly length / 2 results. Because odd lengths are handled by mutating array[0] and then still running the same pairwise loop, the actual number of logical results in array[0..) no longer matches length / 2 in a consistent way.
4. Parallelization would introduce race conditions
   • The commented Parallel.For:

          //Parallel.For(0, length, (int index) =>
     

     If re-enabled as-is, multiple threads would write to the shared array without synchronization. Even though each setIndex is unique for each even index, the combination with the odd-length handling and reuse of array[0] makes correctness highly fragile. Parallel writes to shared state without proper design can lead to unpredictable results, as illustrated in the PLINQ race-condition example where total += n is unsafe when run in parallel.
5. Why it “sometimes” works
   • For small, even-sized lists and simple associative func like addition, the particular pattern of pairwise combination happens to produce the same result as a straightforward fold.
   • As soon as the size, parity, or function changes, the flawed odd-element handling and reuse of array[0] cause elements to be combined in the wrong order or multiple times.

A correct reduction should:

• Treat array[0..length-1] as exactly length active elements.
• For each pass, combine elements in disjoint pairs into the first length/2 positions.
• If length is odd, carry the last element forward separately (e.g., copy it to array[length/2]) instead of folding it into array[0].
• Update length to the exact new count of active elements.

For example, a safer structure (still single-threaded) is:

public static int Reduce(this List<int> source, Func<int, int, int> func)
{
    int[] array = source.ToArray();
    int length = array.Length;

    while (length > 1)
    {
        int newLength = length / 2;
        int i = 0;

        // pairwise combine
        for (; i + 1 < length; i += 2)
        {
            array[i / 2] = func(array[i], array[i + 1]);
        }

        // carry last element if odd
        if (i < length)
        {
            array[newLength] = array[i];
            newLength++;
        }

        length = newLength;
    }

    return array[0];
}

This ensures each element is used exactly once per level and avoids the special-case accumulation into array[0] that causes the incorrect results.

References:

• Potential pitfalls with PLINQ
• Enumerable.Aggregate Method
• Queryable.Aggregate Method

Hi @Jude Grey ,

Thanks for reaching out.

It looks like the issue is likely coming from the Parallel.For version reading from and writing to the same array during the same pass. Because those iterations can run in any order, one iteration may update a value that another iteration was still about to read. So, that can make the result depend on timing, which would fit with why you sometimes see the expected value and sometimes do not.

For example, one iteration can write back into the lower part of the array while another iteration is still reading from that same part. That would also explain why the regular for loop behaves consistently while the parallel version only works some of the time. In the sequential loop, the reads and writes happen in a fixed order. In the parallel loop, they can overlap.

The way to avoid that is to use a separate output array for each reduction pass, so each thread reads from the current array and writes to a different array instead of modifying the same one in place. For example:

public static int Reduce(this List<int> source, Func<int, int, int> func)
{
  if (source == null)
    throw new ArgumentNullException(nameof(source));

  if (func == null)
    throw new ArgumentNullException(nameof(func));

  if (source.Count == 0)
    throw new InvalidOperationException("The source sequence is empty.");

  int[] current = source.ToArray();
  int length = current.Length;

  while (length > 1)
  {
    int pairCount = length / 2;
    int nextLength = pairCount + (length % 2);
    int[] next = new int[nextLength];

    Parallel.For(0, pairCount, i =>
    {
      next[i] = func(current[i * 2], current[i * 2 + 1]);
    });

    if (length % 2 == 1)
      next[nextLength - 1] = current[length - 1];

    current = next;
    length = nextLength;
  }

  return current[0];
}

One other thing to keep in mind is that this kind of parallel reduction generally only works as expected when the operation can be regrouped without changing the result, such as addition. If you pass in a more general function, the result still may not match a normal left-to-right reduction even after removing the race condition.

If your goal here is just to sum the list, numbers.Sum() would probably be the simplest choice. If you want to keep the reduction pattern but do it sequentially, numbers.Aggregate((x, y) => x + y) would also be a reasonable option.

Hope this helps! If my answer was helpful, I would greatly appreciate it if you could follow the instructions here so others with the same problem can benefit as well.