Metraipolis › archive › dc_cb95239abbfa

Pairwise summation — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Pairwise_summation
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T23:32:06.437Z
SHA-256 of the archived text: f1500a9b3bb0a554606e112413ae4fae47f1a336afbd298e1933312f33a43b28
Stable URL of this page: https://metraipolis.com/documento/dc_cb95239abbfa

How to cite

Pairwise summation — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Pairwise_summation (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_cb95239abbfa (Metraipolis archive dc_cb95239abbfa, sha256 f1500a9b3bb0a554606e112413ae4fae47f1a336afbd298e1933312f33a43b28)

BibTeX

@misc{dccb95239abbfa,
  title = {Pairwise summation — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Pairwise_summation},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_cb95239abbfa; sha256 f1500a9b3bb0a554606e112413ae4fae47f1a336afbd298e1933312f33a43b28},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Pairwise_summation. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In numerical analysis, pairwise summation, also called cascade summation, is a summation algorithm, i.e. a technique to sum a sequence of finite-precision floating-point numbers that substantially reduces the accumulated round-off error compared to naively accumulating the sum in sequence. Although there are other techniques such as Kahan summation that typically have even smaller round-off errors, pairwise summation is nearly as good (differing only by a logarithmic factor) while having much lower computational cost—it can be implemented so as to have nearly the same cost (and exactly the same number of arithmetic operations) as naive summation. In particular, pairwise summation of a sequence of n numbers xn works by recursively breaking the sequence into two halves, summing each half, and adding the two sums: a divide and conquer algorithm. Its worst-case roundoff errors grow asymptotically as at most O(ε log n), where ε is the machine precision (assuming a fixed condition number, as discussed below). In comparison, the naive technique of accumulating the sum in sequence (adding each xi one at a time for i = 1, ..., n) has roundoff errors that grow at worst as O(εn). Kahan summation has a worst-case error of roughly O(ε), independent of n, but requires several times more arithmetic operations. If the roundoff errors are random, and in particular have random signs, then they form a random walk and the error growth is reduced to an average of O ( ε log n ) {\displaystyle O(\varepsilon {\sqrt {\log n}})} for pairwise summation. A very similar recursive structure of DFT decomposition is found in many fast Fourier transform (FFT) algorithms, and is responsible for the same slow roundoff accumulation of those FFTs when implemented with a breadth-first technique due to poor memory locality.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Numerical analysis»).
Fonte: Wikipedia in inglese, voce «Pairwise summation» — https://en.wikipedia.org/wiki/Pairwise_summation
Wikidata Q17104961 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q17104961
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Pairwise_summation?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1366836768, consultata il 2026-10-07T23:11:06.356Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f4fbdad39884748f8790e9e4e66a0609c836b384c45840cbe51e04a773765149