Algorytm Kahana: Problemy arytmetyki zmiennoprzecinkowej przy sumowaniu milionów wartości w pamięci operacyjnej

W większości języków programowania liczby typu float i double nie są przechowywane dokładnie. Komputer zapisuje je binarnie, w skończonej liczbie bitów. To oznacza, że część liczb dziesiętnych nie ma dokładnej reprezentacji w pamięci. Typowy przykład to 0.1, które w IEEE 754 staje się przybliżeniem. Przy pojedynczych operacjach błąd zwykle jest mały, ale przy długich sumowaniach zaczyna się kumulować.

W praktyce problem pojawia się szybciej niż wiele osób zakłada. Sumowanie milionów próbek z czujników, danych giełdowych albo wyników obliczeń numerycznych potrafi dać wynik różniący się od oczekiwanego o kilka, kilkanaście albo nawet setki jednostek najmniejszej dokładności. Właśnie w takich sytuacjach stosowany jest Algorytm Kahana.

Algorytm Kahana i mechanizm kompensacji błędu utraconego podczas dodawania liczb zmiennoprzecinkowych

Klasyczne sumowanie wygląda bardzo prosto:

Problem polega na tym, że podczas dodawania liczby bardzo małej do bardzo dużej część bitów jest tracona. Procesor musi wyrównać wykładniki liczb. Mniejsze wartości tracą wtedy fragment precyzji.

Przykład:

W arytmetyce IEEE 754 dla double dodanie 1.0 do tak dużej liczby może nie zmienić wyniku. Jednostka zostanie „zgubiona”.

Klasyczny algorytm:

nie pamięta utraconego błędu.

Kahan zauważył, że można przechowywać tę utraconą część osobno i próbować odzyskać ją przy kolejnych operacjach.

Mechanizm działa przez dodatkową zmienną kompensacji.

Podstawowa idea:

Przy każdym dodaniu wykonywana jest korekta:

Formalnie:

Ta jedna dodatkowa zmienna często radykalnie zmniejsza błąd numeryczny.

Dlaczego kolejność dodawania danych wejściowych zmienia końcowy wynik obliczeń numerycznych

W matematyce:

$(a+b)+c=a+(b+c)$(a+b)+c=a+(b+c)

W komputerze dla liczb zmiennoprzecinkowych to nie zawsze działa.

Przykład:

Matematycznie oba wyrażenia są równe 1.

W praktyce pierwszy wariant traci małą wartość podczas dodawania do dużej liczby.

To bardzo ważne w:

W wielu bibliotekach numerycznych kolejność danych jest kontrolowana właśnie z powodu błędów zaokrągleń.

Dodatkowy problem pojawia się przy równoległości. Procesory wielordzeniowe sumują fragmenty danych niezależnie, a później łączą wyniki. Różna kolejność operacji daje czasem różne rezultaty między uruchomieniami programu. To częsty problem przy debugowaniu obliczeń naukowych.

Implementacja Algorytm Kahana w języku C, C++ oraz Python wraz z analizą dokładności obliczeń

Najprostsza implementacja w C:

Wynik:

Implementacja C++:

Implementacja Python:

W Pythonie problem nadal istnieje, mimo że float jest oparty o double.

Warto zwrócić uwagę, że Kahan nie eliminuje błędu całkowicie. On jedynie minimalizuje utratę informacji.

Przy bardzo ekstremalnych danych nadal mogą wystąpić odchylenia.

Analiza błędów zaokrągleń w standardzie IEEE 754 i wpływ ograniczonej precyzji na wyniki obliczeń

Standard IEEE 754 definiuje sposób przechowywania liczb zmiennoprzecinkowych.

Typ double:

Realna precyzja to około 15–17 cyfr dziesiętnych.

Jeżeli liczby znacząco różnią się skalą:

Klasyczny przykład:

To nie jest błąd Pythona. Tak działa reprezentacja binarna.

Liczba 0.1 w systemie binarnym rozwija się nieskończenie:

$0.1_{10}=0.0001100110011\ldots_2$0.110​=0.0001100110011…2​

Procesor musi ją obciąć.

W praktyce znaczenie ma również:

Cancellation jest szczególnie niebezpieczne. Gdy odejmujemy liczby prawie równe, znaczące cyfry się kasują.

Przykład:

W obliczeniach naukowych takie zjawisko może całkowicie zniszczyć stabilność algorytmu.

Gdzie stosuje się Algorytm Kahana i dlaczego bywa ważniejszy niż sama wydajność programu

W wielu projektach programista długo nie zauważa problemu. Program działa poprawnie na małych danych testowych. Problemy zaczynają się przy dużej skali.

Typowe zastosowania:

W systemach finansowych nawet minimalny błąd może oznaczać realną stratę pieniędzy.

Jeżeli platforma księgowa wykonuje miliard operacji dziennie, błąd rzędu 1e-10 przy każdej transakcji przestaje być abstrakcją.

W obliczeniach naukowych problem jest jeszcze bardziej zdradliwy. Symulacja może wyglądać poprawnie przez wiele godzin, a później wynik zaczyna dryfować. Czasem źródłem jest właśnie akumulacja błędów.

Kahan jest wolniejszy od zwykłego sumowania, ponieważ wykonuje więcej operacji:

W praktyce różnica wydajności często jest akceptowalna wobec poprawy dokładności.

Niektóre biblioteki numeryczne implementują własne warianty:

Pairwise summation jest popularne przy obliczeniach równoległych.

Typowe błędy popełniane podczas implementacji algorytmów numerycznych wykorzystujących sumowanie zmiennoprzecinkowe

Bardzo częsty błąd to porównywanie liczb zmiennoprzecinkowych operatorem ==.

Przykład:

Lepsze rozwiązanie:

Inny problem to mieszanie typów.

W wielu projektach użycie float jest zbyt agresywną optymalizacją pamięci.

Często spotykany błąd:

Kolejna pułapka pojawia się przy kompilatorach.

Niektóre optymalizacje mogą zmieniać kolejność operacji arytmetycznych. W GCC flagi typu:

potrafią osłabić korzyści wynikające z metod kompensacji.

W GPU problem jest jeszcze bardziej złożony. Równoległe redukcje często generują różne wyniki między uruchomieniami.

Zależność między stabilnością numeryczną, dokładnością obliczeń i kosztami wydajnościowymi programu

Stabilność numeryczna to zdolność algorytmu do ograniczania błędów zaokrągleń.

Algorytm może być:

To nie zawsze zależy od samego języka programowania. Znacznie ważniejszy jest sposób wykonywania operacji.

Dla dużych obliczeń numerycznych wybór algorytmu ma ogromne znaczenie.

Przykład:

| Metoda | Dokładność | Szybkość |
|—|—|
| zwykłe sumowanie | niska | bardzo szybkie |
| Kahan | wysoka | wolniejsze |
| arytmetyka wielkiej precyzji | bardzo wysoka | bardzo wolna |

W praktyce trzeba szukać kompromisu.

W systemach czasu rzeczywistego czasem wybiera się szybszy wariant mimo większego błędu. W obliczeniach naukowych zwykle dokładność ma wyższy priorytet.

Istotne jest też testowanie.

Dobre testy numeryczne powinny zawierać:

W wielu zespołach brak takich testów powoduje, że problemy wychodzą dopiero na produkcji.

FAQ

Czy Algorytm Kahana eliminuje błędy zmiennoprzecinkowe całkowicie?

Nie. Zmniejsza ich wpływ przez kompensację utraconych bitów mantysy. Nadal obowiązują ograniczenia IEEE 754.

Czy metoda Kahana zawsze daje identyczny wynik?

Nie zawsze. Wynik nadal może zależeć od kolejności danych i architektury sprzętowej, ale zwykle jest znacznie dokładniejszy niż przy klasycznym sumowaniu.

Dlaczego Python również ma problem z precyzją?

Python korzysta głównie z typu double zgodnego z IEEE 754. Problem wynika z reprezentacji binarnej, a nie z samego języka.

Czy warto stosować Kahana w małych programach?

Jeżeli liczba operacji jest niewielka, zwykle nie ma takiej potrzeby. Sens pojawia się przy dużych zbiorach danych lub wysokich wymaganiach dokładności.

Czy istnieją szybsze alternatywy?

Tak. Pairwise summation bywa szybsze przy równoległości. Są też bardziej zaawansowane algorytmy kompensacyjne.

Dlaczego błędy pojawiają się częściej przy dużych liczbach?

Ponieważ małe wartości tracą część mantysy podczas wyrównywania wykładników.

Czy typ double zawsze wystarcza?

Nie. W części zastosowań naukowych używa się arytmetyki wielkiej precyzji albo specjalnych bibliotek numerycznych.

Czy procesor wpływa na wyniki obliczeń?

Tak. Różne architektury mogą wykonywać operacje w innej kolejności albo używać innych rozszerzeń FPU.

Źródło Foto: Freepik