Algoritmo di sommatoria di Kahan

In analisi numerica, l'algoritmo di sommatoria di Kahan (conosciuto anche come sommatoria compensata) riduce significativamente l'errore numerico nel totale ottenuto sommando una sequenza di numeri in virgola mobile con precisione finita, se confrontato con il consueto procedimento. Ciò è ottenuto mantenendo una compensazione progressiva separata (una variabile per accumulare piccoli errori). Quando rappresentiamo un generico numero reale in virgola mobile con precisione finita, ossia con un numero finito di cifre significative, tale rappresentazione, rispetto al numero reale considerato, differisce di un certo valore, il quale corrisponde all'errore di arrotondamento ed è lo scarto tra la rappresentazione in virgola mobile e il numero stesso. Eseguendo una semplice sommatoria di più numeri reali, utilizzando però le rispettive rappresentazioni in virgola mobile, il totale ottenuto presenta un certo errore dato dalla somma algebrica dei singoli errori di arrotondamento, ossia dei singoli scarti, ed, inoltre, si ottiene un certo scarto quadratico medio, in inglese root mean square error, inteso come la radice quadrata della media aritmetica dei quadrati dei singoli scarti. In particolare, la sommatoria semplice di numeri in sequenza presenta un errore che, nel caso peggiore, cresce proporzionalmente ad ed uno scarto quadratico medio che cresce come per addendi casuali (gli errori di arrotondamento producono una passeggiata aleatoria). Invece, con la sommatoria compensata, l'errore peggiore possibile è indipendente da , dunque un gran numero di valori possono essere sommati con un errore che dipende solo dalla precisione della rappresentazione in virgola mobile. L'algoritmo è attribuito a William Kahan. Tecniche precedenti simili sono, per esempio, l'algoritmo della linea di Bresenham, che mantiene traccia dell'errore accumulato nelle operazioni sugli interi (anche se già presente in un articolo pubblicato circa nello stesso periodo) e la modulazione Sigma-Delta (che integra e non soltanto somma l'errore).