Сандық талдаудағы қателерді азайту алгоритмдері

Algorithm in numerical analysis
In numerical analysis, the Kahan summation algorithm, also known as compensated summation, significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious approach. This is done by keeping a separate running compensation (a variable to accumulate small errors), in effect extending the precision of the sum by the precision of the compensation variable. In particular, simply summing numbers in sequence has a worst case error that grows proportional to , and a root mean square error that grows as for random inputs (the roundoff errors form a random walk). With compensated summation, using a compensation variable with sufficiently high precision the worst case error bound is effectively independent of , so a large number of values can be summed with an error that only depends on the floating point precision of the result. Ivo Babuška seems to have come up with a similar algorithm independently (hence Kahan–Babuška summation). Similar, earlier techniques are, for example, Bresenham's line algorithm, keeping track of the accumulated error in integer operations (although first documented around the same time) and the delta sigma modulation.

Although Kahan's algorithm achieves error growth for summing n numbers, only slightly worse growth can be achieved by pairwise summation: one recursively divides the set of numbers into two halves, sums each half, and then adds the two sums. In practice, with roundoff errors of random signs, the root mean square errors of pairwise summation actually grow as Another method that uses only integer arithmetic, but a large accumulator, was described by Kirchner and Kulisch; a hardware implementation was described by Müller, Rüb and Rülling.

In general, built in "sum" functions in computer languages typically provide no guarantees that a particular summation algorithm will be employed, much less Kahan summation. The BLAS standard for linear algebra subroutines explicitly avoids mandating any particular computational order of operations for performance reasons, and BLAS implementations typically do not use Kahan summation. The standard library of the Python computer language specifies an fsum function for accurate summation. Starting with Python 3.12, the built in "sum " function uses the Neumaier summation. In the Julia language, the default implementation of the sum function does pairwise summation for high accuracy with good performance, but an external library provides an implementation of Neumaier's variant named sum kbn for the cases when higher accuracy is needed. In the C# language, HPCsharp nuget package implements the Neumaier variant and pairwise summation: both as scalar, data parallel using SIMD processor instructions, and parallel multi core.