Za našich čias sme nemali žiadne Džavy, ani céčka: všetko sme programovali ručne, s nulami a jednotkami. Práve tak Herón z Alexandrie, o desať rokov mladší než Ježiš, nemal žiadne kalkulačky. Všetko počítal ručne.

Dokonca aj odmocniny.

Dokonca si na to vymyslel algoritmus.

Herón z Alexandrie a jeho algoritmus

Zistil, že keď má hľadať odmocninu čísla N, znamená to nájsť číslo n také, kde n², teda n · n = N. Lebo napríklad pre odmocninu 9, čo je 3, platí, že 3 · 3 = 9.

V prvom kroku sa plesol po bruchu a odhadol, že odmocnina z 9 je 1. Fakt blbý odhad, ale niekde začať mohol.

Potom sa spýtal sám seba, či jeho odhad o je dostatočne blízko skutočnej odmocnine, alebo inými slovami, či po umocnení odhadu sa trafí do pôvodného čísla:

Je o² blízko k N?

U nás máme o² = 1² = 1, čo nie je veľmi blízko k 9. Čo teraz?

Vylepšenie odhadu

Herón usúdil, že môže ľahko vylepšiť svoj odhad: môže zobrať priemer medzi terajším odhadom a medzi skutočnou hodnotou odmocniny n.

Terajší odhad je známy: je to o. Skutočná hodnota odmocniny, teda n, známa nie je (veď práve tú hľadáme!). Vieme ju však odvodiť!

Ak vieme, že n² = n · n = N, predelením rovnice číslom n zistíme, že, že n = N / n.

Priemer dvoch čísiel je klasický: sčítame ich a vydelíme dvoma. Ak hľadáme priemer odhadu a skutočnej hodnoty odmocniny, máme: novýOdhad = (o + n) / 2, čiže novýOdhad = (o + (N/n)) / 2.

Stále však závisíme na hodnote n, ktorú nepoznáme! Vieme však:

1. o < n (náš odhad bude stále horší než hľadaná odmocnina). Prevráťme obe strany a zároveň otočme znak nerovnosti:
2. 1/o > 1/n. Vynásobme obe strany N:
3. N/o > N/n. Vzájomne vymeňme obe strany:
4. N/n < N/o.

Z toho uvidíme, že

(o + (N/n)) / 2 < (o + (N/o)) / 2

a teda sme dokázali, že nový odhad je väčší než predošlý, čiže bližšie k skutočnej hodnote n.

To isté platí aj pre prípad, že odhad nadstrelíme: napríklad, keď odhadneme odmocninu 9 na 100.

1. o > n (náš odhad bude väčší než hľadaná odmocnina). Prevráťme obe strany a zároveň otočme znak nerovnosti:
2. 1/o < 1/n. Vynásobme obe strany N:
3. N/o < N/n. Vzájomne vymeňme obe strany:
4. N/n > N/o.

Z toho uvidíme, že

(o + (N/n)) / 2 > (o + (N/o)) / 2

a teda sme sa opäť priblížili k skutočnej hodnote n.

Tým sme zistili, že ak odhad nadstrelíme, nový odhad bude podstrelený, a naopak: ak odhad zvolíme príliš nízky, nový odhad príliš veľký; v oboch prípadoch sa však priblížime k skutočnej hodnote.

Na našom príklade: nový odhad je (1 + 9/1) / 2 = 5.

Opakujme algoritmus

Toto odhadovanie môžeme teraz opakovať dovtedy, kým neusúdime, že nový odhad je dostatočne blízko skutočnej odmocnine:

• prvý nový odhad je (1 + 9/1) / 2 = 5. Ten je nadstrelený, ale neprekáža to.
• druhý nový odhad je (5 + 9/5) / 2 = 3,4. Tento je ešte stále nadstrelený.
• tretí nový odhad je (3,4 + 9/3,4) / 2 = 3,023. Aj tento je nadstrelený.
• štvrtý nový odhad je (3,023 + 9/3,023) / 2 = 3,000087495865035

Stačili štyri iterácie a máme celkom presný výsledok!

Ako zistíme, že odhad je dostatočne blízko? Stačí umocniť aktuálny odhad, odčítať od skutočnej hodnoty a zistiť, či sú hodnoty blízko k sebe (cez absolútnu hodnotu):

3,000087495865035^2 – 9 = 9,000524982845735 – 9 = 0.000524982845735

To vyzerá byť dosť blízko, nie?

Implementácia

Máme všetko, môžeme implementovať v Haskelli:

priemer x y = (x + y) / 2

jeDostatocneBlizko odhad x = abs (odhad^2 - x) < 0.00001

vylepsi odhad x = priemer odhad (x / odhad)

odhadniOdmocninu odhad x
    | jeDostatocneBlizko odhad x = odhad
    | otherwise = odhadniOdmocninu (vylepsi odhad x) x

odmocnina x = odhadniOdmocninu 1.0 x

A to je všetko, rátame odmocniny ostošesť!

Literatúra

• Clojure Dojo: Method of Heron. Implementácia v Clojure.
• Abelsson, Sussman: Structure and Interpretation of Computer Programs, section 1.1.7.