Julia High Performance - Second Edition

The K-B-N summation

Adding a collection of floating point values is a very common operation, but it is surprisingly susceptible to the accumulation of errors. A naïve implementation—adding the list from the first element to the last—accumulates errors at the rate of , where n is the number of elements being summed. Julia's sum base uses a pairwise summation algorithm that does better by accumulating errors at , but is almost as fast. However, there exists a more complicated summation algorithm attributed to William Kahan—the K-B-N summation—whose ...