任意精度演算（多倍長整数）の内部

固定幅の壁と、桁配列という発想

CPU が直接扱える整数は 32bit や 64bit の固定幅です。これを超える値は単独のレジスタに収まらず、整数表現と2の補数・オーバーフロー で見たようにラップアラウンドや未定義動作を起こします。任意精度演算（arbitrary-precision arithmetic、多倍長整数）は、この壁を1つの数を複数ワードの配列で表すことで取り払います。

発想は筆算と同じです。普段は基数10の各桁を並べて数を書きますが、多倍長整数では基数を 2^32 や 2^64 に取り、1ワードを「1桁」として配列に詰めます。基数 B = 2^64 のとき、配列 [d0, d1, d2]（リトルエンディアン、下位が先）が表す値は d0 + d1·B + d2·B^2 です。各 di は 0 以上 B 未満で、これをリム（limb） と呼びます。

値 = Σ d[i] · B^i        （B = 2^64, 0 <= d[i] < B）
配列長 n が桁数。値の大きさ N に対し n ≈ log_B(N) = (bit長)/64

基数を 2 の冪に取るのが要点です。B = 2^64 なら、桁の繰り上げは単に「64bit からあふれた分を上位ワードへ送る」だけになり、ハードウェアのワード演算とビットシフトに直結します。符号は配列とは別に符号フラグや符号付き長さで持つのが普通で、こうして大きさ（magnitude）と符号を分離します。

加減算：桁上がりの伝播

加算は筆算そのものです。下位リムから順に対応するリムを足し、基数 B 以上になったら桁上がり（キャリー） を1つ上のリムへ繰り越します。

carry = 0
for i in 0..n-1:
    t = a[i] + b[i] + carry      # 最大 2(B-1)+1 で 1ワードに収まらない
    result[i] = t mod B          # 下位 64bit
    carry = t div B              # 0 か 1（あふれビット）
result[n] = carry                # 最上位の繰り上がり

ここで t は1リムを超えうるため、実装はハードウェアのキャリーフラグ（x86 の adc＝add-with-carry など）を使い、あふれを次の加算に直接送ります。これで t mod B と t div B を分離する明示的な割り算は要りません。減算は桁借り（ボロー）を伝播させる対称的な処理で、sbb（subtract-with-borrow）に対応します。どちらも桁数 n に比例する O(n) で、これより速くはできません（全桁を読む必要があるため）。

乗算：閾値で切り替わる3〜4段のアルゴリズム

多倍長演算の性能を決めるのは乗算です。ここが任意精度ライブラリの心臓部で、桁数に応じて複数のアルゴリズムを閾値（threshold） で切り替えます。これは 分割統治法とマスター定理 で扱った漸化式の指数を、桁数帯ごとに最良へ寄せる戦略です。

筆算は各リムの総当たりで n^2 回の積を行います。定数倍が小さくキャリー処理も単純なので、桁数が小さいうちは一番速い。Karatsuba は数を上下半分に割り、本来4回必要な部分積を代数的工夫で3回に減らします（z1 を (x1+x0)(y1+y0) − z2 − z0 で得る）。これで指数が log_2 3 ≈ 1.585 に下がります。

x = x1·B^m + x0,  y = y1·B^m + y0    （m は桁数の半分）
z2 = x1·y1
z0 = x0·y0
z1 = (x1 + x0)·(y1 + y0) − z2 − z0    ← 部分積を3回に圧縮
xy = z2·B^(2m) + z1·B^m + z0

Toom-Cook はこれを一般化し、数を k 個に分割して多項式とみなし、いくつかの点で評価して積を求め、補間で係数を復元します。Toom-3 なら指数は約 1.465。分割を増やすほど指数は下がりますが、評価・補間の前処理が増えて定数倍が膨らむため、効くのは桁数がさらに大きい領域です。

FFT（高速フーリエ変換）/ NTT（数論変換） は乗算を多項式の巡回畳み込みとみなし、ほぼ線形時間で計算します。係数を周波数領域へ変換すると畳み込みが要素ごとの積になり、逆変換で戻すという原理です。実用ライブラリが使う Schönhage–Strassen 法の計算量は厳密には O(n log n log log n) で、真の O(n log n)（2019年の Harvey–van der Hoeven）は定数倍が現実的でなく実装には使われません。浮動小数点 FFT は丸め誤差の管理が要るため、ライブラリは誤差のない整数演算で済む NTT（有限体上の FFT）を好みます。

除算・その他と、言語ランタイムでの実装

除算は加減乗より厄介で、商を1桁ずつ推定して補正する Knuth のアルゴリズム D が古典です。商の各桁を上位リムから見積もり、行き過ぎたら戻す（補正する）処理が入るため実装が複雑で、高速実装は乗算とニュートン法を組み合わせて逆数を求める手法を使います。十進文字列への変換も、素朴には O(n^2) だが分割統治で高速化されます。

各言語ランタイムは、上記の枠組みを共通して採りつつ「小さい数を速くする」工夫を重ねます。

CPython の int は最初から多倍長で、2^30 を基数とする桁配列で全整数を統一的に表します（小さな値も同じ構造で、ただし −5 から 256 はオブジェクトをキャッシュ）。JavaScript の BigInt は通常の number（IEEE 754 倍精度）とは別型で、リテラル末尾の n（123n）で作り、内部はリム配列を持つヒープオブジェクトです。number の安全整数上限 2^53 − 1 を超える正確な整数計算のために導入されました。これは 浮動小数点数とIEEE 754 の精度限界を、整数に限って取り払う仕組みと言えます。

まとめ

• 多倍長整数は固定幅ワード（リム）の配列で1つの数を表し、基数 2^64 などの位取りで巨大な値を扱う。符号は別フィールドに分離する。
• 加減算は下位リムからキャリー/ボローを伝播させる O(n)。ハードのキャリーフラグで効率化する。
• 乗算は桁数で筆算 O(n^2)→Karatsuba→Toom-Cook→FFT/NTT（ほぼ線形、実装は O(n log n log log n)）を閾値切り替えする。漸近的に速い手法ほど定数倍が大きく、大きい桁数でしか勝てない。
• GMP・CPython・V8・Java BigInteger はこの枠組みを共有しつつ、小さな値の高速化と閾値の作り込みで実用性能を出している。