# Kahanen batuketa-algoritmo

Kahanen batuketa-algoritmoa (edo batuketa konpentsatua) doitasun finituko koma higikorreko zenbakien baturan gertatzen diren zenbakizko erroreak gutxitzeko algoritmoa da, William Kahanek sortutakoa.
Doitasun finituko koma higikorreko zenbakiekin lan egiten dugunean, zenbakia adierazteko erabil dezakegun digitu kopurua mugatua da, ondorioz ezin dira zenbaki guztiak adierazi eta biribiltze eta trunkatze erroreak sortzen dira. Zenbaki askoren arteko batura egin nahi denean eta, bereziki, zenbaki handiei zenbaki txikiak gehitu nahi dizkiegunean, zenbaki txikiaren azken digituek ez dute eraginik izango baturan, galdu egingo dira. Galdutako digituek eta prezisioak, batukari askorekin, emaitzaren errorea handiegia izatera bultza dezakete eta, ondorioz, kalkulu zientifiko zehatzak beharrezkoak diren kasuetan, arazo izan daiteke.
Algoritmo honi esker, batuketa bakoitzean galdutako digituak gorde egiten dira bigarren aldagai batean, eta bildutako errore hori ondorengo batuketan eransten saiatzen da algoritmoa. Era honetan, galera txikien baturak esanguratsua izan daitekeen digitu batean eragin dezake egindako erroreak murriztuz.

## Adibidea

Batuketaren hasierako balioa 234001.0 dela suposatuz, eta horri 1.427569 eta 3.139473 gehitu nahi badiogu hurrenez hurren, Kahanen batuketa-algoritmoarekin eta hau gabe lortzen ditugun emaitzak aztertuko ditugu, zenbakia 7 digitura mugatuz.
Batuketa hauen emaitza zehatza honakoa da: 234005.567042 ⇒ 7 digituetara mugatuz: 234005.6
* Batuketa arruntarekin:
* Kahanen batuketa konpentsatuarekin:
Baina batuketan bakarrik 7 digitu gelditu dira, besteak galduz. Beraz, c-n galdutako digitu horiek gordetzen dira, benetan gehitu diren digituen eta gehitu behar zirenen arteko kenketa eginez.
Beraz, ikus daitekeen bezala, batuketa bi metatzailerekin gauzatzen da: sum, batuketa gordetzen duena, eta c, galdutako digituak gordetzen dituena.

## Zehaztasuna

Orokorrean, horrelako eragiketen ebazpenak inplizituki hainbat errore ditu:
    1. Makina epsilona deiturikoa, konputagailuek erabilitako doitasunaren araberakoa dena: ɛ = (1/2)(b$^{-d+1}$), non:
      * b = erabilitako oinarria (adibidez b=2 bitarrean, b=10 hamartarrean, etab.)
      * d = zenbakiak adierazteko erabiliko ditzakegun digitu kopurua
       Adibidez, IEEE standard double precision floating pointerako: ɛ = (1/2)(2$^{-52+1}$) ≈ 10$^{−16}$ .
    2. Problemaren baldintzapena, adierazten duena problemaren emaitza zer nolako sentikortasuna duen sarrerako datuekiko, hau da, sarrerako datuen aldaketak edo erroreak zer nolako eragina duen emaitzan. Gaizki baldintzatutako problema batekin, sarrerako datuen aldaketa minimo batek, emaitzaren aldaketa oso esanguratsu bat suposatu dezake, problema horren emaitzen fidagarritasuna behera eginez. Problema honetarako:
             $C_{n}={\frac {\sum \limits _{i=1}^{n}|x_{i}|}{\left|\sum \limits _{i=1}^{n}x_{i}\right|}}$
Algoritmo honek emaitzan duen eragin nagusia, lortutako errorearen ordena gutxitzea da: oinarrizko batuketa batekin lortutako errorea batugai kopuruaren arabera hazten den bitartean ($O(n\varepsilon )$ ordenarekin, kasu okerrenean), Kahanen algoritmoarekin errorea batugai kopuruaren independentea izatea lortzen da, soilik makina epsilon-en balioaren araberako erroreak lortuz, hau da, erabiltzen den zenbakien adierazpenak duen inplizituzko errorearen arabera: $O(\varepsilon )$.

### Errorearen analisia

Izan bedi batukari baten emaitza erreala:
       $S_{n}=\sum _{i=1}^{n}x_{i}$,
Batuketa konpentsatuarekin lortutako ematiza $S_{n}+E_{n}$ izango da, non errorea horrela bornatu dezakegu:
       $|E_{n}|\leq \left[2\varepsilon +O(n\varepsilon ^{2})\right]\sum _{i=1}^{n}|x_{i}|$.
Datu horiekin, emaitzaren errore erlatiboa horrela bornatu dezakegu:
    ${\frac {|E_{n}|}{|S_{n}|}}\leq \left[2\varepsilon +O(n\varepsilon ^{2})\right]{\frac {\sum \limits _{i=1}^{n}|x_{i}|}{\left|\sum \limits _{i=1}^{n}x_{i}\right|}}$ $\Rightarrow$ $E_{er}\leq \left[2\varepsilon +O(n\varepsilon ^{2})\right]C_{n}$

### Errorearen interpretazioa

Nahiz eta errorearen adierazpidean $O(n\varepsilon ^{2})$ motako ordena bat izan, horrek suposatutako errorea ≈ 0 da: Makina epsilona zenbakia ɛ izanik, zenbakiak doitasun horren arabera biribilduko dira. Hortaz, nɛ$^2$ zenbakia 0-ra biribilduko da, n≥(1/ɛ) ez bada, orokorrean praktikan gertatzen ez den kasua izanez (adibidez double floating point doitasunarekin, n≥10$^{16}$ izan beharko luke). Ondorioz, baldintzapenaren zenbakiaz gain, errorea soilik $\varepsilon$-en arabera geratzen da, $n$-ren independentea izatea lortuz.

## Kanpo estekak

* Datuak: Q2982293