Satu pembulatan floating-point berukuran sekitar 10⁻¹⁶ — kecil sekali, dan Chapter sebelumnya menunjukkan toleransi relatif menanganinya dengan rapi. Masalah baru muncul ketika pembulatan itu diulang ratusan ribu kali: galat yang dianggap aman pada satu operasi bisa menumpuk menjadi galat besar pada hasil akhir, dan pola penjumlahan paling umum — menambahkan banyak nilai kecil ke satu akumulator besar — adalah tanah subur kejadian yang disebut loss of significance. Angka kecil ditambahkan ke akumulator, hasilnya dibulatkan kembali ke grid nilai yang bisa disimpan, dan berlian kecil itu ternyata tidak pernah masuk hitungan. Chapter ini membedah mekanisme penumpukan itu, lalu memperkenalkan Kahan summation, algoritma sederhana yang menagih kembali sisa pembulatan di setiap langkah — dengan bukti angka yang bisa Anda jalankan sendiri.

Mekanisme Penumpukan Galat #

Bayangkan akumulator total sedang menyimpan 1e16 — di titik ini jarak antar nilai double yang masih bisa dibedakan (ulp) sudah 2, jadi total + 1.0 dibulatkan kembali ke 1e16 dan angka 1 itu hilang pergi tanpa jejak. Ulangi seribu kali, dan seribu unit masukan menguap dari hasil akhir. Ini bukan kasus jauh yang direkayasa: menjumlahkan harga-harga satuan dalam rupiah ke total miliaran, atau mengakumulasi selisih mikrodetik dalam benchmark panjang, keduanya berjalan di rezim yang sama. Dua pola kehilangan yang paling sering ditemui:

  1. Akumulasi pembulatan berulang — setiap total += x membulatkan sekali; setelah N operasi, galat bisa tumbuh proporsional dengan N.
  2. Kehilangan signifikansi — menambah nilai yang jauh lebih kecil dari akumulator (rasio lebih dari 2⁵³ pada double) membuat nilai kecil itu tidak terwakili sama sekali dalam hasil.

Naif vs Kahan: Bukti Angka #

Program berikut membandingkan penjumlahan naif, penjumlahan setelah pengurutan, dan Kahan summation pada dua kasus:

cpp 
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <limits>
#include <vector>

// Penjumlahan naif: setiap langkah menyimpan hasil yang dibulatkan.
double jumlahNaif(const std::vector<double>& data) {
    double total = 0.0;
    for (double x : data) {
        total += x;
    }
    return total;
}

// Kahan summation: membawa sisa pembulatan setiap langkah ke langkah
// berikutnya lewat variabel kompensasi c.
double jumlahKahan(const std::vector<double>& data) {
    double total = 0.0;
    double c = 0.0;              // sisa pembulatan yang ditagih nanti
    for (double x : data) {
        double y = x - c;        // bayar tagihan dari langkah sebelumnya
        double t = total + y;    // di sini pembulatan bisa terjadi
        c = (t - total) - y;     // catat bagian yang hilang pada t
        total = t;
    }
    return total;
}

int main() {
    std::cout << std::setprecision(std::numeric_limits<double>::max_digits10);

    // Kasus 1: 0.1 dijumlahkan sepuluh kali
    std::vector<double> kecil(10, 0.1);
    std::cout << "naif  : " << jumlahNaif(kecil) << "\n";
    std::cout << "kahan : " << jumlahKahan(kecil) << "\n";

    // Kasus 2: satu nilai jauh lebih besar dari sisanya
    std::vector<double> besar{1e16, 1.0, 1.0, 1.0};
    std::cout << "naif  : " << jumlahNaif(besar) << "\n";

    // Ringkas: mengurutkan menaik menolong penjumlahan satu arah
    std::vector<double> urut = besar;
    std::sort(urut.begin(), urut.end());
    std::cout << "urut  : " << jumlahNaif(urut) << "\n";

    std::cout << "kahan : " << jumlahKahan(besar) << "\n";

    return 0;
}

Output yang Dihasilkan:

text 
naif  : 0.99999999999999989
kahan : 1
naif  : 10000000000000000
urut  : 10000000000000004
kahan : 10000000000000004

Bedah baris-per-baris:

  1. Baris 8-14 (double jumlahNaif(const std::vector<double>& data)): penjumlahan biasa yang kita tulis tanpa pikir panjang. Setiap total += x membulatkan hasil ke nilai double terdekat, dan pembulatan itulah sumber seluruh galat dalam chapter ini.
  2. Baris 18-20 (double jumlahKahan(...) ... double c = 0.0;): Kahan menambah satu variabel c — kompensasi — yang menyimpan pembulatan yang baru saja hilang, siap ditagihkan pada langkah berikutnya.
  3. Baris 22 (double y = x - c;): nilai masukan dikoreksi dulu dengan tagihan langkah sebelumnya. Bila langkah lalu kehilangan sebagian kecil dari x, bagian itu masuk kembali lewat sini.
  4. Baris 23-24 (double t = total + y; ... c = (t - total) - y;): baris 24 adalah jantung algoritmanya. Secara aljabar (t - total) harusnya sama dengan y, sehingga selisih keduanya adalah pembulatan yang baru terjadi saat menghitung t — ditangkap tanpa perlu tahu bagaimana CPU membulatkan.
  5. Baris 34-36 (std::vector<double> kecil(10, 0.1); ...): sepuluh kali 0,1 seharusnya 1. Hasil naif 0.99999999999999989 menyisakan galat kecil khas pembulatan biner; Kahan mengembalikan tepat 1.
  6. Baris 39-40 (std::vector<double> besar{1e16, 1.0, 1.0, 1.0};): jumlah eksak kasus ini adalah 10000000000000003, tetapi ulp pada 1e16 adalah 2, sehingga dua nilai double terdekatnya adalah …002 dan …004. Hasil naif …000 kehilangan seluruh tiga unit; keduanya urut dan kahan mendarat di …004 — nilai yang tepat sama dengan hasil pembulatan matematika untuk jumlah eksak tersebut.
  7. Baris 42-45 (std::sort(urut.begin(), urut.end());): trik ringkas untuk penjumlahan satu arah — menjumlahkan nilai kecil lebih dulu (menaik) agar akumulator membesar belakangan. Elegan, tetapi butuh salinan data dan biaya sort O(n log n), dan tidak menolong semua kasus seperti dijelaskan di bawah.

Batas Trik Pengurutan dan Pilihan yang Utama #

Mengurutkan menaik menolong ketika semua masukan bertanda sama, tetapi bukan obat universal. Untuk deret campuran tanda dengan suku besar yang saling meniadakan — misalnya 1e20 + 3.14 + (-1e20) — hasil tetap 0 pada urutan menaik maupun menurun yang kita uji, karena suku besar justru harus dijumlahkan berpasangan lebih dulu agar peniadaannya bersih. Algoritma kompensasi seperti Kahan (dan keluarganya: pairwise summation yang dipakai pustaka numerik, atau Neumaier yang lebih tahan banting) adalah alat yang benar untuk kasus umum. Prinsip yang bisa dibawa pulang: urutan operasi mengubah hasil floating-point; jadi ketika hasil deret panjang tampak “geser sedikit”, cek dulu urutan dan algoritma penjumlahannya sebelum menyalahkan data.

Mengetahui bahwa setiap tipe floating-point punya batas presisi yang bisa diukur, sekarang saatnya membongkar peralatan resminya: <limits> menyimpan epsilon, angka terbesar dan terkecil, infinity, hingga aturan pencetakan round-trip — semua objek yang kita sentuh seadanya di dua chapter terakhir. Chapter numeric_limits berikutnya memetanya satu per satu.

Rujukan resmi untuk topik Chapter ini: std::accumulate dan fungsi matematika <cmath> di cppreference.