4 ms·
What about a "reduce" technique? Average the numbers in equal-sized chunks, then average those averages. You could even chunk the chunk averages and repeat the
by _bxg1 8y ago
What about a "reduce" technique? Average the numbers in equal-sized chunks, then average those averages. You could even chunk the chunk averages and repeat the process as many levels down as you want to, and chunks could be as small as 2 each.
I guess this still assumes that the largest number in the original list is less than or equal to the maximum floating point value, but otherwise you stay roughly in the same space of precision as the original data.
- svenhof 8y agoUnfortunately, by averaging the averages you skew the results. Average of averages does not produce the same result as averaging the whole list.
- sokoloff 8y agoAverage of equal size chunks' averages does. (mathematically)
- svenhof 8y agoAh my bad. Thanks for that correction
- umdiff 8y ago\left( \sum_{i=1}^m x_i/m + \sum_{i=m+1}^{2m} x_i/m \right) / 2 = \sum_{i=1}^{2m} x_i /(2m)
- BubRoss 8y agoIt does if you weight the chunks correctly. Combine pairs of numbers and keep a weight of the remaining odd number. Either cut the weight in half of the odd number every time or use it in the average if an iteration has an even number of numbers.
- svenhof 8y agoThanks for that, didn't know.
- umdiff 8y agoI think this works perfectly if your list has 2^n elements. Otherwise, you have to resort to multiplying by imprecise fractions.
- _bxg1 8y agoYou would only need one special case: if a list (top level or not) has 2n+1 numbers, weight the last one differently.
- rwz 8y agoThat produces an unavoidable special case when the number of elements in the list is a prime number.
- bhl 8y agoJust pad the end of the list with 0s, but keep the original size of the list.
- mannykannot 8y agoI believe you have pairwise / cascade summation in mind: https://en.wikipedia.org/wiki/Pairwise_summation https://en.wikipedia.org/wiki/Pairwise_summation