[R] Best way to compute a sum

[Peter Langfelder]

On Thu, Jun 24, 2010 at 1:26 PM, Duncan Murdoch
<murdoch.duncan at gmail.com> wrote:
> On 24/06/2010 4:08 PM, Lasse Kliemann wrote:

>> What is the best way in R to compute a sum while avoiding cancellation
>> effects?
>>
>
> Use sum().  If it's not good enough, then do it in C, accumulating in
> extended precision (which is what sum() does), from smallest to largest if
> all terms are positive.  If there are mixed signs it's a lot harder to
> optimize, but I believe the optimal order would be something like the one
> that keeps each partial sum as close as possible to zero.  It would rarely
> be practical to implement that, so summing from smallest absolute value to
> largest would be my recommendation.

AFAIK the optimal way of summing a large number of positive numbers is
to always add the two smallest numbers (and update the list of
numbers). For example, summing 0.1, 0.2, 0.25, and 0.27, you would
first add 0.1 and 0.2 = 0.3, then, from 0.3, 0.25 and 0.27 you add
0.25 + 0.27 = 0.52, then 0.3 + 0.52. The initial sort of the numbers
would take ~n*log(n) operations, and maintaining the order should be
doable in <log(n) operations per sum step, so the whole sum would take
~n*log(n) operations instead of just n operations.

I'm not aware of anything of this sort being implemented in R.

Peter