Přesná práce s čísly pomocí běžných operátorů

Školení, která pořádám

V Google Code Jamu jsem už podruhé dojel na zaokrouhlovací chybu. K těm dochází nejen při práci s desetinnými čísly, ale i u velkých celých čísel, s kterými PHP pracuje také jako s desetinnými. V PHP jsou dvě knihovny pro práci s přesnými čísly: BC a GMP, s těmi se ale pracuje mnohem krkolomněji. Porovnejte běžný zápis s využitím knihovny BC:

<?php
// běžný zápis
$x += $v * $d / 2 - $p;

// využití BC
$x = bcadd($x, bcsub(bcmul($v, bcdiv($d, '2')), $p));
?>

Vzpomněl jsem si ale na extenzi Operator, která dovoluje změnit chování operátorů u objektů. S jejím využitím se dá kód alespoň částečně zpátky zjednodušit:

<?php
$x = new BcNum($x);
$x += new BcNum($v) * $d / 2 - $p;
?>

Objekty implementující přetěžování operátorů by měly být vždy alespoň na levé straně binárního operátoru (s výjimkou operátoru >, kde je to naopak). Samotná implementace třídy je jednoduchá:

<?php
/** Representation of arbitrary precision number with support for common operators
* @copyright Jakub Vrána, https://php.vrana.cz/
* @uses PHP extension bc
* @uses PECL extension operator
*/
class BcNum {
    private $value;
    
    /** Create arbitrary precision number
    * @param string
    * @uses default scale set by bcscale()
    */
    function __construct($value) {
        $this->value = (string) $value;
    }
    
    function __toString() {
        return $this->value;
    }
    
    function __add($value) { return new BcNum(bcadd($this->value, $value)); }
    function __sub($value) { return new BcNum(bcsub($this->value, $value)); }
    function __mul($value) { return new BcNum(bcmul($this->value, $value)); }
    function __div($value) { return new BcNum(bcdiv($this->value, $value)); }
    function __mod($value) { return new BcNum(bcmod($this->value, $value)); }
    function __is_identical($value) { return $this->value === $value; }
    function __is_not_identical($value) { return $this->value !== $value; }
    function __is_equal($value) { return bccomp($this->value, $value) == 0; }
    function __is_not_equal($value) { return bccomp($this->value, $value) != 0; }
    function __is_smaller($value) { return bccomp($this->value, $value) < 0; }
    function __is_smaller_or_equal($value) { return bccomp($this->value, $value) <= 0; }
    function __is_larger($value) { return bccomp($this->value, $value) > 0; }
    function __is_larger_or_equal($value) { return bccomp($this->value, $value) >= 0; }
    function __assign_add($value) { return new BcNum($this->value = bcadd($this->value, $value)); }
    function __assign_sub($value) { return new BcNum($this->value = bcsub($this->value, $value)); }
    function __assign_mul($value) { return new BcNum($this->value = bcmul($this->value, $value)); }
    function __assign_div($value) { return new BcNum($this->value = bcdiv($this->value, $value)); }
    function __assign_mod($value) { return new BcNum($this->value = bcmod($this->value, $value)); }
    function __pre_inc() { return $this->value = bcadd($this->value, '1'); }
    function __pre_dec() { return $this->value = bcsub($this->value, '1'); }
    function __post_inc() { $return = $this->value; $this->value = bcadd($this->value, '1'); return $return; }
    function __post_dec() { $return = $this->value; $this->value = bcsub($this->value, '1'); return $return; }
}
?>

Chybí jen podpora pro unární mínus.

Jakub Vrána, Řešení problému, 23.5.2011, diskuse: 7 (nové: 0)

Diskuse

xsuchy09:

Podobný problém jsem řešil před několika lety, od té doby na BCmath myslím. Jeho použití je krkolomnější, ale funguje, za což jsem byl v době řešení problému rád :) každopádně je tato "vlastnost" a "funkčnost" PHP nepříjemná a opomenutí je nasnadě, nemluvě o případném neplánovaném "přetečení" číslic, s kterými aplikace pracuje ...

25.5.2011 11:07:18

Martin Hruška:

Hodně se mi líbí statistika Google Code Jam na http://www.go-hero.net/jam/10/languages/6 a to, jak směrem do finále jazyky odpadávaly.

Soutěž je především o algoritmech, paměťové náročnosti a rychlosti. Takže moc nechápu, proč si kazit výsledek nevhodným jazykem.

30.5.2011 13:08:09

Jakub Vrána :

Z vlastní zkušenosti mohu říct, že paměťová náročnost v úlohách příliš podstatná není a rychlost nakonec taky ne. Jde o vyřešení úlohy algoritmem s asymptoticky dobrou složitostí. Ale jestli algoritmus běží 10 sekund nebo 30 je nakonec celkem jedno.

Vhodný je tedy takový jazyk, se kterému se řešiteli dobře pracuje a který má po ruce vhodné datové struktury. Já např. v PHP intenzivně využívám asociativní pole a jejich vlastnost k libovolnému prvku přistoupit v konstantním čase.

30.5.2011 14:17:45

Martin Prokeš:

Mimochodem, jestli tou pokaženou úlohou myslíš "space emergency", tak tam bc funkce nejsou potřeba. Jen brutálně zpomalí výpočet.

Problém je totiž logický a to v řádku

<?php
$saves[] = min($as[$i % $C], bcdiv(bcsub($return, $b), 2));
?>

protože ($return - $b)/2 je platné jen u letu, ve kterém jsou dokončeny boostery, takže tam to "min" nemá smysl a nepěkně se projeví pokud je $b > $return kde to uteče do záporných hodnot. Viz úloha začínající "979006 611707690 1000000 1000"

31.5.2011 01:05:24