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