大きな数

ナビゲーション: ガイド | ドキュメントルート

V0.2 の数値オーバーフロー構文は、検査付きの算術演算のたびに i128 中間結果の上位半分と下位半分を束縛します。これは、64 ビット符号付き整数である同梱の Word 型に対する多桁算術の要となる仕組みです。本ガイドでは、examples/scripts/09_big_numbers.kel の実例を用いてこのパターンを解説します。

この構文が公開するもの

この構文の表層形式は次のとおりです。

op_expr {
    ok(v)             => arm_body,
    overflow(h, l)    => arm_body,
    underflow(h, l)   => arm_body,
}

ランタイムは op_expr の真の結果を i128 で計算し、それを上位半分と下位半分に分割して (high, low, flag) をオペランドスタックにプッシュします。コンパイラは flag によって 3 つの結果クラス（ok、overflow、underflow）のいずれかにディスパッチし、その分岐の本体内のパターン変数を対応するスロット値に束縛します。ok の分岐は範囲内の結果に対して単一の Word を束縛します。overflow と underflow の分岐は、上位半分と下位半分に対して 2 つの Word 値を束縛します。

上位半分は、加法系の演算では桁上げ出力であり、乗算では真の積の上位 64 ビットです。下位半分（ラップされた i64 の結果）と合わせると、これは連鎖する多桁算術を表現するのに十分です。

パターン：完全な 64x64 -> 128 ビット乗算

fn mul_full(a: Word, b: Word) -> (Word, Word) {
    a * b {
        ok(v) => (0, v),
        overflow(h, l) => (h, l),
        underflow(h, l) => (h, l),
    }
}

真の積が Word に収まる場合は ok の分岐が発火し、上位半分は定義により 0 になります。積が 64 ビットを超える場合、この構文は overflow の分岐へ経路付けし、真の積の上位 64 ビットを h に束縛します。

実例：2^32 * 2^32 = 2^64。真の積はビットパターン 0x0000000000000001_0000000000000000 を 128 ビット値として解釈したものです。上位半分は 1、下位半分は 0 です。スクリプトの main は 1 を返し、この分解を確認します。

パターン：桁上げ出力を伴う加算

fn add_with_carry(a: Word, b: Word) -> (Word, Word) {
    a + b {
        ok(v) => (0, v),
        overflow(_, l) => (1, l),
        underflow(_, l) => (1, l),
    }
}

桁上げ出力は、上位半分から直接ではなく overflow クラスから導出されます。符号付きの Word 加算では、i128 中間結果の上位半分は i64 のラップの符号拡張であり、符号なしの桁上げではありません。よりクリーンな抽象化は、結果クラスから桁上げを読み取ることです。ラップされた結果は下位スロットに残ります。

連鎖する 2 桁の加算は、桁上げを次に高い位置へ伝播します。

fn add_two_digits(a_hi: Word, a_lo: Word, b_hi: Word, b_lo: Word) -> (Word, Word) {
    let (carry_lo, sum_lo) = add_with_carry(a_lo, b_lo);
    let (_, partial_hi) = add_with_carry(a_hi, b_hi);
    let (_, sum_hi) = add_with_carry(partial_hi, carry_lo);
    (sum_hi, sum_lo)
}

完全な 256 ビット加算では、同じ手順を 4 つの Word 位置にわたって繰り返し、桁上げを各手順に通していきます。

注意点

Word 型は符号付きの i64 です。多桁算術においてこれを符号なしの u64 桁として扱うには注意が必要です。

i128 中間結果の上位半分は符号付き算術を反映します。和が i64::MAX を超える 2 つの非負オペランドの場合、上位半分は 0 であり、下位半分はラップ（そのビットパターンが符号なしの和の最上位ビットに一致する負の i64）です。桁上げ出力はいずれにせよ 1 であり、overflow クラスから導出できます。
和が 65 ビットを超える必要のある 2 つのオペランド（i64 の加算では不可能ですが、乗算を通じて到達可能）の場合、上位半分は真のビット 64〜127 を保持します。乗算の例がこのケースを直接示しています。
除算と剰余は、専用の Op::CheckedDiv および Op::CheckedMod オペコードを経由します。これらは真の結果を i128 で計算し、他の検査付き演算と同じ (h, l, flag) の形状にディスパッチします。i64::MIN / -1 のコーナーケース（真の結果 2^63、high=0, low=i64::MIN, flag=1 として分解される）は overflow の分岐へ経路付けされ、i64::MIN % -1 のコーナーケース（真の結果 0、除算ステップがオーバーフローする）も同様に high=0, low=0 で overflow の分岐を通してフラグ付けされます。ゼロ除算は、分岐ディスパッチが走る前にオペコードが失敗するため、引き続き VmError::DivisionByZero でトラップします。

このパターンが適切な場合と適切でない場合

この構文は次の場合に適切です。

プログラム内の明確に定義された地点で、算術演算が Word 範囲のオーバーフローを検出または回復する必要がある場合。
乗算の上位半分が有用な情報を持つ場合（真の 64x64 -> 128 積における最も重要なケース）。
加算の桁上げ出力を、より上位の桁に引き継ぐ必要がある場合。

この構文は、任意精度の BigInt 型の代替ではありません。この構文による実行時の多桁算術は機能しますが、人間工学的にゼロコストというわけではありません。将来のイテレーションでは、内部で連鎖したチェック付き演算にコンパイルされるネイティブ算術演算子を備えた、専用の BigInt 標準ライブラリ型が導入される可能性があります。

相互参照

GRAMMAR.md、セクション 7.5 — 数値オーバーフロー構文の形式文法。
LANGUAGE_DESIGN.md、「部分演算の処理」 — 設計上の根拠。チェック付き算術はその構文ファミリーの一員です。
examples/scripts/09_big_numbers.kel — このガイドが解説する実践例。
tests/big_number_arithmetic.rs — この例をコンパイルして結果を検証する統合テスト。

Keyboard shortcuts