第3章 · 有理数

整数の比から、有理数を実装する¶

整数まで広げても 1÷2 の答えは作れません。分子と分母に整数を保存し、異なる分数表現を同じ値として扱う規則を、コンストラクタ・等号・約分の実装へ接続します。

前章から使うもの

整数の代表元、同値関係、整数の乗法と等号、ログの表示範囲。

この章で学ぶこと

整数の比、分母の不変条件、交差積、約分を必要なときだけ行う設計。

この章を終えると

Rational.p と Rational.q が何を保存するか説明できる
交差積の定義を __eq__ と実行ログへ対応付けられる
表現を保存すること、値が等しいこと、約分することを区別できる

数学

整数の比 p/q を作り、交差積が等しい比を同じ値とします。

データ表現

Rational.p と Rational.q に、分子と分母の整数を保存します。

実装

__post_init__ が分母を検査し、__eq__ が交差積を比較します。

この章で横に置く実装

完全なクラス: peano/rational.py の Rational。本文では作成時検査、等号、加法、約分、ハッシュを抜粋します。

分母0・交差積・約分の検査: tests/test_rational.py。ファイル索引は実装リファレンスにあります。

数学上の定義

分数の等しさを、整数の演算だけで定義する¶

p/q の上の p を分子、下の q を分母と呼びます。分母は0にできません。0で割ることは有理数の演算として定義しないためです。

1/2 と 2/4 は表記が違いますが、同じ大きさです。小数へ直さなくても、斜めに掛けた二つの積で判定できます。

p/q ∼ r/s ⇔ p×s = q×r

1/2 と 2/4 なら 1×4=2×2 です。前章と同じく、∼ は「違う代表元だが同じ値を表す」という同値関係です。この関係で整数の比をまとめたものを有理数と呼びます。

有理数の加法も、整数の演算だけで定義できます。

p/q + r/s = (p×s + q×r)/(q×s)

たとえば 1/2+1/3=(1×3+2×1)/(2×3)=5/6 です。

データの表し方

作成時に守る条件と、あえて変えない表現¶

実装では、有理数一つが二つの Integer を持ちます。

@total_ordering
@dataclass(frozen=True, slots=True, eq=False, repr=False)
class Rational:
    p: Integer
    q: Integer

    def __post_init__(self) -> None:
        if not isinstance(self.p, Integer) or not isinstance(self.q, Integer):
            raise TypeError("Rational.p and Rational.q must be Integer values")
        if self.q == Z_ZERO:
            raise ZeroDivisionError("the denominator cannot be zero")

Rational を作った直後に __post_init__ が呼ばれ、表現が最低限の条件を満たしているか検査します。

生成された __init__ と、手書きの検査を接続する

__post_init__ を利用者が直接呼ぶ必要はありません。 dataclassが生成した __init__ が p と q を設定し、直後にこの検査処理を呼びます。作成に成功したすべてのRationalで「両方がIntegerで、分母は0でない」という不変条件が成立します。

ここで self.q == Z_ZERO は、前章で読んだ整数の同値関係を使います。分母の代表元が (2,2) でも、それは整数0と等しいので拒否されます。上の数体系が下の数体系の実装を再利用している具体例です。

rational(1,2) は、Python標準の整数1と2から Integer を二つ作り、 Rational へ渡す短縮関数です。このライブラリの有理数が、 Pythonに用意された別の数値型へ置き換わるわけではありません。

def rational(numerator: int, denominator: int) -> Rational:
    return Rational(integer(numerator), integer(denominator))

このライブラリは、作成時に 2/4 を 1/2 へ自動約分しません。また 1/−2 の分母を自動で正にしません。

操作	保存される表現	表す値
`rational(2,4)`	`2/4`	`1/2` と等しい
`rational(1,-2)`	`1/−2`	`−1/2` と等しい
`rational(2,4).reduction()`	`1/2`	元と同じ

Pythonでの実装

交差積と通分を、そのままメソッドにする¶

Pythonの half == two_quarters は Rational.__eq__ を呼びます。次がログ文字列を含む完全な実装です。

@log(log_level=21)
def __eq__(self, other: object) -> tuple[bool, LogMessage]:
    converted = _coerce_rational(other)
    if converted is None:
        return (
            cast(bool, NotImplemented),
            lambda: f"{self!r} == {other!r} = NotImplemented",
        )
    result = self.p * converted.q == self.q * converted.p
    return (
        result,
        lambda: (
            f"{self!r} == {converted!r} ⇔ "
            f"{self.p!r} * {converted.q!r} == "
            f"{self.q!r} * {converted.p!r}"
        ),
    )

数学	実装
左の交差積 `p×s`	`self.p * converted.q`
右の交差積 `q×r`	`self.q * converted.p`
二つの積が等しい	整数の `__eq__` で比較

Rational.__add__ も加法の定義から直接、新しい分子と分母を作ります。

@log(log_level=24)
def __add__(self, other: object) -> tuple[Rational, LogMessage]:
    converted = _coerce_rational(other)
    if converted is None:
        return (
            cast(Rational, NotImplemented),
            lambda: f"{self!r} + {other!r} = NotImplemented",
        )
    result = Rational(
        self.p * converted.q + self.q * converted.p,
        self.q * converted.q,
    )
    return (
        result,
        lambda: (
            f"{self!r} + {converted!r} = "
            f"({self.p!r} * {converted.q!r} + "
            f"{self.q!r} * {converted.p!r}) / "
            f"({self.q!r} * {converted.q!r})"
        ),
    )

この一行の中では整数の乗法と加法が動き、その内部ではさらに自然数の演算が動きます。自然数 → 整数 → 有理数は、説明上の順序だけでなく実際の呼び出し関係です。

約分は別の reduction() に分離されています。

def reduction(self) -> Rational:
    numerator = self.p.normalize()
    denominator = self.q.normalize()
    if denominator < Z_ZERO:
        numerator, denominator = -numerator, -denominator

    a, b = abs(numerator), abs(denominator)
    while b:
        a, b = b, a % b
    divisor = Integer(a, N_ZERO)
    return Rational(numerator // divisor, denominator // divisor)

まず分子・分母を整数として正規化し、分母を正に揃え、最大公約数で割ります。元の Rational は不変なので、reduction() は同じ値を表す新しいオブジェクトを返します。

実行して確かめる

有理数の等号ログは、内部の整数計算を要約する¶

Rational.__eq__ のログレベルは21です。次の実験では、交差積を作ったという有理数層の一行だけを表示します。

実行前に、ログの部品を予想

上に抜粋した Rational.__eq__ の result とログ文字列を参照し、1/2 と 2/4 のどの整数どうしが掛けられるかを書き、最後の判定を予想してください。

⌘ / Ctrl + Enter

出力

交差積の定義と有理数の等号ログを照合します。

Q と Z を層として読む

<Q(1/2)> と <Q(2/4)> は比較した有理数の代表元です。右側の <Z(1,0)> * <Z(4,0)> と <Z(2,0)> * <Z(2,0)> は交差積を作る整数演算です。 Q は有理数、Z は整数という実装上の表示です。

ログには、等しさを判定する二つの交差積が表示されます。それぞれの積4までは表示しないため、式を実装へ戻し、最後の True と合わせて判断します。

log_level=21 は21未満の整数・自然数ログを隠します。 log_level=15 に変えると整数乗法も見え、log_level=4 まで下げると自然数加法も見えます。ただし出力量は急に増えます。ログレベルは、自然数や整数の途中計算まで表示するか選ぶためのフィルターで、通常の本文には表示されません。

有理数の加法だけを見る次の実験では、設定値24を使います。

もう一度、実装から予想

上に抜粋した Rational.__add__ の result を参照し、新しい分子と分母を先に計算してください。

⌘ / Ctrl + Enter

出力

分子・分母の構築式と、表示された5/6を照合します。

テストで確かめる

テストは定義、不変条件、正規化を別々に確かめる¶

加法のテストは、分子・分母を小さな範囲で動かし、定義式と照合します。

self.assertEqual(
    rational(i, j) + rational(k, m),
    rational(i * m + j * k, j * m),
)

表現が異なっても同じハッシュ値になること、約分が値を変えないことも別に検査します。

self.assertEqual(hash(rational(i, j)), hash(rational(i * 2, j * 2)))
self.assertEqual(rational(16, 9).reduction(), rational(16, 9))

ハッシュは、辞書や集合が値をすばやく探すために使う整数です。 Pythonのデータモデルには「a == b なら hash(a) == hash(b)」という契約があります。そのため Rational.__hash__ は、保存された 2/4 から直接ハッシュ値を求めず、 reduction() で同じ値を同じ標準形へ揃えてから求めます。数学上の等値関係を __eq__ だけでなく、コンテナの振る舞いへも反映する実装です。

def __hash__(self) -> int:
    reduced = self.reduction()
    if reduced.q == Z_ONE:
        return hash(reduced.p)
    return hash(("Rational", int(reduced.p), int(reduced.q)))

そして、分母0は正常な値を返すのではなく、例外になることを確かめます。

with self.assertRaises(ZeroDivisionError):
    rational(1, 0)

「正しい入力の演算」と「不正な入力を拒否する不変条件」は、異なる責務なのでテストも分かれています。

次に必要になるもの

有理数で表せない数が、次の実装課題になる¶

x×x=2 を満たす数を √2 と書きます。√2 は整数どうしの比では表せないため、この Rational だけでは値を構築できません。

発展 · √2が有理数でない理由

√2を既約分数 p/q と仮定すると p²=2q² です。ここから p と q が両方とも2で割れることになり、既約という仮定に反します。したがって√2は有理数ではありません。

この不足はライブラリの失敗ではなく、数体系を広げる動機です。次章では √2 をいきなり小数として近似せず、まず x²−2 という多項式を保存し、 0になる場所を調べます。

多項式へ進む →