[R] Best way to compute a sum

[Duncan Murdoch]

On 24/06/2010 4:39 PM, Peter Langfelder wrote:
> 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 
Isn't that what I said?

Duncan Murdoch


> (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
>