Zenn
🧮

【JavaScript】BigIntに頼らずにNumber型の限界を超えてみる

2024/09/05に公開
JavaScript
TypeScript
tech

Number型で正常に扱える整数値の上限は、Number.MAX_SAFE_INTEGERで定義される値（一般的には9007199254740991）です。それより大きい整数値を扱うにはBigInt型を利用することになります。

ですが、今回は数値を文字列型で扱い、BigInt型にすることなくNumber型の限界を超えた計算ができるようにしてみたいと思います。時間の都合上、自然数の足し算だけやってみます。

どうやるの？

もちろん、普通の構文でNumber型を超えることはできません。今回は、小学校で習った筆算のアプローチを参考にしながら、各位ごとに計算して繰り上げを行います。

こうすることで、各位の計算は9 + 9 + 繰り上がりまでに収まりますから、Number型の範疇で十分計算が行えるわけです。

完成品

そして出来上がったのがこちらになります。

type IntLike = bigint | number | string;

function parseIntLike(x: IntLike): string {
    if (typeof x === 'bigint' && x >= 0) {
        return x.toString();
    } else if (typeof x === 'number') {
        if (x % 1 === 0 && x >= 0) {
            return x.toString();
        } else  {
            throw new Error('not a positive integer or zero');
        }
    } else if (typeof x === 'string') {
        if (/^\d+$/.test(x) && x[0] !== '-') {
            return x.replace(/^0+/, '');
        } else {
            throw new Error('not a positive integer or zero');
        }
    } else {
        throw new Error('not a positive integer or zero');
    }
}

// 整数を文字列で足す関数
function add(a: IntLike, b: IntLike): string {
    // 整数に変換
    const aStr = parseIntLike(a);
    const bStr = parseIntLike(b);

    // 位ごとに分割してそれぞれをnumber型に変換
    const aArr = aStr.split('').reverse().map(x => parseInt(x, 10));
    const bArr = bStr.split('').reverse().map(x => parseInt(x, 10));

    // 各位を足して繰り上がりを処理
    const result: number[] = [];
    let carry = 0;

    for (let i = 0; i < Math.max(aArr.length, bArr.length); i++) {
        const sum = (aArr[i] || 0) + (bArr[i] || 0) + carry; // 位の和
        result.push(sum % 10); // 位の和の下一桁を結果に追加
        carry = Math.floor(sum / 10); // 繰り上がり
    }

    // 繰り上がったけど足す相手が居ない場合は、新しい位が必要だということ
    while (carry > 0) {
        result.push(carry % 10); // 繰り上がりがあれば結果に追加
        carry = Math.floor(carry / 10); // 繰り上がり
    }

    return result.reverse().join('');
}

しくみ

parseIntLike

無駄に通常のNumber型やBigInt型も受け付けるようにしたため、それらをバリデーション（自然数もしくは0であるか）したうえで文字列に変換する関数です。

add

こっちが本命。まず、整数になったふたつの値を１位ごとに分割して配列に入れます。

このとき、各数字は配列にこのような順番で格納されます。

でも、これだと配列のインデックスの番号とくらいの番号が、入力した桁数によって変動してしまい、操作が面倒臭くなってしまいます。

そこで、reverse()を使用して配列の順番を逆転させます。するとこうなります。

こうすると、配列の0番目には1の位、配列の1番目には10の位…のように桁数と配列の番号を対応させることができます。直感的ではないですが処理はしやすくなりましたね！


心なしかこんな風にも見えてくる

reverseした後は、配列の各値に同じ操作を行って値を加工するmap関数を使用して、それぞれの位ごとにnumber型にします。

あとは、対応させた各位ごとに計算を行うだけです。これはもう筆算ですね！

  1. 同じ位同士と繰り上がりの数値を足す
  2. ①の結果が10を超えた場合は1の位の数値だけを結果の配列に入れ、繰り上がりの数値を別（この場合、carryという変数）で記録する
  3. ①～②を繰り返す

こんな感じで、文字列を利用して理論上はどこまでも足し算することができるようになりました！

試してみる

結果がNumber.MAX_SAFE_INTEGERを超える計算は不正確になります。例えば、

Number.MAX_SAFE_INTEGER + 1 // -> 9007199254740992

Number.MAX_SAFE_INTEGER + 2 // -> 9007199254740992 あれ！？

といった具合です。ここで、今回作った関数を使用してみましょう。

add(Number.MAX_SAFE_INTEGER, 1)

add(Number.MAX_SAFE_INTEGER, 2)

さあ、結果はどうなったでしょうか…！

おおー！BigIntを使わず、Number型の限界を突破することに成功しました🎉同じようにすれば、四則演算や正負の計算くらいならBigIntなしで実装できそうですね！

やはり筆算は最強であるということが証明できました（？）

まあ、実用性はあまりないですが。

Discussion