Summing the values of an array is a common operation. If the naive implementation is used, simply adding each new array element to the accumulated sum of all the previous, there will be an overall round-off error proportional to the number of terms added. For a small array this is negligible but for a large array it may matter. One way to avoid the accumulated round-off error is to use pairwise summation. This is a recursive divide-and-conquer algorithm which checks to see if the input array length is below a cutoff value, say five elements, and if so it returns their sum by simply adding them together. Otherwise, it takes the length of the input array, divides it by two using integer division, and calls itself on each of those subarrays adding the return values together to form the final output value. In pseudo-code,

Implement this function in C and Python. Demonstrate the effect of round-off by comparing the output of this function with the naive summation for input arrays of 10,000 elements or more. Use a pseudo-random number generator to generate values in the range [0,1).

Transcribed Image Text:

function pairwise (x) { if (length (x)