おれがコンピュータに筆算を教えてやる - 「100 桁の足し算」編

こちらの記事は free_dev_com Advent Calendar 2019 - Adventar 2 日目の記事です。

環境

$ php -v
PHP 7.3.11 (cli) (built: Oct 22 2019 11:20:10) ( NTS MSVC15 (Visual C++ 2017) x64 )
Copyright (c) 1997-2018 The PHP Group
Zend Engine v3.3.11, Copyright (c) 1998-2018 Zend Technologies

まずは普通に計算させる

試しに 2 つの整数を足す関数を作って 100 桁の足し算を実行してみます．きっとコンピュータだからできて当たり前でしょう．

function add($a, $b)
{
    return $a + $b;
}

var_dump(add(
    2345760293460295683704558703456102394871348756109347501936410934756102913874187344541930193470934875,
    7947618927365019364019257691823461928734634570193248703473987562093471093576293478628949398873429857
));

結果

float(1.0293379220825E+100)

あれ，正確に出てこないうえに float って．．．

果たしてコンピュータには 100 桁の足し算はできないのでしょうか？

でも，人間は小学校のときに習った筆算を使えば，どんなに大きい桁の足し算も計算できたはずですよね？
どうやって計算していたかというと， 1 桁ずつ計算していたはずです．
それを関数の形で実装してみたいと思います．
簡単のため，自然数での実装とします．

コンピュータに筆算させる

完成品がこちらになります．

function addBigInt(string $a, string $b): string
{
    // 自然数を受け取る
    $reversedDigit1 = array_reverse(str_split($a));
    $reversedDigit2 = array_reverse(str_split($b));
    $reversedSumDigit = array_fill(
        0,
        /* 足す数のうち，大きい方の桁数 */ max(count($reversedDigit1), count($reversedDigit2)),
        /* 0 で埋めた配列 */ 0
    );

    // 各位の足し算をする
    $carryOver = 0; // 繰り上がりの数字 (2 つの数の足し算なら必ず 0 or 1)
    foreach ($reversedSumDigit as $power => $digit) {
        // 直接要素をいじりたいので， $reversedSumDigit[$power] を変数化しない
        $reversedSumDigit[$power] += $carryOver;
        $carryOver = 0;

        $reversedSumDigit[$power] += $reversedDigit1[$power] + $reversedDigit2[$power];
        if ($reversedSumDigit[$power] >= 10) {
            $carryOver += floor($reversedSumDigit[$power] / 10);
            $reversedSumDigit[$power] %= 10;
        }
    }

    // 最後の桁の繰り上がりを考慮
    if ($carryOver > 0) {
        $reversedSumDigit[] = $carryOver;
    }

    // 再び逆順にすれば答えになる
    return implode(array_reverse($reversedSumDigit));
}

100 桁の整数を受け取る

今回の環境で int 型の最大の数は次の通りです．

var_dump(PHP_INT_MAX); // int(9223372036854775807)

19 桁．
100 桁には到底及ばないので，整数を文字列で受け取り，文字列で返すことにします．

function addBigInt(string $a, string $b): string
{
    return '';
}

1 桁ずつ配列に収めて各位で足し算をする

筆算は一般的に 1 の位から順に行うので，受け取った文字列を逆順で配列に収めます．

// 自然数を受け取る
$reversedDigit1 = array_reverse(str_split($a));
$reversedDigit2 = array_reverse(str_split($b));

逆順に収めておくと，配列のインデックス番号が 10 の累乗部分そのものになるので計算しやすくなります．

// 各位の足し算をする
$carryOver = 0; // 繰り上がりの数字 (2 つの数の足し算なら必ず 0 or 1)
foreach ($reversedSumDigit as $power => $digit) {
    // 直接要素をいじりたいので， $reversedSumDigit[$power] を変数化しない
    $reversedSumDigit[$power] += $carryOver;
    $carryOver = 0;
    $reversedSumDigit[$power] += $reversedDigit1[$power] + $reversedDigit2[$power];
    if ($reversedSumDigit[$power] >= 10) {
        $carryOver += floor($reversedSumDigit[$power] / 10);
        $reversedSumDigit[$power] %= 10;
    }
}

// 最後の桁の繰り上がりを考慮
if ($carryOver > 0) {
    $reversedSumDigit[] = $carryOver;
}

数字が逆順になっていたので，元に戻して完成

文字列で返します．

// 再び逆順にすれば答えになる
return implode(array_reverse($reversedSumDigit));

再計算！

var_dump(addBigInt(
    '2345760293460295683704558703456102394871348756109347501936410934756102913874187344541930193470934875',
    '7947618927365019364019257691823461928734634570193248703473987562093471093576293478628949398873429857'
));

結果

string(101) "10293379220825315047723816395279564323605983326302596205410398496849574007450480823170879592344364732"

うおおおおおおおおおおお
ちゃんと計算できてますね．

もっと増やしてもちゃんと計算してくれます．

var_dump(addBigInt(
    '912737487163405918273410730417265019827364107277350123412012745625927341972568902713780850717457812370418984756601723460197236495188772346318765091765127363109837412873561009237462421287346041972650192837461873568364192837464193865103948571238741602957163184971620398471348160239471694857629384761528375165299384710397610347102938471057109471929387912347103945761348571039847102934633329457693487120398855703947198434618237466193744642173654165247634516234278458645056978560980690867798069684974562938740234875601982374918723659517364716523498172625398176230471645981732948710234971602359175234567324',
    '123652387065670597706023401234982497590123407123680183455013284812330953490713456773049987353980572364096780450287409287645097665450287342987439276093478610932476093745620985710934476103498761923874629478612384762839439878563545862399958304984756983409233938793038473949458162862368345760806798080800609819236732348345628345222735234725325734821978378294398249756924877266895898237946170284762875887039846752934762330953872469857872394368754654245343375176247702983567623478610943865759675412563561984357209568793645982345727483865817236460394867249128621423873458374458623485886442938467634715623412'
));

もはや意味わからないけどｗ

string(601) "1036389874229076515979434131652247517417487514401030306867026030438258295463282359486830838071438384734515765206889132747842334160639059689306204367858605974042313506619181994948396897390844803896524822316074258331203632716027739727503906876223498586366397123764658872420806323101840040618436182842328984984536117058743238692325673705782435206751366290641502195518273448306743001172579499742456363007438702456881960765572109936051617036542408819492977891410526161628624602039591634733557745097538124923097444444395628357264451143383181952983893039874526797654345104356191572196121414540826809950190736"

感想

int の壁を破って計算できたのはうれしいです．
同じ考え方で他の四則演算もできるのではないかと思っています． (時間があったら実装してみたいです．)

調子乗ってすみませんでした