PHP
AtCoder
PHP7
YYPHPDay 9

PHPはときどき掛け算ができない

発覚の経緯

プログラミングコンテストサイト「AtCoder」の「C - AtCoDeerくんと選挙速報」でどうしても正答ができなかった。
それほど難しいロジックはないはずなのに……
そして、計算途中に変な値になっていることが発見された。

出現条件

Windows版のPHP7.0〜7.1117231566641875000 * 7 を計算する。
PHP7.1の最新版では間違った結果が表示されます。
PHP7.2.0以降では正しい結果(820620966493125000)が表示されます。

どういう不具合か

117231566641875000 ✕ 7 = 820620966493125120
大きな数字ですが、下4桁に注目してください。
5000に7を掛けて答えは35000なので、掛け算の結果も下4桁は5000のはず。
なのに、5120という中途半端な数字(計算結果が正しくない)

c:\php-7.1.25-Win32-VC14-x64>php -r "$a = 117231566641875000 * 7; echo $a . PHP_EOL; printf(\"%d\", $a);"
8.2062096649313E+17
820620966493125120

PHPのマニュアルには、整数の範囲を超えたら浮動小数点数になる、という記述はあるけれど、今回はその範囲の最大(2の63乗-1、約9✕10の18乗)より小さいにもかかわらず、浮動小数点数になって、誤差が発生している。

# ↓今回の計算結果
820620966493125120
9223372036854775807
# ↑PHP(64bit版)で扱える整数の最大値

回避方法

単純な掛け算で答えが間違ってしまうので、掛け算を自作するしかない。
(「BCMath 任意精度数学関数」を使えれば回避できますが、AtCoderは非対応)

function omulti($a, $b) {
    $aa = str_split(strval($a));
    $bb = str_split(strval($b));
    foreach ($aa as $ka => $va) {
        foreach ($bb as $kb => $vb) {
            $res[$ka + $kb + 1] += intval($va) * intval($vb);
        }
    }
    for ($i = max(array_keys($res)); $i > 0; $i--) {
        if ($res[$i] > 9) {
            $res[$i - 1] += floor($res[$i] / 10);
            $res[$i] %= 10;
        }

    }
    ksort($res);
    return implode("", $res);
}

数字を文字列に変換して分割し、1桁ずつ計算して桁上りを処理して文字列としてガッチャンコしております。
正整数同士の掛け算にしか対応しておりません。

intdivの発見

ちなみに上記で不正解になっていたテストケースの5番は正答できたのですが、テストケース9番で今度は除算の結果が間違っていて、不正解になりました。
ここでまたオリジナル除算を作ったのですが、PHP7には intdiv なる関数があることを発見しました。
他の言語ではそもそもあったりしますが、除算における商(除算の結果の整数部分)を取得できる関数です。(他の言語では a // b みたいな表記を良く見かけます)
これを基に除算して切り上げる関数を作りました。(オリジナル除算よりも圧倒的にコードが短くて済む)

function divceil($dividend, $divisor) {
    return intdiv($dividend, $divisor) + ($dividend % $divisor !== 0);
}

総括

まぁ、10の14乗を超えるような数を扱う機会は通常あまりなく、しかもWindows版の一部のバージョンでしか起こらない不具合なので、実際問題として誰も困らないのかもしれませんね。今回は intdiv を知ることができたのが収穫でした。

後付け

本稿はYYPHP Advent Calendar 2018 - Qiitaの9日目の記事です(空いていたので忍び込みました)。