On 08/06/16 01:53, Emilio G. Cota wrote: > On Tue, Jun 07, 2016 at 17:06:16 +0300, Sergey Fedorov wrote: >> On 07/06/16 02:40, Emilio G. Cota wrote: >>> On Fri, Jun 03, 2016 at 20:46:07 +0300, Sergey Fedorov wrote: >>>> Maybe something like >>>> https://en.wikipedia.org/wiki/Kahan_summation_algorithm could help? >>> That algorithm is overkill for what we're doing. Pairwise summation >>> should suffice: >>> >>> diff --git a/util/qdist.c b/util/qdist.c >>> index 3343640..909bd2b 100644 >>> --- a/util/qdist.c >>> +++ b/util/qdist.c >>> @@ -367,20 +367,34 @@ unsigned long qdist_sample_count(const struct qdist >>> *dist) >>> return count; >>> } >>> >>> +static double qdist_pairwise_avg(const struct qdist *dist, size_t index, >>> + size_t n, unsigned long count) >>> +{ >>> + if (n <= 2) { >> We would like to amortize the overhead of the recursion by making the >> cut-off sufficiently large. > Yes, this was just for showing what it looked like. > > We can use 128 here like JuliaLang does: > https://github.com/JuliaLang/julia/blob/d98f2c0dcd/base/arraymath.jl#L366 > >
Probably cut-off of ~10 items would be enough to amortize the recursion in C. Kind regards, Sergey
