On 24/06/2010 4:39 PM, Peter Langfelder wrote:
On Thu, Jun 24, 2010 at 1:26 PM, Duncan Murdoch
<murdoch.dun...@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
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
