Rational 内部表現と四則演算

概要

Rational は任意精度の有理数を表現するクラスで、 内部に 2 つの Int (分子 $p$、分母 $q$) を保持する。 値は次の不変条件を満たす:

$$x = \frac{p}{q}, \quad q > 0, \quad \gcd(|p|, q) = 1$$

四則演算のたびに binary GCD を用いて自動的に約分し、正規化された状態を維持する。 ゼロ除算は NaN 状態として安全に扱う。

API の使い方については Rational API リファレンス — 算術演算子 を参照。

内部表現と不変条件

クラスは以下の 2 つの Int メンバを持つ。

class Rational {
    Int num;   // 分子 p (符号付き)
    Int den;   // 分母 q (常に正、または NaN 状態では 0)
    // ...
};

不変条件:

• $q > 0$ — 符号はすべて分子側に集約する
• $\gcd(|p|, q) = 1$ — 約分済み (canonical form)
• $q = 0$ かつ $p = 0$ は NaN 状態 — それ以外の $q = 0$ も NaN

$q > 0$ の不変条件があるため、符号判定は分子だけを見ればよく、 比較演算で「分母の符号で不等号が反転する」面倒を回避できる。

正規化は基本的にコンストラクタと各演算子の末尾で行われ、 ユーザーは常に約分済みの値を受け取る。 パフォーマンス上の理由で約分をスキップしたい場合は Rational(num, den, /*doReduce=*/false) で構築し、 後から reduce() を明示呼び出しできる。

自動約分 — binary GCD

約分のコア演算は GCD である。 $p/q$ を約分するには $g = \gcd(|p|, q)$ を求めて両方を $g$ で割る。

sangi は Stein の binary GCD アルゴリズムを使用する。 ユークリッドの互除法 ($O(\log \min(a, b))$ 回の剰余) と漸近計算量は同等だが、 多倍長除算の代わりに 2 のべき除算 (右シフト) と減算で済むため、 各反復のコストが格段に小さい。

$$\gcd(a, b) = \begin{cases} a & (b = 0) \\ 2 \gcd(a/2, b/2) & (a, b \text{ 共に偶}) \\ \gcd(a/2, b) & (a \text{ 偶}, b \text{ 奇}) \\ \gcd(a, b/2) & (a \text{ 奇}, b \text{ 偶}) \\ \gcd((a - b)/2, b) & (a, b \text{ 共に奇}, a \geq b) \end{cases}$$

多倍長 Int 同士の演算では右シフトと減算がいずれも線形時間 $O(n)$ で行えるため、 binary GCD は実用的に高速である。

加減算 — 中間肥大の抑制

素朴な式と中間肥大

素朴な実装は次の通り。

$$\frac{a}{b} + \frac{c}{d} = \frac{a d + b c}{b d}$$

$b$ と $d$ が大きい場合、この式は中間値 $a d, b c, b d$ を最大 $b \cdot d$ のスケールまで肥大化させる。 最後に約分で縮むが、計算コストは中間値のサイズに支配される。

共通因数を先に取り出す

$g = \gcd(b, d)$ を先に計算し、$b = g b'$, $d = g d'$ と書くと:

$$\frac{a}{b} + \frac{c}{d} = \frac{a d' + c b'}{g \, b' \, d'} = \frac{a d' + c b'}{\operatorname{lcm}(b, d)}$$

分子の中間値は $a d' + c b'$ のスケールに収まり、$b \cdot d / g$ に等しい $\operatorname{lcm}(b, d)$ を分母とする。 最後の約分は新分子 $a d' + c b'$ と $g$ の GCD のみで済み、軽い。 多倍長算術では中間サイズが直接コストに直結するため、この経路は実用的な高速化につながる。

計算量

• $\gcd(b, d)$: 1 回 — binary GCD で $O(M \log M)$ ($M = \max(\operatorname{size}(b), \operatorname{size}(d))$)
• 除算 $b / g$, $d / g$: 2 回
• 乗算 $a d'$, $c b'$, $b' d' g$: 3 回
• 加算と最終約分: それぞれ 1 回

減算 $a/b - c/d$ も同じ枠組みで実装する。

乗算

$$\frac{a}{b} \times \frac{c}{d} = \frac{a c}{b d}$$

素朴な実装は $a c$ と $b d$ を求めて約分するだけだが、 sangi は cross-cancellation により中間サイズを抑える。 $g_1 = \gcd(|a|, d)$, $g_2 = \gcd(|c|, b)$ を先に取り、

$$\frac{a}{b} \times \frac{c}{d} = \frac{(a / g_1)(c / g_2)}{(b / g_2)(d / g_1)}$$

と分子側・分母側で別々に約分する。 $a/g_1$ と $b/g_2$、$c/g_2$ と $d/g_1$ はすでに互いに素であり、 最終ステップでは追加の約分が不要 (または非常に軽い) になる。

$$\gcd\!\left(\frac{a}{g_1} \cdot \frac{c}{g_2}, \frac{b}{g_2} \cdot \frac{d}{g_1}\right) = 1$$

計算量は GCD 2 回 + 除算 4 回 + 乗算 2 回。

除算と剰余

除算

$$\frac{a}{b} \div \frac{c}{d} = \frac{a}{b} \times \frac{d}{c} = \frac{a d}{b c}$$

分子と分母を入れ替えてから乗算経路に流す。 $c < 0$ の場合は (a d) / (b c) の符号が分母側に出るため、 正規化フェーズで分子側に符号を移動し、$q > 0$ の不変条件を回復する。

剰余

有理数の剰余 r % s は数学的にはあまり標準的でないが、sangi では次のように定義する:

$$r \bmod s = r - \lfloor r / s \rfloor \cdot s$$

結果は再び有理数となる。 除算の商の整数化に floor を使うため、結果は常に $0 \leq r \bmod s < |s|$ (符号は $s$ に従う) を満たす。

比較 — cross-multiplication

$a/b$ と $c/d$ の比較を実数除算で行うと精度損失と速度低下が生じる。 sangi は cross-multiplication で完全に整数演算に帰着する。

$$\frac{a}{b} < \frac{c}{d} \iff a d < b c \quad (b, d > 0)$$

$b, d > 0$ の不変条件があるため、不等号の向きは反転しない。 実装は Int の乗算 2 回と Int 比較 1 回で済む。

C++20 三方比較演算子 <=> は std::partial_ordering を返す。 NaN の存在により全順序ではなく半順序となる:

• NaN と任意の値の比較は unordered
• NaN == NaN も false

Int / int との比較

$a/b$ と整数 $n$ の比較は cross-multiplication を使うまでもなく $a \lessgtr n b$ で済む (整数 $n$ を分母 1 の Rational と見なす特殊化)。 int も同様。 いずれも Int の比較・乗算で実装する。

符号・絶対値・逆数

逆数は分子・分母の入れ替えだけで完了するため、Rational の最大の利点の 1 つである ($O(1)$ で正確な逆数が得られる)。 Int や Float での逆数は除算が必要だが、Rational では構造的に無料である。

floor・ceil・round・trunc

$r = p / q$ の整数化はすべて Int 除算を通じて実装する。 いずれも結果は Int を返す。

$$\begin{aligned} \lfloor r \rfloor &= \operatorname{div}_{\text{floor}}(p, q) \quad (q \text{ 方向に切り捨て}), \\ \lceil r \rceil &= -\lfloor -r \rfloor, \\ \operatorname{trunc}(r) &= \operatorname{div}_{\text{trunc}}(p, q) \quad (\text{ゼロ方向}), \\ \operatorname{round}(r) &= \lfloor r + 1/2 \rfloor \quad (\text{半 hi half-up}). \end{aligned}$$

$q = 1$ (整数値) の場合はすべて自身の分子を返す。 frac(r) = r - floor(r) は再び Rational として返り、$0 \leq \operatorname{frac}(r) < 1$ を満たす。

NaN とゼロ除算

分母にゼロを与えると Rational はNaN 状態に入る。

Rational nan = Rational(1, 0);   // NaN
assert(nan.isNaN());

NaN の振る舞いは IEEE 754 と類似:

• NaN 同士の演算は NaN を返す
• NaN == NaN は false
• NaN を含む比較はすべて unordered (std::partial_ordering::unordered)
• isNaN() で明示的に判定できる

例外送出やプログラム停止は行わないため、計算チェーンが安全に進む。 最終結果が必要な箇所で isNaN() をチェックすればよい。

設計判断

毎回自動約分する理由

有理数の途中結果を約分せずに進めると、分子・分母のサイズが急速に増大し、 後続演算のコストが指数的に膨らむことがある。 正規化を毎回行うほうが、合計コストは小さく抑えられる。 さらに、ハッシュや比較で同値判定が単純化される ($p_1 = p_2 \land q_1 = q_2$ のみ確認すればよい)。

パフォーマンスが極めてクリティカルで途中結果の約分を省略したい場合のみ、 doReduce = false でコンストラクタを呼び、後で reduce() を明示する経路がある。

$q > 0$ の不変条件

分母を正に固定することで、比較・符号判定・三方比較がすべて分子だけで完結する。 分母の符号を考慮するために $\operatorname{sign}(b d)$ で不等号を反転するような場合分けが不要になる。 構築時と除算の正規化フェーズで、必要なら符号を分子側に移動する。

多倍長型での乗除算より GCD 主導

多倍長算術では、乗除算より GCD のほうがコストが小さい (binary GCD は線形時間の右シフトと減算で構成されるが、乗除算は超線形)。 したがって「先に GCD で共通因数を消す」戦略は乗算回数を増やしてでも有効である。 加減算・乗算ともに、約分を末尾でなく中間で行うことで合計コストを小さく保つ。

参考文献

• Stein, J. (1967). "Computational Problems Associated with Racah Algebra". Journal of Computational Physics, 1 (3), 397–405. (binary GCD)
• Knuth, D. E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3rd ed. Addison-Wesley, 1997. §4.5.1 (rational arithmetic), §4.5.2 (GCD).