{"id":1585,"date":"2026-04-16T14:06:46","date_gmt":"2026-04-16T12:06:46","guid":{"rendered":"https:\/\/trzykody.pl\/?p=1585"},"modified":"2026-05-19T14:10:13","modified_gmt":"2026-05-19T12:10:13","slug":"algorytm-kahana-problemy-arytmetyki-zmiennoprzecinkowej-przy-sumowaniu-milionow-wartosci-w-pamieci-operacyjnej","status":"publish","type":"post","link":"https:\/\/trzykody.pl\/index.php\/2026\/04\/16\/algorytm-kahana-problemy-arytmetyki-zmiennoprzecinkowej-przy-sumowaniu-milionow-wartosci-w-pamieci-operacyjnej\/","title":{"rendered":"Algorytm Kahana: Problemy arytmetyki zmiennoprzecinkowej przy sumowaniu milion\u00f3w warto\u015bci w pami\u0119ci operacyjnej"},"content":{"rendered":"\n

W wi\u0119kszo\u015bci j\u0119zyk\u00f3w programowania liczby typu float<\/code> i double<\/code> nie s\u0105 przechowywane dok\u0142adnie. Komputer zapisuje je binarnie, w sko\u0144czonej liczbie bit\u00f3w. To oznacza, \u017ce cz\u0119\u015b\u0107 liczb dziesi\u0119tnych nie ma dok\u0142adnej reprezentacji w pami\u0119ci. Typowy przyk\u0142ad to 0.1<\/code>, kt\u00f3re w IEEE 754 staje si\u0119 przybli\u017ceniem. Przy pojedynczych operacjach b\u0142\u0105d zwykle jest ma\u0142y, ale przy d\u0142ugich sumowaniach zaczyna si\u0119 kumulowa\u0107.<\/p>\n\n\n\n

W praktyce problem pojawia si\u0119 szybciej ni\u017c wiele os\u00f3b zak\u0142ada. Sumowanie milion\u00f3w pr\u00f3bek z czujnik\u00f3w, danych gie\u0142dowych albo wynik\u00f3w oblicze\u0144 numerycznych potrafi da\u0107 wynik r\u00f3\u017cni\u0105cy si\u0119 od oczekiwanego o kilka, kilkana\u015bcie albo nawet setki jednostek najmniejszej dok\u0142adno\u015bci. W\u0142a\u015bnie w takich sytuacjach stosowany jest Algorytm Kahana.<\/p>\n\n\n\n

Algorytm Kahana i mechanizm kompensacji b\u0142\u0119du utraconego podczas dodawania liczb zmiennoprzecinkowych<\/h2>\n\n\n\n

Klasyczne sumowanie wygl\u0105da bardzo prosto:<\/p>\n\n\n\n

Operacja<\/th>Opis<\/th><\/tr><\/thead>
suma = suma + x<\/code><\/td>Dodanie kolejnego elementu do akumulatora<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Problem polega na tym, \u017ce podczas dodawania liczby bardzo ma\u0142ej do bardzo du\u017cej cz\u0119\u015b\u0107 bit\u00f3w jest tracona. Procesor musi wyr\u00f3wna\u0107 wyk\u0142adniki liczb. Mniejsze warto\u015bci trac\u0105 wtedy fragment precyzji.<\/p>\n\n\n\n

Przyk\u0142ad:<\/p>\n\n\n\n

Liczba<\/th>Warto\u015b\u0107<\/th><\/tr><\/thead>
Du\u017ca liczba<\/td>10000000000000000.0<\/code><\/td><\/tr>
Ma\u0142a liczba<\/td>1.0<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

W arytmetyce IEEE 754 dla double<\/code> dodanie 1.0<\/code> do tak du\u017cej liczby mo\u017ce nie zmieni\u0107 wyniku. Jednostka zostanie \u201ezgubiona\u201d.<\/p>\n\n\n\n

Klasyczny algorytm:<\/p>\n\n\n\n

Krok<\/th>Kod<\/th><\/tr><\/thead>
1<\/td>sum += value<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

nie pami\u0119ta utraconego b\u0142\u0119du.<\/p>\n\n\n\n

Kahan zauwa\u017cy\u0142, \u017ce mo\u017cna przechowywa\u0107 t\u0119 utracon\u0105 cz\u0119\u015b\u0107 osobno i pr\u00f3bowa\u0107 odzyska\u0107 j\u0105 przy kolejnych operacjach.<\/p>\n\n\n\n

Mechanizm dzia\u0142a przez dodatkow\u0105 zmienn\u0105 kompensacji.<\/p>\n\n\n\n

Podstawowa idea:<\/p>\n\n\n\n

Zmienna<\/th>Znaczenie<\/th><\/tr><\/thead>
sum<\/code><\/td>aktualna suma<\/td><\/tr>
c<\/code><\/td>utracony b\u0142\u0105d zaokr\u0105glenia<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Przy ka\u017cdym dodaniu wykonywana jest korekta:<\/p>\n\n\n\n

Etap<\/th>Dzia\u0142anie<\/th><\/tr><\/thead>
1<\/td>odj\u0119cie poprzedniego b\u0142\u0119du<\/td><\/tr>
2<\/td>dodanie liczby<\/td><\/tr>
3<\/td>obliczenie nowego b\u0142\u0119du<\/td><\/tr>
4<\/td>zapis kompensacji<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Formalnie:<\/p>\n\n\n\n

Wz\u00f3r<\/th>Znaczenie<\/th><\/tr><\/thead>
y = x - c<\/code><\/td>korekta wej\u015bcia<\/td><\/tr>
t = sum + y<\/code><\/td>nowe dodanie<\/td><\/tr>
c = (t - sum) - y<\/code><\/td>odzysk b\u0142\u0119du<\/td><\/tr>
sum = t<\/code><\/td>aktualizacja wyniku<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Ta jedna dodatkowa zmienna cz\u0119sto radykalnie zmniejsza b\u0142\u0105d numeryczny.<\/p>\n\n\n\n

Dlaczego kolejno\u015b\u0107 dodawania danych wej\u015bciowych zmienia ko\u0144cowy wynik oblicze\u0144 numerycznych<\/h2>\n\n\n\n

W matematyce:<\/p>\n\n\n\n

(<\/mo>a<\/mi>+<\/mo>b<\/mi>)<\/mo>+<\/mo>c<\/mi>=<\/mo>a<\/mi>+<\/mo>(<\/mo>b<\/mi>+<\/mo>c<\/mi>)<\/mo><\/mrow>(a+b)+c=a+(b+c)<\/annotation><\/semantics><\/math>(a+b)+c=a+(b+c)<\/p>\n\n\n\n

W komputerze dla liczb zmiennoprzecinkowych to nie zawsze dzia\u0142a.<\/p>\n\n\n\n

Przyk\u0142ad:<\/p>\n\n\n\n

Kolejno\u015b\u0107<\/th>Wynik<\/th><\/tr><\/thead>
(1e16 + 1) - 1e16<\/code><\/td>0<\/code><\/td><\/tr>
(1e16 - 1e16) + 1<\/code><\/td>1<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Matematycznie oba wyra\u017cenia s\u0105 r\u00f3wne 1<\/code>.<\/p>\n\n\n\n

W praktyce pierwszy wariant traci ma\u0142\u0105 warto\u015b\u0107 podczas dodawania do du\u017cej liczby.<\/p>\n\n\n\n

To bardzo wa\u017cne w:<\/p>\n\n\n\n

Zastosowanie<\/th>Problem<\/th><\/tr><\/thead>
Symulacje fizyczne<\/td>dryf energii<\/td><\/tr>
Finanse<\/td>b\u0142\u0119dne sumy transakcji<\/td><\/tr>
ML i AI<\/td>niestabilno\u015b\u0107 gradient\u00f3w<\/td><\/tr>
Analiza sygna\u0142\u00f3w<\/td>utrata ma\u0142ych amplitud<\/td><\/tr>
Statystyka<\/td>b\u0142\u0119dne wariancje<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

W wielu bibliotekach numerycznych kolejno\u015b\u0107 danych jest kontrolowana w\u0142a\u015bnie z powodu b\u0142\u0119d\u00f3w zaokr\u0105gle\u0144.<\/p>\n\n\n\n

Dodatkowy problem pojawia si\u0119 przy r\u00f3wnoleg\u0142o\u015bci. Procesory wielordzeniowe sumuj\u0105 fragmenty danych niezale\u017cnie, a p\u00f3\u017aniej \u0142\u0105cz\u0105 wyniki. R\u00f3\u017cna kolejno\u015b\u0107 operacji daje czasem r\u00f3\u017cne rezultaty mi\u0119dzy uruchomieniami programu. To cz\u0119sty problem przy debugowaniu oblicze\u0144 naukowych.<\/p>\n\n\n\n

Implementacja Algorytm Kahana w j\u0119zyku C, C++ oraz Python wraz z analiz\u0105 dok\u0142adno\u015bci oblicze\u0144<\/h2>\n\n\n\n

Najprostsza implementacja w C:<\/p>\n\n\n\n

Element<\/th>Kod<\/th><\/tr><\/thead>
Implementacja C<\/td>c\\n#include <stdio.h>\\n\\nint main() {\\n double values[] = {1e16, 1.0, -1e16};\\n double sum = 0.0;\\n double c = 0.0;\\n\\n for(int i = 0; i < 3; i++) {\\n double y = values[i] - c;\\n double t = sum + y;\\n c = (t - sum) - y;\\n sum = t;\\n }\\n\\n printf(\\\"%.1f\\\\n\\\", sum);\\n return 0;\\n}\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Wynik:<\/p>\n\n\n\n

Metoda<\/th>Wynik<\/th><\/tr><\/thead>
Zwyk\u0142e sumowanie<\/td>0.0<\/code><\/td><\/tr>
Kahan<\/td>1.0<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Implementacja C++:<\/p>\n\n\n\n

Element<\/th>Kod<\/th><\/tr><\/thead>
Implementacja C++<\/td>cpp\\n#include <iostream>\\n#include <vector>\\n\\nint main() {\\n std::vector<double> data = {1e16, 1.0, -1e16};\\n\\n double sum = 0.0;\\n double c = 0.0;\\n\\n for(double x : data) {\\n double y = x - c;\\n double t = sum + y;\\n c = (t - sum) - y;\\n sum = t;\\n }\\n\\n std::cout << sum << std::endl;\\n return 0;\\n}\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Implementacja Python:<\/p>\n\n\n\n

Element<\/th>Kod<\/th><\/tr><\/thead>
Implementacja Python<\/td>python\\nvalues = [1e16, 1.0, -1e16]\\n\\nsum_value = 0.0\\nc = 0.0\\n\\nfor x in values:\\n y = x - c\\n t = sum_value + y\\n c = (t - sum_value) - y\\n sum_value = t\\n\\nprint(sum_value)\\n<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

W Pythonie problem nadal istnieje, mimo \u017ce float<\/code> jest oparty o double<\/code>.<\/p>\n\n\n\n

Warto zwr\u00f3ci\u0107 uwag\u0119, \u017ce Kahan nie eliminuje b\u0142\u0119du ca\u0142kowicie. On jedynie minimalizuje utrat\u0119 informacji.<\/p>\n\n\n\n

Przy bardzo ekstremalnych danych nadal mog\u0105 wyst\u0105pi\u0107 odchylenia.<\/p>\n\n\n\n

Analiza b\u0142\u0119d\u00f3w zaokr\u0105gle\u0144 w standardzie IEEE 754 i wp\u0142yw ograniczonej precyzji na wyniki oblicze\u0144<\/h2>\n\n\n\n

Standard IEEE 754 definiuje spos\u00f3b przechowywania liczb zmiennoprzecinkowych.<\/p>\n\n\n\n

Typ double<\/code>:<\/p>\n\n\n\n

Sk\u0142adnik<\/th>Liczba bit\u00f3w<\/th><\/tr><\/thead>
Znak<\/td>1<\/td><\/tr>
Wyk\u0142adnik<\/td>11<\/td><\/tr>
Mantysa<\/td>52<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Realna precyzja to oko\u0142o 15\u201317 cyfr dziesi\u0119tnych.<\/p>\n\n\n\n

Je\u017celi liczby znacz\u0105co r\u00f3\u017cni\u0105 si\u0119 skal\u0105:<\/p>\n\n\n\n

Operacja<\/th>Problem<\/th><\/tr><\/thead>
1e16 + 1<\/code><\/td>utrata ma\u0142ej warto\u015bci<\/td><\/tr>
0.1 + 0.2<\/code><\/td>wynik nie jest dok\u0142adnie 0.3<\/code><\/td><\/tr>
d\u0142ugie sumowanie<\/td>akumulacja b\u0142\u0119du<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Klasyczny przyk\u0142ad:<\/p>\n\n\n\n

Kod<\/th>Wynik<\/th><\/tr><\/thead>
python\\nprint(0.1 + 0.2)\\n<\/code><\/td>0.30000000000000004<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

To nie jest b\u0142\u0105d Pythona. Tak dzia\u0142a reprezentacja binarna.<\/p>\n\n\n\n

Liczba 0.1<\/code> w systemie binarnym rozwija si\u0119 niesko\u0144czenie:<\/p>\n\n\n\n

0.1<\/mn>10<\/mn><\/msub>=<\/mo>0.0001100110011<\/mn>\u2026<\/mo>2<\/mn><\/msub><\/mrow>0.1_{10}=0.0001100110011\\ldots_2<\/annotation><\/semantics><\/math>0.110\u200b=0.0001100110011\u20262\u200b<\/p>\n\n\n\n

Procesor musi j\u0105 obci\u0105\u0107.<\/p>\n\n\n\n

W praktyce znaczenie ma r\u00f3wnie\u017c:<\/p>\n\n\n\n

Poj\u0119cie<\/th>Znaczenie<\/th><\/tr><\/thead>
epsilon maszynowy<\/td>najmniejsza rozr\u00f3\u017cnialna zmiana<\/td><\/tr>
overflow<\/td>przekroczenie zakresu<\/td><\/tr>
underflow<\/td>utrata bardzo ma\u0142ych warto\u015bci<\/td><\/tr>
cancellation<\/td>odejmowanie podobnych liczb<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Cancellation jest szczeg\u00f3lnie niebezpieczne. Gdy odejmujemy liczby prawie r\u00f3wne, znacz\u0105ce cyfry si\u0119 kasuj\u0105.<\/p>\n\n\n\n

Przyk\u0142ad:<\/p>\n\n\n\n

Operacja<\/th>Wynik<\/th><\/tr><\/thead>
123456.789123 - 123456.789122<\/code><\/td>bardzo ma\u0142a r\u00f3\u017cnica po utracie precyzji<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

W obliczeniach naukowych takie zjawisko mo\u017ce ca\u0142kowicie zniszczy\u0107 stabilno\u015b\u0107 algorytmu.<\/p>\n\n\n\n

Gdzie stosuje si\u0119 Algorytm Kahana i dlaczego bywa wa\u017cniejszy ni\u017c sama wydajno\u015b\u0107 programu<\/h2>\n\n\n\n

W wielu projektach programista d\u0142ugo nie zauwa\u017ca problemu. Program dzia\u0142a poprawnie na ma\u0142ych danych testowych. Problemy zaczynaj\u0105 si\u0119 przy du\u017cej skali.<\/p>\n\n\n\n

Typowe zastosowania:<\/p>\n\n\n\n

Obszar<\/th>Przyk\u0142ad<\/th><\/tr><\/thead>
Finanse<\/td>sumowanie milion\u00f3w operacji<\/td><\/tr>
Grafika 3D<\/td>akumulacja transformacji<\/td><\/tr>
Symulacje CFD<\/td>obliczenia p\u00f3l numerycznych<\/td><\/tr>
Machine Learning<\/td>sumowanie gradient\u00f3w<\/td><\/tr>
Statystyka<\/td>\u015brednie i wariancje<\/td><\/tr>
Telekomunikacja<\/td>analiza sygna\u0142\u00f3w<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

W systemach finansowych nawet minimalny b\u0142\u0105d mo\u017ce oznacza\u0107 realn\u0105 strat\u0119 pieni\u0119dzy.<\/p>\n\n\n\n

Je\u017celi platforma ksi\u0119gowa wykonuje miliard operacji dziennie, b\u0142\u0105d rz\u0119du 1e-10<\/code> przy ka\u017cdej transakcji przestaje by\u0107 abstrakcj\u0105.<\/p>\n\n\n\n

W obliczeniach naukowych problem jest jeszcze bardziej zdradliwy. Symulacja mo\u017ce wygl\u0105da\u0107 poprawnie przez wiele godzin, a p\u00f3\u017aniej wynik zaczyna dryfowa\u0107. Czasem \u017ar\u00f3d\u0142em jest w\u0142a\u015bnie akumulacja b\u0142\u0119d\u00f3w.<\/p>\n\n\n\n

Kahan jest wolniejszy od zwyk\u0142ego sumowania, poniewa\u017c wykonuje wi\u0119cej operacji:<\/p>\n\n\n\n

Metoda<\/th>Liczba dzia\u0142a\u0144<\/th><\/tr><\/thead>
klasyczne dodawanie<\/td>1 dodanie<\/td><\/tr>
Kahan<\/td>kilka dodawa\u0144 i odejmowa\u0144<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

W praktyce r\u00f3\u017cnica wydajno\u015bci cz\u0119sto jest akceptowalna wobec poprawy dok\u0142adno\u015bci.<\/p>\n\n\n\n

Niekt\u00f3re biblioteki numeryczne implementuj\u0105 w\u0142asne warianty:<\/p>\n\n\n\n

Wariant<\/th>Charakterystyka<\/th><\/tr><\/thead>
Kahan<\/td>podstawowa kompensacja<\/td><\/tr>
Neumaier<\/td>lepsze dzia\u0142anie dla du\u017cych r\u00f3\u017cnic<\/td><\/tr>
pairwise summation<\/td>sumowanie drzewiaste<\/td><\/tr>
compensated summation<\/td>szersza grupa metod<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Pairwise summation jest popularne przy obliczeniach r\u00f3wnoleg\u0142ych.<\/p>\n\n\n\n

Typowe b\u0142\u0119dy pope\u0142niane podczas implementacji algorytm\u00f3w numerycznych wykorzystuj\u0105cych sumowanie zmiennoprzecinkowe<\/h2>\n\n\n\n

Bardzo cz\u0119sty b\u0142\u0105d to por\u00f3wnywanie liczb zmiennoprzecinkowych operatorem ==<\/code>.<\/p>\n\n\n\n

Przyk\u0142ad:<\/p>\n\n\n\n

Kod<\/th>Problem<\/th><\/tr><\/thead>
python\\nif x == 0.3:\\n<\/code><\/td>mo\u017ce nigdy nie by\u0107 prawd\u0105<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Lepsze rozwi\u0105zanie:<\/p>\n\n\n\n

Kod<\/th>Dzia\u0142anie<\/th><\/tr><\/thead>
python\\nabs(x - 0.3) < 1e-9\\n<\/code><\/td>por\u00f3wnanie z tolerancj\u0105<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Inny problem to mieszanie typ\u00f3w.<\/p>\n\n\n\n

Typ<\/th>Zakres precyzji<\/th><\/tr><\/thead>
float<\/code><\/td>oko\u0142o 7 cyfr<\/td><\/tr>
double<\/code><\/td>oko\u0142o 15 cyfr<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

W wielu projektach u\u017cycie float<\/code> jest zbyt agresywn\u0105 optymalizacj\u0105 pami\u0119ci.<\/p>\n\n\n\n

Cz\u0119sto spotykany b\u0142\u0105d:<\/p>\n\n\n\n

Sytuacja<\/th>Konsekwencja<\/th><\/tr><\/thead>
sumowanie od najmniejszej do najwi\u0119kszej<\/td>mniejszy b\u0142\u0105d<\/td><\/tr>
sumowanie losowe<\/td>wi\u0119kszy b\u0142\u0105d<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Kolejna pu\u0142apka pojawia si\u0119 przy kompilatorach.<\/p>\n\n\n\n

Niekt\u00f3re optymalizacje mog\u0105 zmienia\u0107 kolejno\u015b\u0107 operacji arytmetycznych. W GCC flagi typu:<\/p>\n\n\n\n

Flaga<\/th>Efekt<\/th><\/tr><\/thead>
-ffast-math<\/code><\/td>szybsze, mniej dok\u0142adne obliczenia<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

potrafi\u0105 os\u0142abi\u0107 korzy\u015bci wynikaj\u0105ce z metod kompensacji.<\/p>\n\n\n\n

W GPU problem jest jeszcze bardziej z\u0142o\u017cony. R\u00f3wnoleg\u0142e redukcje cz\u0119sto generuj\u0105 r\u00f3\u017cne wyniki mi\u0119dzy uruchomieniami.<\/p>\n\n\n\n

Zale\u017cno\u015b\u0107 mi\u0119dzy stabilno\u015bci\u0105 numeryczn\u0105, dok\u0142adno\u015bci\u0105 oblicze\u0144 i kosztami wydajno\u015bciowymi programu<\/h2>\n\n\n\n

Stabilno\u015b\u0107 numeryczna to zdolno\u015b\u0107 algorytmu do ograniczania b\u0142\u0119d\u00f3w zaokr\u0105gle\u0144.<\/p>\n\n\n\n

Algorytm mo\u017ce by\u0107:<\/p>\n\n\n\n

Typ<\/th>Charakterystyka<\/th><\/tr><\/thead>
stabilny<\/td>b\u0142\u0119dy rosn\u0105 powoli<\/td><\/tr>
niestabilny<\/td>b\u0142\u0119dy gwa\u0142townie si\u0119 kumuluj\u0105<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

To nie zawsze zale\u017cy od samego j\u0119zyka programowania. Znacznie wa\u017cniejszy jest spos\u00f3b wykonywania operacji.<\/p>\n\n\n\n

Dla du\u017cych oblicze\u0144 numerycznych wyb\u00f3r algorytmu ma ogromne znaczenie.<\/p>\n\n\n\n

Przyk\u0142ad:<\/p>\n\n\n\n

| Metoda | Dok\u0142adno\u015b\u0107 | Szybko\u015b\u0107 |
|—|—|
| zwyk\u0142e sumowanie | niska | bardzo szybkie |
| Kahan | wysoka | wolniejsze |
| arytmetyka wielkiej precyzji | bardzo wysoka | bardzo wolna |<\/p>\n\n\n\n

W praktyce trzeba szuka\u0107 kompromisu.<\/p>\n\n\n\n

W systemach czasu rzeczywistego czasem wybiera si\u0119 szybszy wariant mimo wi\u0119kszego b\u0142\u0119du. W obliczeniach naukowych zwykle dok\u0142adno\u015b\u0107 ma wy\u017cszy priorytet.<\/p>\n\n\n\n

Istotne jest te\u017c testowanie.<\/p>\n\n\n\n

Dobre testy numeryczne powinny zawiera\u0107:<\/p>\n\n\n\n

Element<\/th>Pow\u00f3d<\/th><\/tr><\/thead>
bardzo du\u017ce liczby<\/td>sprawdzanie overflow<\/td><\/tr>
bardzo ma\u0142e liczby<\/td>underflow<\/td><\/tr>
liczby o r\u00f3\u017cnych skalach<\/td>cancellation<\/td><\/tr>
d\u0142ugie sekwencje<\/td>akumulacja b\u0142\u0119d\u00f3w<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

W wielu zespo\u0142ach brak takich test\u00f3w powoduje, \u017ce problemy wychodz\u0105 dopiero na produkcji.<\/p>\n\n\n\n

FAQ<\/h2>\n\n\n\n

Czy Algorytm Kahana eliminuje b\u0142\u0119dy zmiennoprzecinkowe ca\u0142kowicie?<\/h3>\n\n\n\n

Nie. Zmniejsza ich wp\u0142yw przez kompensacj\u0119 utraconych bit\u00f3w mantysy. Nadal obowi\u0105zuj\u0105 ograniczenia IEEE 754.<\/p>\n\n\n\n

Czy metoda Kahana zawsze daje identyczny wynik?<\/h3>\n\n\n\n

Nie zawsze. Wynik nadal mo\u017ce zale\u017ce\u0107 od kolejno\u015bci danych i architektury sprz\u0119towej, ale zwykle jest znacznie dok\u0142adniejszy ni\u017c przy klasycznym sumowaniu.<\/p>\n\n\n\n

Dlaczego Python r\u00f3wnie\u017c ma problem z precyzj\u0105?<\/h3>\n\n\n\n

Python korzysta g\u0142\u00f3wnie z typu double<\/code> zgodnego z IEEE 754. Problem wynika z reprezentacji binarnej, a nie z samego j\u0119zyka.<\/p>\n\n\n\n

Czy warto stosowa\u0107 Kahana w ma\u0142ych programach?<\/h3>\n\n\n\n

Je\u017celi liczba operacji jest niewielka, zwykle nie ma takiej potrzeby. Sens pojawia si\u0119 przy du\u017cych zbiorach danych lub wysokich wymaganiach dok\u0142adno\u015bci.<\/p>\n\n\n\n

Czy istniej\u0105 szybsze alternatywy?<\/h3>\n\n\n\n

Tak. Pairwise summation bywa szybsze przy r\u00f3wnoleg\u0142o\u015bci. S\u0105 te\u017c bardziej zaawansowane algorytmy kompensacyjne.<\/p>\n\n\n\n

Dlaczego b\u0142\u0119dy pojawiaj\u0105 si\u0119 cz\u0119\u015bciej przy du\u017cych liczbach?<\/h3>\n\n\n\n

Poniewa\u017c ma\u0142e warto\u015bci trac\u0105 cz\u0119\u015b\u0107 mantysy podczas wyr\u00f3wnywania wyk\u0142adnik\u00f3w.<\/p>\n\n\n\n

Czy typ double<\/code> zawsze wystarcza?<\/h3>\n\n\n\n

Nie. W cz\u0119\u015bci zastosowa\u0144 naukowych u\u017cywa si\u0119 arytmetyki wielkiej precyzji albo specjalnych bibliotek numerycznych.<\/p>\n\n\n\n

Czy procesor wp\u0142ywa na wyniki oblicze\u0144?<\/h3>\n\n\n\n

Tak. R\u00f3\u017cne architektury mog\u0105 wykonywa\u0107 operacje w innej kolejno\u015bci albo u\u017cywa\u0107 innych rozszerze\u0144 FPU.<\/p>\n\n\n\n

\u0179r\u00f3d\u0142o Foto: Freepik<\/em><\/p>\n\n\n\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

W wi\u0119kszo\u015bci j\u0119zyk\u00f3w programowania liczby typu float i double nie s\u0105 przechowywane dok\u0142adnie. Komputer zapisuje je binarnie, w sko\u0144czonej liczbie bit\u00f3w. To oznacza, \u017ce cz\u0119\u015b\u0107 liczb dziesi\u0119tnych nie ma dok\u0142adnej reprezentacji w pami\u0119ci. Typowy przyk\u0142ad to 0.1, kt\u00f3re w IEEE 754 staje si\u0119 przybli\u017ceniem. Przy pojedynczych operacjach b\u0142\u0105d zwykle jest ma\u0142y, ale przy d\u0142ugich sumowaniach zaczyna si\u0119 kumulowa\u0107. W praktyce problem pojawia si\u0119 szybciej ni\u017c wiele os\u00f3b zak\u0142ada. Sumowanie milion\u00f3w pr\u00f3bek z czujnik\u00f3w, danych gie\u0142dowych albo wynik\u00f3w oblicze\u0144 numerycznych potrafi da\u0107 wynik r\u00f3\u017cni\u0105cy si\u0119 od oczekiwanego o kilka, kilkana\u015bcie albo nawet setki jednostek najmniejszej dok\u0142adno\u015bci. W\u0142a\u015bnie w takich sytuacjach stosowany jest Algorytm Kahana. Algorytm Kahana i mechanizm kompensacji b\u0142\u0119du utraconego podczas dodawania liczb zmiennoprzecinkowych Klasyczne sumowanie wygl\u0105da bardzo prosto: Operacja Opis suma = suma + x Dodanie kolejnego elementu do akumulatora Problem polega na tym, \u017ce podczas dodawania liczby bardzo ma\u0142ej do bardzo du\u017cej cz\u0119\u015b\u0107 bit\u00f3w jest tracona. Procesor musi wyr\u00f3wna\u0107 wyk\u0142adniki liczb. Mniejsze warto\u015bci trac\u0105 wtedy fragment precyzji. Przyk\u0142ad: Liczba Warto\u015b\u0107 Du\u017ca liczba 10000000000000000.0 Ma\u0142a liczba 1.0 W arytmetyce IEEE 754 dla double dodanie 1.0 do tak du\u017cej liczby mo\u017ce nie zmieni\u0107 wyniku. Jednostka zostanie \u201ezgubiona\u201d. Klasyczny algorytm: Krok Kod 1 sum += value nie pami\u0119ta utraconego b\u0142\u0119du. Kahan zauwa\u017cy\u0142, \u017ce mo\u017cna przechowywa\u0107 t\u0119 utracon\u0105 cz\u0119\u015b\u0107 osobno i pr\u00f3bowa\u0107 odzyska\u0107 j\u0105 przy kolejnych operacjach. Mechanizm dzia\u0142a przez dodatkow\u0105 zmienn\u0105 kompensacji. Podstawowa idea: Zmienna Znaczenie sum aktualna suma c utracony b\u0142\u0105d zaokr\u0105glenia Przy ka\u017cdym dodaniu wykonywana jest korekta: Etap Dzia\u0142anie 1 odj\u0119cie poprzedniego b\u0142\u0119du 2 dodanie liczby 3 obliczenie nowego b\u0142\u0119du 4 zapis kompensacji Formalnie: Wz\u00f3r Znaczenie y = x – c korekta wej\u015bcia t = sum + y nowe dodanie c = (t – sum) – y odzysk b\u0142\u0119du sum = t aktualizacja wyniku Ta jedna dodatkowa zmienna cz\u0119sto radykalnie zmniejsza b\u0142\u0105d numeryczny. Dlaczego kolejno\u015b\u0107 dodawania danych wej\u015bciowych zmienia ko\u0144cowy wynik oblicze\u0144 numerycznych W matematyce: (a+b)+c=a+(b+c)(a+b)+c=a+(b+c)(a+b)+c=a+(b+c) W komputerze dla liczb zmiennoprzecinkowych to nie zawsze dzia\u0142a. Przyk\u0142ad: Kolejno\u015b\u0107 Wynik (1e16 + 1) – 1e16 0 (1e16 – 1e16) + 1 1 Matematycznie oba wyra\u017cenia s\u0105 r\u00f3wne 1. W praktyce pierwszy wariant traci ma\u0142\u0105 warto\u015b\u0107 podczas dodawania do du\u017cej liczby. To bardzo wa\u017cne w: Zastosowanie Problem Symulacje fizyczne dryf energii Finanse b\u0142\u0119dne sumy transakcji ML i AI niestabilno\u015b\u0107 gradient\u00f3w Analiza sygna\u0142\u00f3w utrata ma\u0142ych amplitud Statystyka b\u0142\u0119dne wariancje W wielu bibliotekach numerycznych kolejno\u015b\u0107 danych jest kontrolowana w\u0142a\u015bnie z powodu b\u0142\u0119d\u00f3w zaokr\u0105gle\u0144. Dodatkowy problem pojawia si\u0119 przy r\u00f3wnoleg\u0142o\u015bci. Procesory wielordzeniowe sumuj\u0105 fragmenty danych niezale\u017cnie, a p\u00f3\u017aniej \u0142\u0105cz\u0105 wyniki. R\u00f3\u017cna kolejno\u015b\u0107 operacji daje czasem r\u00f3\u017cne rezultaty mi\u0119dzy uruchomieniami programu. To cz\u0119sty problem przy debugowaniu oblicze\u0144 naukowych. Implementacja Algorytm Kahana w j\u0119zyku C, C++ oraz Python wraz z analiz\u0105 dok\u0142adno\u015bci oblicze\u0144 Najprostsza implementacja w C: Element Kod Implementacja C c\\n#include <stdio.h>\\n\\nint main() {\\n double values[] = {1e16, 1.0, -1e16};\\n double sum = 0.0;\\n double c = 0.0;\\n\\n for(int i = 0; i < 3; i++) {\\n double y = values[i] – c;\\n double t = sum + y;\\n c = (t – sum) – y;\\n sum = t;\\n }\\n\\n printf(\\”%.1f\\\\n\\”, sum);\\n return 0;\\n}\\n Wynik: Metoda Wynik Zwyk\u0142e sumowanie 0.0 Kahan 1.0 Implementacja C++: Element Kod Implementacja C++ cpp\\n#include <iostream>\\n#include <vector>\\n\\nint main() {\\n std::vector<double> data = {1e16, 1.0, -1e16};\\n\\n double sum = 0.0;\\n double c = 0.0;\\n\\n for(double x : data) {\\n double y = x – c;\\n double t = sum + y;\\n c = (t – sum) – y;\\n sum = t;\\n }\\n\\n std::cout << sum << std::endl;\\n return 0;\\n}\\n Implementacja Python: Element Kod Implementacja Python python\\nvalues = [1e16, 1.0, -1e16]\\n\\nsum_value = 0.0\\nc = 0.0\\n\\nfor x in values:\\n y = x – c\\n t = sum_value + y\\n c = (t – sum_value) – y\\n sum_value = t\\n\\nprint(sum_value)\\n W Pythonie problem nadal istnieje, mimo \u017ce float jest oparty o double. Warto zwr\u00f3ci\u0107 uwag\u0119, \u017ce Kahan nie eliminuje b\u0142\u0119du ca\u0142kowicie. On jedynie minimalizuje utrat\u0119 informacji. Przy bardzo ekstremalnych danych nadal mog\u0105 wyst\u0105pi\u0107 odchylenia. Analiza b\u0142\u0119d\u00f3w zaokr\u0105gle\u0144 w standardzie IEEE 754 i wp\u0142yw ograniczonej precyzji na wyniki oblicze\u0144 Standard IEEE 754 definiuje spos\u00f3b przechowywania liczb zmiennoprzecinkowych. Typ double: Sk\u0142adnik Liczba bit\u00f3w Znak 1 Wyk\u0142adnik 11 Mantysa 52 Realna precyzja to oko\u0142o 15\u201317 cyfr dziesi\u0119tnych. Je\u017celi liczby znacz\u0105co r\u00f3\u017cni\u0105 si\u0119 skal\u0105: Operacja Problem 1e16 + 1 utrata ma\u0142ej warto\u015bci 0.1 + 0.2 wynik nie jest dok\u0142adnie 0.3 d\u0142ugie sumowanie akumulacja b\u0142\u0119du Klasyczny przyk\u0142ad: Kod Wynik python\\nprint(0.1 + 0.2)\\n 0.30000000000000004 To nie jest b\u0142\u0105d Pythona. Tak dzia\u0142a reprezentacja binarna. Liczba 0.1 w systemie binarnym rozwija si\u0119 niesko\u0144czenie: 0.110=0.0001100110011\u202620.1_{10}=0.0001100110011\\ldots_20.110\u200b=0.0001100110011\u20262\u200b Procesor musi j\u0105 obci\u0105\u0107. W praktyce znaczenie ma r\u00f3wnie\u017c: Poj\u0119cie Znaczenie epsilon maszynowy najmniejsza rozr\u00f3\u017cnialna zmiana overflow przekroczenie zakresu underflow utrata bardzo ma\u0142ych warto\u015bci cancellation odejmowanie podobnych liczb Cancellation jest szczeg\u00f3lnie niebezpieczne. Gdy odejmujemy liczby prawie r\u00f3wne, znacz\u0105ce cyfry si\u0119 kasuj\u0105. Przyk\u0142ad: Operacja Wynik 123456.789123 – 123456.789122 bardzo ma\u0142a r\u00f3\u017cnica po utracie precyzji W obliczeniach naukowych takie zjawisko mo\u017ce ca\u0142kowicie zniszczy\u0107 stabilno\u015b\u0107 algorytmu. Gdzie stosuje si\u0119 Algorytm Kahana i dlaczego bywa wa\u017cniejszy ni\u017c sama wydajno\u015b\u0107 programu W wielu projektach programista d\u0142ugo nie zauwa\u017ca problemu. Program dzia\u0142a poprawnie na ma\u0142ych danych testowych. Problemy zaczynaj\u0105 si\u0119 przy du\u017cej skali. Typowe zastosowania: Obszar Przyk\u0142ad Finanse sumowanie milion\u00f3w operacji Grafika 3D akumulacja transformacji Symulacje CFD obliczenia p\u00f3l numerycznych Machine Learning sumowanie gradient\u00f3w Statystyka \u015brednie i wariancje Telekomunikacja analiza sygna\u0142\u00f3w W systemach finansowych nawet minimalny b\u0142\u0105d mo\u017ce oznacza\u0107 realn\u0105 strat\u0119 pieni\u0119dzy. Je\u017celi platforma ksi\u0119gowa wykonuje miliard operacji dziennie, b\u0142\u0105d rz\u0119du 1e-10 przy ka\u017cdej transakcji przestaje by\u0107 abstrakcj\u0105. W obliczeniach naukowych problem jest jeszcze bardziej zdradliwy. Symulacja mo\u017ce wygl\u0105da\u0107 poprawnie przez wiele godzin, a p\u00f3\u017aniej wynik zaczyna dryfowa\u0107. Czasem \u017ar\u00f3d\u0142em jest w\u0142a\u015bnie akumulacja b\u0142\u0119d\u00f3w. Kahan jest wolniejszy od zwyk\u0142ego sumowania, poniewa\u017c wykonuje wi\u0119cej operacji: Metoda Liczba dzia\u0142a\u0144 klasyczne dodawanie 1 dodanie Kahan kilka dodawa\u0144 i odejmowa\u0144 W praktyce r\u00f3\u017cnica wydajno\u015bci cz\u0119sto jest akceptowalna wobec poprawy dok\u0142adno\u015bci. Niekt\u00f3re biblioteki numeryczne implementuj\u0105 w\u0142asne warianty: Wariant Charakterystyka Kahan podstawowa kompensacja Neumaier lepsze dzia\u0142anie dla du\u017cych r\u00f3\u017cnic pairwise summation sumowanie drzewiaste compensated summation szersza grupa metod Pairwise summation jest popularne przy obliczeniach r\u00f3wnoleg\u0142ych. Typowe b\u0142\u0119dy pope\u0142niane podczas implementacji algorytm\u00f3w numerycznych wykorzystuj\u0105cych sumowanie zmiennoprzecinkowe Bardzo cz\u0119sty b\u0142\u0105d to por\u00f3wnywanie liczb zmiennoprzecinkowych operatorem ==. Przyk\u0142ad: Kod Problem python\\nif x == 0.3:\\n mo\u017ce nigdy nie by\u0107 prawd\u0105 Lepsze rozwi\u0105zanie: Kod Dzia\u0142anie python\\nabs(x – 0.3) < 1e-9\\n por\u00f3wnanie z tolerancj\u0105 Inny problem to mieszanie typ\u00f3w. Typ Zakres precyzji float oko\u0142o 7 cyfr double oko\u0142o 15 cyfr W wielu projektach u\u017cycie float jest zbyt agresywn\u0105 optymalizacj\u0105 pami\u0119ci. Cz\u0119sto spotykany b\u0142\u0105d: Sytuacja Konsekwencja sumowanie od najmniejszej do najwi\u0119kszej mniejszy b\u0142\u0105d sumowanie losowe wi\u0119kszy b\u0142\u0105d Kolejna pu\u0142apka pojawia si\u0119 przy kompilatorach. Niekt\u00f3re optymalizacje mog\u0105 zmienia\u0107 kolejno\u015b\u0107 operacji arytmetycznych. W GCC flagi typu: Flaga Efekt -ffast-math szybsze, mniej dok\u0142adne obliczenia potrafi\u0105 os\u0142abi\u0107 korzy\u015bci wynikaj\u0105ce z metod kompensacji. W GPU problem jest jeszcze bardziej z\u0142o\u017cony. R\u00f3wnoleg\u0142e redukcje cz\u0119sto generuj\u0105 r\u00f3\u017cne wyniki mi\u0119dzy uruchomieniami. Zale\u017cno\u015b\u0107 mi\u0119dzy stabilno\u015bci\u0105 numeryczn\u0105, dok\u0142adno\u015bci\u0105 oblicze\u0144 i kosztami wydajno\u015bciowymi programu Stabilno\u015b\u0107 numeryczna to zdolno\u015b\u0107 algorytmu do ograniczania b\u0142\u0119d\u00f3w zaokr\u0105gle\u0144. Algorytm mo\u017ce by\u0107: Typ Charakterystyka stabilny b\u0142\u0119dy rosn\u0105 powoli niestabilny b\u0142\u0119dy gwa\u0142townie si\u0119 kumuluj\u0105 To nie zawsze zale\u017cy od samego j\u0119zyka programowania. Znacznie wa\u017cniejszy jest spos\u00f3b wykonywania operacji. Dla du\u017cych oblicze\u0144 numerycznych wyb\u00f3r algorytmu ma ogromne znaczenie. Przyk\u0142ad: | Metoda | Dok\u0142adno\u015b\u0107 | Szybko\u015b\u0107 ||—|—|| zwyk\u0142e sumowanie | niska | bardzo szybkie || Kahan | wysoka | wolniejsze || arytmetyka wielkiej precyzji | bardzo wysoka | bardzo wolna | W praktyce trzeba szuka\u0107 kompromisu. W systemach czasu rzeczywistego czasem wybiera si\u0119 szybszy wariant mimo wi\u0119kszego b\u0142\u0119du. W obliczeniach naukowych zwykle dok\u0142adno\u015b\u0107 ma wy\u017cszy priorytet. Istotne jest te\u017c testowanie. Dobre testy numeryczne powinny zawiera\u0107: Element Pow\u00f3d bardzo du\u017ce liczby sprawdzanie overflow bardzo ma\u0142e liczby underflow liczby o r\u00f3\u017cnych skalach cancellation d\u0142ugie sekwencje akumulacja b\u0142\u0119d\u00f3w W wielu zespo\u0142ach brak takich test\u00f3w powoduje, \u017ce problemy wychodz\u0105 dopiero na produkcji. FAQ Czy Algorytm Kahana eliminuje b\u0142\u0119dy zmiennoprzecinkowe ca\u0142kowicie? Nie. Zmniejsza ich wp\u0142yw przez kompensacj\u0119 utraconych bit\u00f3w mantysy. Nadal obowi\u0105zuj\u0105 ograniczenia IEEE 754. Czy metoda Kahana zawsze daje identyczny wynik? Nie zawsze. Wynik nadal mo\u017ce zale\u017ce\u0107 od kolejno\u015bci danych i architektury sprz\u0119towej, ale zwykle jest znacznie dok\u0142adniejszy ni\u017c przy klasycznym sumowaniu. Dlaczego Python r\u00f3wnie\u017c ma problem z precyzj\u0105? Python korzysta g\u0142\u00f3wnie z typu double zgodnego z IEEE 754. Problem wynika z reprezentacji binarnej, a nie z samego j\u0119zyka. Czy warto stosowa\u0107 Kahana w ma\u0142ych programach? Je\u017celi liczba operacji jest niewielka, zwykle nie ma takiej potrzeby. Sens pojawia si\u0119 przy du\u017cych zbiorach danych lub wysokich wymaganiach dok\u0142adno\u015bci. Czy istniej\u0105 szybsze alternatywy? Tak. Pairwise summation bywa szybsze przy r\u00f3wnoleg\u0142o\u015bci. S\u0105 te\u017c bardziej zaawansowane algorytmy kompensacyjne. Dlaczego b\u0142\u0119dy pojawiaj\u0105 si\u0119 cz\u0119\u015bciej przy du\u017cych liczbach? Poniewa\u017c ma\u0142e warto\u015bci trac\u0105 cz\u0119\u015b\u0107 mantysy podczas wyr\u00f3wnywania wyk\u0142adnik\u00f3w. Czy typ double zawsze wystarcza? Nie. W cz\u0119\u015bci zastosowa\u0144 naukowych u\u017cywa si\u0119 arytmetyki wielkiej precyzji albo specjalnych bibliotek numerycznych. Czy procesor wp\u0142ywa na wyniki oblicze\u0144? Tak. R\u00f3\u017cne architektury mog\u0105 wykonywa\u0107 operacje w innej kolejno\u015bci albo u\u017cywa\u0107 innych rozszerze\u0144 FPU. \u0179r\u00f3d\u0142o Foto: Freepik<\/p>\n","protected":false},"author":1,"featured_media":1586,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24],"tags":[],"class_list":["post-1585","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-kodowanie"],"_links":{"self":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1585","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/comments?post=1585"}],"version-history":[{"count":1,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1585\/revisions"}],"predecessor-version":[{"id":1587,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1585\/revisions\/1587"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/media\/1586"}],"wp:attachment":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/media?parent=1585"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/categories?post=1585"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/tags?post=1585"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}