accuracy of intrinsic SUM function

[Schorsch MCMLX]

AFAIK, the only problem of the pairwise algo is to define its 
behaviour in case of an odd number of elements that are to be summed 
up. The self-written function on which the results published in my 
initial email were based on does not use recursion as I wanted to 
avoid stack problems. Instead, it uses a local array of size n_val/2 
that is overridden in each subsequent step. The superior accuracy of 
the FTN95 results indicates that my decision to add the last element 
of an odd number of values to a randomly chosen sum of two parent 
elements is sub-optimal. It might be better to start with the 
last/first sum and keep track of that decision in order to minimise 
the overall amount of additions of un-balanced sums...
Basically, the amount of additions of the pairwise algo depends on the
amount of occurrences of an odd number of array elements: if the 
initial number of array elements equals a power of two, there are no 
more additions than in the recurrent algo. Moreover, due to the binary
tree structure of the additions, this algo can be easily and 
effectively parallelised. Worst case is if the number of array 
elements is smaller than a power of two by 1. 

Kahan's or compensated summation requires at least three times the 
number of additions of the recurrent algo plus the evaluation of an if
statement in each step (Knuth's/Kahan's three step algo requires the 
first variable to be the largest in absolute terms...). Though it is 
not mentioned in Higham's book (see wikipedia for reference), I 
suspect it might be best to fill up the array of values with zeroes in
case N >= 1.5*(2**floor(log2(N)) in order to make N_fill equal a power
of 2...

There seems not to exist an overall optimal summation algo, as can be 
concluded from the overwhelming variety of scientific papers on 
"adaptive statictics". Indeed, Higham even recommends even sorting the
values before summing them up in some situations. On the other hand, 
the recurrent algo seems to be the overall worse. 

Unfortunately, I do not want to provide timing information at the 
moment, as I'm currently fighting against the confusing results 
obtained when calling QueryPerformanceCounter (yielding in a constant 
frequency my proc. never attains)  as opposed to the WMI results 
indicating that each of my 4 logical cores steps from 1184 MHz up to 
3200Mhz during a timespan of 10musec. I'm even less familiar with 
performance  measurements in the Linux environment...

If somebody is interested in the F-code I used, please let me know; I 
did not post it because I thought gFortran uses C or ASM as 
back-bone...

All the best 
Schorsch