桁があふれるぐらい大きな整数で加減算をしてみる

はじめに

初カキコ…ども…
マークダウンとかWikipediaぐらいしか経験無いので許してください。
この内容絶対既出ですが見つからないのでどこにあるか誰か教えてください！
あとプログラムとか初心者なんでこうした方がいいとかぜひコメント下さい。

概要

64bitもしくは32bitを超える符号なし整数(integer)が桁あふれを起こすことは周知の事実ですが、桁があふれるぐらい大きな整数をどう扱えばいいの？という疑問に誰も答えてくれなかったので考えてみました。
てか普通に誰か考えてると思うけどまあ車輪の再発明は悪いことではないでしょう。

実装

格納

まずは64bitで表せる最大値、すなわち9223372036854775807を越える数字を格納します。
え、いやまあ一の位から順番に配列に格納していくだけです。

格納

//9223372036854775808を格納する
$num = '9223372036854775808';
$digit = strlen($num);

for($i=$digit-1;$i>=0;$i--){
 $array[$i] = substr($num, $i, 1);
}

for文の条件式が汚いような。arrayにした時に0番目を一の位にするか最上位にするかはお好みかな？

足し算

足し算をします。$1+1=2$、簡単だね。

足し算

function array_add($a,$b){//$a:足される数、$b:足す数。それぞれarray

    //大きい方の桁数を取得
    if(count($a)>count($b)){
        $n = count($a);
    }else{
        $n = count($b);
    }

    $c[0] = 0;
    for($i=0;$i<$n;$i++){

        //undifined対策
        if(!isset($a[$i])){
            $a[$i] = 0;
        }elseif(!isset($b[$i])){
            $b[$i] = 0;
        }

        $c[$i] = $a[$i] + $b[$i] + $c[$i];
        
　　　　//繰り上がり処理
        if($c[$i]>9){
            $c[$i+1] = 1;
            $c[$i] -= 10;
        }else{
            $c[$i+1] = 0;
        }
    }

　　//最後に頭に0が着くことがあるので消す
    $m = count($c)-1;
    for(;$c[$m] == 0;$m--){
            unset($c[$m]);
    }

    return $c;
}

これだけ。特に無駄はないと思うんだけどどうだろう？最後の0消すfor文はいらないかもしれない。

引き算

引き算をします。$2-1=1$、簡単だね。

引き算

function array_sub($a,$b){//$a:足される数、$b:足す数。それぞれarray

    //大きい方の桁数を取得
    if(count($a)>count($b)){
        $n = count($a);
    }else{
        $n = count($b);
    }

    $c[0] = 0;
    for($i=0;$i<$n;$i++){

        //undifined対策
        if(!isset($a[$i])){
            $a[$i] = 0;
        }elseif(!isset($b[$i])){
            $b[$i] = 0;
        }

        $c[$i] += $b[$i] - $a[$i];

　　　　//繰り下がり処理
        if($c[$i]<0){
            $c[$i] += 10;
            $c[$i+1] = -1;
        }else{
            $c[$i+1] = 0;
        }
    }

　　//最後に頭に0が着くことがあるので消す
    $m = count($c)-1;
    for(;$c[$m] == 0;$m--){
            unset($c[$m]);
    }

    return $c;
}

足し算と引き算は同じものだと実感しました。

掛け算(おまけ1)

まだ任意桁×一桁しか出来てません。

掛け算

function array_multi_single($a,$b){//$a:掛けられる数、任意桁 $b:掛ける数、一桁　それぞれarray
    $n = count($a);
    $c[0] = 0;
    for($i=0;$i<$n;$i++){
        $c[$i] += $a[$i]*$b;

        //繰り上がり処理
        if($c[$i]>9){
            $d = (int)floor($c[$i]/10);
            $c[$i] -= 10*$d;
            $c[$i+1] = $d;
        }else{
            $c[$i+1] = 0;
        }
    }

　　//最後に頭に0が着くことがあるので消す
    $m = count($c)-1;
    for(;$c[$m] == 0;$m--){
            unset($c[$m]);
    }

    return $c;
}

足し算より短く済むことに驚きを隠せないが当然である。

べき算(おまけ2)

上の掛け算を使うとべき算もできます。

べき算

function array_pow($a,$b){//$a:基数、$b:指数。$aの$b乗
    $c = $a[0];

　　//0乗は1
    if($b == 0){
        return array(1);
    }

    for(;$b>1;$b--){
        $a = array_multi_single($a, $c);
    }
    return $a;
}

2の1024乗とかが意外と速くもとまってびっくり

まとめ

くぅ～疲れましたw これにて完結です！
一言で言えば、筆算、ですね。やってることは完全に筆算です。なので掛け算の計算量は$O(n^2)$になっているはず。つまりもっと計算量を減らせるということですね。
このアイデア僕が一番乗りとは決して思えないんで、同じことしてるサイトとかあったら教えてください。あとソースの改善とか、お叱りとか、お待ちしております。