大きな数

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

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

Note that the arm binds (h, l) while the runtime pushes low first, so the binding order is the reverse of the stack order. You never need the stack order to write a program, and it is stated here only because it is easy to misread the two as the same. The reason for it is that an uncaptured operation such as a bare a + b lowers to the checked opcode followed by PopN(2), which discards the flag and the high half and leaves the wrapped low half as the value of the expression.

上位半分は、加法系の演算では桁上げ出力であり、乗算では真の積の上位 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 を保持します。乗算の例がこのケースを直接示しています。
Division and modulo route through dedicated Op::CheckedDiv and Op::CheckedMod opcodes that compute the true result in i128 and dispatch to the same (h, l, flag) shape as the other checked operations. The i64::MIN / -1 corner (true result 2^63, decomposed as high=0, low=i64::MIN, flag=1) routes to the overflow arm; the i64::MIN % -1 corner (true result 0, division step overflows) likewise flags through the overflow arm with high=0, low=0. A zero divisor does not fail inside the opcode: CheckedDiv and CheckedMod reify it as flag 3 carrying the numerator, precisely so a zero_divisor(numerator) arm can bind it. An UNHANDLED zero divisor still surfaces as VmError::DivisionByZero, but through the compiled dispatch rather than from the opcode. This sentence previously gave the opposite mechanism, saying the opcode fails before arm dispatch runs.

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

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

プログラム内の明確に定義された地点で、算術演算が 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