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.

## Algoritmoa 
  **function** KahanSum(input)
     **var** sum = 0.0
     **var** c = 0.0                  // batuketan galtzen diren digituak gordetzeko (negatiboan).
     **for** i = 1 **to** input.length **do**
         **var** y = input[i] - c       // Aurreko eragiketetan galdutako digituak hurrengo batugaiari gehitzen dizkio eragiketa honek (negatiboan daudenez, kendu!).
         **var** t = sum + y            // sum zenbaki handia bada eta y txikia, y-ko digitu asko gal daitezke.
         c = (t - sum) - y          //*(t - sum)* balioan agertuko dira y-ren hainbat digitu, baturan eragina izan dutenak hain zuzen ere, eta horri y kenduz, galdutako digituak lortuko ditugu negatiboan**
         sum = t                  // Algebraikoki, c beti 0 izan beharko litzateke.
     **next** i                       // Hurrengoan, galdutako digituak y-ri gehituko zaizkio.
     **return** sum

## 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:'*

 234001.0 + 1.427569 = 234002.427569 ≈ 234002.4                 *Jada, 4ren ondorengo digitu guztiak galdu egin dira*
 234002.4 + 3.139473 = 234005.539473 ≈ 234005.5                 *Emaitza ez da zehatz zehatza, galdu ditugun digituengatik.*
     

* **Kahanen batuketa konpentsatuarekin:**

 sum = 234001.0                    
 c = 0.0                            
 **y** = 1.427569 – 0 = 1.427569 
 **t** = 234001.0 + 1.427569 = 
   = 234002.427569                 *Baina 7 digitu besterik ezin dira erabili!* Beraz, biribildu beharra daukagu.
   = 234002.4
 **c** = (234002.4 – 234001.0) – 1.427569 
   = 1.400000 – 1.427569 
   = -0.027569                     *Batuketa honetan galdutako digituak, hurrengo batuketan erabiltzeko gordeko direnak*
 **sum** = 234002.4

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.

 **y** = 3.139473 - (-0.027569) * Aurreko atalean galdutako digituak sartzen dira. y-ren antzeko tamainakoa denez, digitu  
   = 3.167042                    gehienak kontuan hartzen dira.*
 **t** = 234002.4 + 3.167042
   = 234005.567042
   = 234005.6            *Baina berriro ere, batuketan gutxi batzuk kontuan hartzen dira, emaitza 7 digituetara biribilduz.*
 **c** = (234005.6 – 234002.4) – 3.167042
   = 3.200000 – 3.167042   *Hala ere, aurreko eragiketan galdutako digituak sartu dira, kasu honetan, gehiegi, c positiboa
   = 0.032958                baita. Beraz, hurrengo batuketa egongo balitz, kendu beharko lirateke.*
 **sum** = 234005.6     *Horrela, biribiltze zuzena lortzen dugu.*

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 point*erako: ɛ = (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|\le\left[2\varepsilon + O(n\varepsilon^2)\right]\sum_{i=1}^n |x_i|.

Datu horiekin, emaitzaren **errore erlatiboa** horrela bornatu dezakegu:

:\frac\le\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}\le\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≥1016 izan beharko luke). Ondorioz, baldintzapenaren zenbakiaz gain, errorea soilik \varepsilon-en arabera geratzen da, n-ren independentea izatea lortuz.

## Kanpo estekak