Mellékleteink: HUP | Gamekapocs
Keres

Szükségtelen pontosságvesztésre vadászik a Herbie

Hlács Ferenc, 2016. január 26. 11:30

Már a math.js könyvtárban is talált javításra szoruló hibákat a washingtoni egyetem új fejlesztése, a Herbie. Az új megoldás a felhasznált matematikai függvényeket és például a műveletek sorrendjét is vizsgálja.

hirdetés

A lebegőpontos számítások okozta pontatlan eredményekkel sok fejlesztőnek meggyűlik a baja: a kerekített értékek, majd az azok alapján számolt, ismét lekerekített eredmények lavinája egy idő után, nem elhanyagolható hibákhoz vezethet. Ezek a hibák a digitális számítástechnika velejárói, amelyeket eltüntetni nem, minimalizálni viszont lehet. Ezt tűzte ki célul a Washingtoni Egyetem csapata, Herbie nevű eszközével, amely már most meglepően hatékonynak bizonyult.

Automatizált szakember

A problémára egyébként többféle megoldás is létezik: a "legbutább" megközelítés, ha a fejlesztő egyenként áll neki javítgatni a kerekítésekből adódó, fontosabbnak vélt hibákat. Ez meglehetősen fáradságos munka, ráadásul - különösen a termetesebb programok esetében - nem is a legmegbízhatóbb. Egy másik megoldás, ha a programozó egy tetszőleges pontosságú libraryt (arbitrary precision library), például a GNU MPFR-t (GNU Multiple Precision Floating-Point Reliably) hajtja igába.

A tetszőleges pontosságú számításoknál csak a rendelkezésre álló memória szab határt annak, hogy hány számjegy kerülhet a lebegőpontos értékekbe, így az eljárással kapott eredmények rendkívül pontosak, ez tehát értelemszerűen jóval megbízhatóbb eredményeket ad, mint a gyors, de pontatlan módszer - cserébe viszont amellett, hogy igényel némi szakértelmet, a natív lebegőpontos számításhoz képest iszonyúan lassú, a különbség akár több száz- vagy ezerszeres is lehet, ami a gyakorlatban a legtöbb esetben használhatatlanná teszi.

A fentieken túl meg lehet tanulni kifejezetten a hasonló, lebegőpontos hibák megkeresésére szolgáló numerikus módszereket, ez azonban sok időt és energiabefektetést igényel a fejlesztő részéről, igaz cserébe nem csak megbízható, de gyors is. Ez utóbbi, harmadik opciót hivatott automatizálni a Herbie, amely heurisztikus kereséssel, a fenti módszereket bevetve kalapálja helyére a megcélzott programok lebegőpontos számításait.

A szóban forgó számítások során többféle hiba is előfordulhat, ilyen például a túlcsordulás, mikor az eredmény nem fér el a rendelkezésére álló tárterületen vagy épp a "katasztrofális kioltás" (catastrophic cancellation) esete, azaz az olyan súlyos pontosságromlás, mikor a nem kerekített, nagy számokból kell kis értékeket számítani. Előbbit orvosolhatja, ha például a túlcsordulást okozó műveletet egy eltérő, ugyanakkor azzal azonos értékű kifejezéssel helyettesítjük, utóbbiban pedig az adott egyenlet átrendezése segíthet. Ahhoz, hogy a program által produkált eredmény valóban pontos, vagy legalábbis elég pontos legyen, minden hasonló lehetőséget egyszerre figyelembe kell venni - ahogy azt a numerikus módszerek jó szakértője is tenné - és pontosan ez az, amit a Herbie ígér.

Pontosabb eredmény, három lépésben

A Washingonti Egyetem fejlesztőinek terméke ehhez első körben "alapigazságokat" keres: 64 bitnyi véletlenszerű, az adott szoftver számára elfogadható kiindulási értékből számol  eredményt az ultramagas pontosságú módszerrel - ezekhez kell majd az adott programnak minél közelebbi értéket produkálni, hasonló indulóértékek mellett. Ugyanezeket a számokat az implementációban szereplő lebegőpontos eljáráson is végigfuttatva, a kapott eredményeket összehasonlítva továbbá rögtön látható lesz, mennyire pontos vagy pontatlan alaphelyzetben a vizsgált szoftver.

A következő lépésben a Herbie új, az eredetinél pontosabb formulákat keres az adott műveletekhez. Miután a tetszőleges pontosságú és hagyományos számításokkal kapott eredmények összevetésével lokalizálta a hibákért felelős elemeket, az adott műveleteket másképp felírva (-x helyett például 0-x-et véve) vizsgálja meg, pontosabb lett-e az eredmény. Ehhez a program különböző előre betárazott műveleti adatbázisokat is használhat. De a szoftver az egyes feladatokat nem csak teljesen megegyező jelentésű alternatívákkal váltja le, automatikusan generált, az eredetikkel csupán közel megegyező változatokat is bevet a próbálkozás során - ez is sok pontatlanságot kiirthat. A fenti eljárás tetszőleges alkalommal futtatható le, a segítségével kapott, sok esetben hosszú, bonyolult kifejezéseket a program egyszerűsíti.

Az így kapott programváltozatok kerülnek be az utolsó körbe, ahol a Herbie megvizsgálja, milyen értékek mellett, mely verziók teljesítenek a legjobban, majd ennek megfelelően fésüli össze belőlük a végleges programot. Előfordulhat ugyanis, hogy az élmezőnybe jutott A, B és C variánsok közül, 1-10-ig terjedő bemeneti értékeknél az A kiemelkedően pontos végeredményt ad, viszont más számoknál már pontatlanul teljesít - ugyanígy lehet a B például 10 és 20 között pontos, a C pedig ennél nagyobb értékeknél. Ilyenkor mindhárom metódus maradhat, és a bemeneti értéknek megfelelően a legpontosabb eredményt adó ágon fut végig a feldolgozás.

Lassabb, de biztosabb

Az ilyen módon feltuningolt kód értelemszerű velejárója, hogy testesebb, mint az eredeti verzió, illetve annál valamivel lassabb is - a fejlesztők szerint nagyjából 40 százalékkal komótosabb tempóra kell számítani. Ez ugyanakkor még mindig összehasonlíthatatlanul gyorsabb mint a tetszőleges pontosságú módszerek száz- vagy akár ezerszeres lassulása, a sebességcsökkenésért ráadásul a legtöbb esetben valószínűleg bőségesen kárpótol a jelentősen megnövekedett pontosság.

A Herbie már a gyakorlatban is több alkalommal bizonyított: amellett, hogy sikeresen megoldotta Richard Hamming Numerical Methods for Scientists and Engineers című, numerikus módszerekkel foglalkozó könyvének lebegőpontos feladatait, segített pontosabbá tenni a Washingtoni Egyetemen fejlesztett gépi tanulási algoritmusok kvalitatív eredményeit, sőt, neki köszönhető két, a nyílt forrású math.js matematikai könyvtárhoz kiadott patch is.

Ha a Herbie valakinek felkeltette az érdeklődését, érdemes felkeresni a projekt GitHub oldalát.