LoginSignup
5
1

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-12-01

こちらの記事は 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'
));

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

string(601) "1036389874229076515979434131652247517417487514401030306867026030438258295463282359486830838071438384734515765206889132747842334160639059689306204367858605974042313506619181994948396897390844803896524822316074258331203632716027739727503906876223498586366397123764658872420806323101840040618436182842328984984536117058743238692325673705782435206751366290641502195518273448306743001172579499742456363007438702456881960765572109936051617036542408819492977891410526161628624602039591634733557745097538124923097444444395628357264451143383181952983893039874526797654345104356191572196121414540826809950190736"

感想

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

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

5
1
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
1