~~はいちょっと今緊急で記事書いてるんですけども。~~

本来この記事は来年か再来年の国際ビット演算デー¹のために温めていたネタなのですが、とある事情で急いで形にしています。

この記事ではビット単位の論理積、排他的論理和、論理和の演算子にそれぞれ $\wedge$、$\oplus$、$\vee$ を使用します。

この記事の初版では「有限小数は循環節をもたない」という認識でコードを書いていましたが、信仰の変化のため「有限小数は循環節 $\dot{0}$ をもつ循環小数の一種である」としたコードに変更しました。

先に狂われたら立つ瀬がない

Anarchy Golf というコードゴルフサイトに、単位分数同士の二項演算をして単位分数を答える問題が出題されていました(私がこれを知ったのは 4 月 2 日だけどもうちょっと前から公開されていたっぽい?)。

問題はその中に四則演算だけではなくどう見てもビット演算な演算子もあってオイオイオイ。表題みたいなこと考える変態が俺以外にいるとか信じたくないのですが、世界は思ったよりも狂人に満ちているようです。

そんなわけで急いで有理数に対するビット演算というアイデアを具現化します。鉄は熱いうちに撃て。

論理積があればいい

以前書いた記事では、$n$ 番目のビットが立っているビット列として表現される数 $x \in S$ を $n$ を元として含む集合 $A \in S^\prime \subset \mathfrak{P}(\mathbb{Z})$ に写すことでビット演算 $S \times S \to S$ を集合演算 $S^\prime \times S^\prime \to S^\prime $ に帰着させるという方法を紹介するとともに、この考え方では有理数のビット演算を考えるときに問題が起こることを示しました。

有理数は有限小数または循環小数に展開できます。始点と終点に点を付する形で循環節を示すことにして、たとえば $\frac{3}{4} = 0.75$、$\frac{6}{7} = 0.\dot{8}5714\dot{2}$ です。しかし、有限小数は循環小数としても展開できます。よく話題になる $1 = 0.\dot{9}$ などがわかりやすいです。二進数でいうなら $1 = 0.\dot{1}$ といったところでしょうか。通常の整数に対するビット演算のときの結果と一致させるためには $0.\dot{1}$ ではなく $1$ の方を採用しなければいけませんから、集合に写すときもそれをもとに考えるべきです($\forall A \in \mathbb{Q}^\prime; \nexists k \in \mathbb{Z}; {\left\lbrace k - n \mathrel{:} n \in \mathbb{N}\right\rbrace} \subseteq A$)。しかし、論理和と排他的論理和では両辺が真でなくても真になる組み合わせがあることから、予期せず循環節 $\dot{1}$ が現れてしまうという問題がありました。言い換えると $\mathbb{Q}^\prime$ は集合環でないのでこれに写す方法では $\mathbb{Q} \times \mathbb{Q} \to \mathbb{Q}$ なるビット演算はうまく定義できません。

一方でビット単位の論理積ではこのような問題は起こりません。そこで、ビット単位の論理和やビット単位の排他的論理積ではビットで考えることを諦め、ビット単位の論理積から代数的に求めることにします。ビットで考えないビット演算とはこれ如何に。

$a + b$ を二進数で筆算することを考えます。一つの位だけに注目すると以下の表のようになります。

$a$ のある桁	$b$ のある桁	(繰り上がり)	桁のみで見た和
$0$	$0$	$0$	$0$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$0$

加算器をご存じの方にとっては当たり前ではありますが、繰り上がりは論理積、和は排他的論理和と同じ結果になります。繰り上がりは次の位、つまり $2$ 倍されて足されることを考えると、以下のような等式が成り立つはずです。

a + b = 2{\left(a \wedge b\right)} + {\left(a \oplus b\right)}

これを $a \oplus b$ について解くと以下の式を得られます。

a \oplus b = {\left(a + b\right)} - 2{\left(a \wedge b\right)}

さらに、ビット演算は当然以下の式を満たすべきです²。

a \oplus b = {\left(a \vee b\right)} - {\left(a \wedge b\right)}

これを $a \vee b$ について解くと以下の式を得られます。

\begin{aligned}
a \vee b &= {\left(a \oplus b\right)} + {\left(a \wedge b\right)} \\
&= {\left[{\left(a + b\right)} - 2{\left(a \wedge b\right)}\right]} + {\left(a \wedge b\right)} \\
&= {\left(a + b\right)} - {\left(a \wedge b\right)}
\end{aligned}

よってどちらもビット単位の論理積さえ定義してしまえば代数的に定義できるのです。しかし、その代わりにこれらの演算がこれまで持っていた性質のうちいくつかは落ちてしまいます。たとえば $a \oplus b = a \oplus c$ から $b = c$ を導けないことから簡約不可能です(e.g. $\frac{1}{3} \wedge \frac{2}{3} = 0$ より $\frac{1}{3} \oplus \frac{2}{3} = 1$、$\frac{1}{3} \wedge \frac{4}{3} = \frac{1}{3}$ より $\frac{1}{3} \oplus \frac{4}{3} = 1$)。

実装

それでは Python の有理数クラス Fraction に対して実装をしていきます。まずこんな感じの関数を定義しておきます。スタブとして便利なのでよく書くんですよこういうの。Never は Python 3.11 で追加されたボトム型です。型チェッカの解釈は 3.6.2 で実装された NoReturn と同じなので各人の信仰によって使い分けましょう。

from __future__ import annotations

from typing import TYPE_CHECKING

if TYPE_CHECKING:
    from typing import Never


def todo() -> Never:
    raise NotImplementedError

そして次のように関数を定義していきます。論理積の実装はあとに回すとして、排他的論理和と論理和は先に示した通りです。

from __future__ import annotations

+ from fractions import Fraction
from typing import TYPE_CHECKING

if TYPE_CHECKING:
    from typing import Never
+
+
+ def _fraction_and(self: Fraction, __value: Fraction, /) -> Fraction:
+     return todo()
+
+
+ def _fraction_xor(self: Fraction, __value: Fraction, /) -> Fraction:
+     return self + __value - 2 * _fraction_and(self, __value)
+
+
+ def _fraction_or(self: Fraction, __value: Fraction, /) -> Fraction:
+     return self + __value - _fraction_and(self, __value)


def todo() -> Never:
    raise NotImplementedError

さらに Fraction に対して動的にマジックメソッドを追加しておくことで、このモジュールをインポートすると演算子として &、^、| を利用可能になります。ただし、型チェッカなどの静的 Linter にかけると動的に追加されたメソッドを認識できずそんな演算子ないぞと怒られますが。どうにかして伝えられないだろうか。

from __future__ import annotations

from fractions import Fraction
from typing import TYPE_CHECKING

if TYPE_CHECKING:
    from typing import Never


def _fraction_and(self: Fraction, __value: Fraction, /) -> Fraction:
    return todo()


def _fraction_xor(self: Fraction, __value: Fraction, /) -> Fraction:
    return self + __value - 2 * _fraction_and(self, __value)


def _fraction_or(self: Fraction, __value: Fraction, /) -> Fraction:
    return self + __value - _fraction_and(self, __value)


def todo() -> Never:
    raise NotImplementedError
+
+
+ setattr(Fraction, "__and__", _fraction_and)
+ setattr(Fraction, "__xor__", _fraction_xor)
+ setattr(Fraction, "__or__", _fraction_or)

さて、ここからビット単位の論理積を実装していきます。以下の手順で実装していきましょう。

引数を整数部と小数部に分け、整数部を int に変換しておく
小数部を有限節と循環節を示す tuple[bool, ...] に変換する
右辺と左辺で有限節同士と循環節同士の長さを揃える
それぞれ要素ごとに論理積をとる
tuple[bool, ...] のペアを Fraction に変換する
整数部のビット単位論理積と足し合わせて返す

各手順を関数にわけ、引数が満たすべき条件を表明で示したものが以下になります。

from __future__ import annotations

from fractions import Fraction
from typing import TYPE_CHECKING

if TYPE_CHECKING:
+   from collections.abc import Sequence
    from typing import Never


def _fraction_and(self: Fraction, __value: Fraction, /) -> Fraction:
-   return todo()
+   s_int, s_frac = _split_to_int_and_frac(self)
+   v_int, v_frac = _split_to_int_and_frac(__value)
+   s_finite, s_repetend = _split_to_finite_and_repetend(s_frac)
+   v_finite, v_repetend = _split_to_finite_and_repetend(v_frac)
+   s_finite, s_repetend, v_finite, v_repetend = _fix_length(
+       s_finite, s_repetend, v_finite, v_repetend
+   )
+   finite = _seq_bool_and(s_finite, v_finite)
+   repetend = _seq_bool_and(s_repetend, v_repetend)
+   frac = _unite_from_finite_and_repetend(finite, repetend)
+   return (s_int & v_int) + frac


def _fraction_xor(self: Fraction, __value: Fraction, /) -> Fraction:
    return self + __value - 2 * _fraction_and(self, __value)


def _fraction_or(self: Fraction, __value: Fraction, /) -> Fraction:
    return self + __value - _fraction_and(self, __value)
+
+
+ def _split_to_int_and_frac(a: Fraction) -> tuple[int, Fraction]:
+     return todo()
+
+
+ def _split_to_finite_and_repetend(a: Fraction) -> tuple[
+     tuple[bool, ...],
+     tuple[bool, ...],
+ ]:
+     assert 0 <= a < 1
+     return todo()
+
+
+ def _fix_length(
+     a_finite: tuple[bool, ...],
+     a_repetend: tuple[bool, ...],
+     b_finite: tuple[bool, ...],
+     b_repetend: tuple[bool, ...],
+ ) -> tuple[
+     tuple[bool, ...],
+     tuple[bool, ...],
+     tuple[bool, ...],
+     tuple[bool, ...],
+ ]:
+     return todo()
+
+
+ def _seq_bool_and(a: Sequence[bool], b: Sequence[bool]) -> tuple[bool, ...]:
+     assert len(a) == len(b)
+     return todo()
+
+
+ def _unite_from_finite_and_repetend(
+     finite: tuple[bool, ...], repetend: tuple[bool, ...]
+ ) -> Fraction:
+     assert any(not bit for bit in repetend)
+     return todo()


def todo() -> Never:
    raise NotImplementedError


setattr(Fraction, "__and__", _fraction_and)
setattr(Fraction, "__xor__", _fraction_xor)
setattr(Fraction, "__or__", _fraction_or)

この辺で各関数のテストコードも書いておきます。が、2 と 5 に関しては手作業で有理数を小数展開してテストケース作るとかやってらんないので、ごく簡単なケース以外は分解再構築して元の有理数に戻ることを確認しておけばいいでしょう。偶然対合するバグを埋め込むとかいう奇跡が起きなければどっかで落ちるはずです。~~そしてそれでも 3 のテストケースは地獄。0 と 1で書いて Excel で自動変換した。~~ ここでテストを実行してみると NotImplementedError で真っ赤っ赤です。これが Red ちゃんですか³。

整数部と小数部の分割

_split_to_int_and_frac を実装します。これについては Fraction に __floor__ が実装されているのでそれを使うのが簡単です。

from __future__ import annotations

from fractions import Fraction
+ from math import floor
from typing import TYPE_CHECKING

if TYPE_CHECKING:
    from collections.abc import Sequence
    from typing import Never

# snip

def _split_to_int_and_frac(a: Fraction) -> tuple[int, Fraction]:
-   todo()
+   i = floor(a)
+   return i, a - i

# snip

有限節と循環節の分割

_split_to_finite_and_repetend を実装します。~~おそらくこの記事で一番重く、かつ、まだしも有用な部分だと思います。~~

対象の有理数を $\frac{a}{b}$ とします。前節で真分数になっているので、$a < b$ です。なお、$a = 0$ の場合もあり得るので、その場合はアーリーリターンしておきます。以下では $a \ne 0$ であることを前提に記述します。

# snip

def _split_to_finite_and_repetend(a: Fraction) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
]:
    assert 0 <= a < 1
+
+   if not a.numerator:
+       return (), (False,)
+
    return todo()

# snip

$\frac{a}{b}$ の $n$ 進数での小数展開は

$na$ を $b$ で整除し、商が次の桁となる
その余りを新たな $a$ とする

という手順を繰り返していくことで実現できます。この手順 1 回を「1 歩」と呼ぶことにします。

有限小数であれば余りが $0$ となり、循環小数ならどこかで同じ余りが出るはずです。後者のケースでどこから循環が始まり、循環節がどれだけの長さがあるかを知るための方法を考えます。ナイーブな方法は 1 歩 1 歩で商と余りを記録して同じ余りが登場するかを毎回走査する方法があるでしょう。

今回は「うさぎとかめのアルゴリズム」とも呼ばれるフロイドの循環検出法を使ってみます。

アルゴリズムの簡単な手順は以下の通りです。「うさぎ」と「かめ」の二つの「ポインタ」⁴を用意します。

ステップ 1 (下準備および有限小数の検出)

このステップでは「うさぎ」は 2 歩一気に進み、「かめ」は 1 歩ずつ進みます。有限小数の検出のため、「かめ」は各歩数での商を記録します。

もしも「かめ」側の余りが $0$ になれば、そこで割り切れる有限小数ということになるので、「かめ」の記録と~~空タプル~~ (False,) を返却できます。

循環小数の場合は循環している部分の中で後ろから「うさぎ」が「かめ」に追いつきます。ここでステップ 1 を終了します。「かめ」の記録は残念ながら一旦破棄します。

# snip

def _split_to_finite_and_repetend(a: Fraction) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
]:
    assert 0 <= a < 1

    if not a.numerator:
        return (), (False,)
+
+   # step 1
+   finite: list[bool] = []
+   hare = a.numerator
+   tortoise = a.numerator
+   while True:
+       hare *= 2
+       hare %= a.denominator
+       hare *= 2
+       hare %= a.denominator
+       tortoise *= 2
+       q, tortoise = divmod(tortoise, a.denominator)
+       finite.append(bool(q))
+       if not tortoise:
+           return tuple(finite), (False,)
+       if hare == tortoise:
+           finite.clear()
+           break

    return todo()

# snip

ステップ 2 (有限節の算出)

ステップ 2 の開始時に「うさぎ」をスタート時点に戻します。このとき余りが当初の分子と一致する場合、つまりすでにスタート地点の場合は後述する終了条件がすでに満たされていることになり、有限節はないということになるのでそのままステップ 3 に進みます。

ステップ 2 では「うさぎ」は 1 歩ずつ進みます。「うさぎ」は有限節の記録者であり、各歩数での商を記録します。

「うさぎ」が歩を進めていくと、ちょうど循環節の開始位置で「かめ」と遭遇します。ここでステップ 2 は終了となり有限節が明らかになります。

# snip

def _split_to_finite_and_repetend(a: Fraction) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
]:
    assert 0 <= a < 1

    if not a.numerator:
        return (), (False,)

    # step 1
    finite: list[bool] = []
    hare = a.numerator
    tortoise = a.numerator
    while True:
        hare *= 2
        hare %= a.denominator
        hare *= 2
        hare %= a.denominator
        tortoise *= 2
        q, tortoise = divmod(tortoise, a.denominator)
        finite.append(bool(q))
        if not tortoise:
            return tuple(finite), (False,)
        if hare == tortoise:
            finite.clear()
            break
+
+   # step 2
+   if hare != a.numerator:
+       hare = a.numerator
+       while True:
+           hare *= 2
+           q, hare = divmod(hare, a.denominator)
+           finite.append(bool(q))
+           tortoise *= 2
+           tortoise %= a.denominator
+           if hare == tortoise:
+               break

    return todo()

# snip

ステップ 3 (循環節の算出)

ステップ 3 では「うさぎ」は再び 2 歩ずつ進みます。記録者は「かめ」に移り、循環節として各歩数での商を記録します。

「うさぎ」が循環節を 2 周、「かめ」が循環節を 1 周して再び両者が出会います。ここで循環節が明らかになります。

# snip

def _split_to_finite_and_repetend(a: Fraction) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
]:
    assert 0 <= a < 1

    if not a.numerator:
        return (), (False,)

    # step 1
    finite: list[bool] = []
    hare = a.numerator
    tortoise = a.numerator
    while True:
        hare *= 2
        hare %= a.denominator
        hare *= 2
        hare %= a.denominator
        tortoise *= 2
        q, tortoise = divmod(tortoise, a.denominator)
        finite.append(bool(q))
        if not tortoise:
            return tuple(finite), (False,)
        if hare == tortoise:
            finite.clear()
            break

    # step 2
    if hare != a.numerator:
        hare = a.numerator
        while True:
            hare *= 2
            q, hare = divmod(hare, a.denominator)
            finite.append(bool(q))
            tortoise *= 2
            tortoise %= a.denominator
            if hare == tortoise:
                break

-   return todo()
+   # step 3
+   repetend: list[bool] = []
+   while True:
+       hare *= 2
+       hare %= a.denominator
+       hare *= 2
+       hare %= a.denominator
+       tortoise *= 2
+       q, tortoise = divmod(tortoise, a.denominator)
+       repetend.append(bool(q))
+       if hare == tortoise:
+           break
+
+   return tuple(finite), tuple(repetend)

# snip

右辺と左辺の有限節、循環節同士の長さを揃える

_fix_length を実装します。

説明のために $0$ と $1$ しか数字を使えないのは厳しいので十進数で説明します。$0.123\dot{4}567\dot{8}$ という循環小数を考えます。有限節と循環節は本来最も短くなるように表現しなければいけませんが、たとえば有限節を 2 桁多く取ってそのぶん循環節をずらした、$0.12345\dot{6}784\dot{5}$ という循環小数を考えると、これは元の数と同じように循環するはずです。また、循環節を 3 回繰り返した形を取って、$0.123\dot{4}5678456784567\dot{8}$ という循環小数を考えると、これも当然元の数と同じように循環するはずです。

これを元に、

有限節を左辺と右辺の長い方に揃え、その分循環節をずらす
循環節を左辺の長さと右辺の長さの最小公倍数になるように繰り返す

という風にして実装することができます。

その前に有限小数は $\dot{0}$ という循環節を持つ循環小数とみなすことができます。最小公倍数を考えるときに長さが 0 であってはいけないので、置換しておきます。

削除

# snip

def _fix_length(
    a_finite: tuple[bool, ...],
    a_repetend: tuple[bool, ...],
    b_finite: tuple[bool, ...],
    b_repetend: tuple[bool, ...],
) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
]:
+   if not a_repetend:
+       a_repetend = (False,)
+   if not b_repetend:
+       b_repetend = (False,)
+
    return todo()

# snip

つづいて 1 を実装します。気持ち的には以下のようにスライスを利用して実装したいところです。

# snip

def _fix_length(
    a_finite: tuple[bool, ...],
    a_repetend: tuple[bool, ...],
    b_finite: tuple[bool, ...],
    b_repetend: tuple[bool, ...],
) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
]:
+   a_length_diff = max(len(b_finite) - len(a_finite), 0)
+   b_length_diff = max(len(a_finite) - len(b_finite), 0)
+   a_finite = a_finite + a_repetend[:a_length_diff]
+   b_finite = b_finite + b_repetend[:b_length_diff]
+   a_repetend = a_repetend[a_length_diff:] + a_repetend[:a_length_diff]
+   b_repetend = b_repetend[b_length_diff:] + b_repetend[:b_length_diff]

    return todo()

# snip

しかしこの実装には問題があります。a_length_diff > len(a_repetend) だったときにおかしくなってしまいます。ちなみに単一のインデックスを渡したときは範囲外アクセスでエラーになりますがスライスの場合はエラーになりません。バグの発見が遅れそうなよくわからない仕様です。

循環節をずらす部分は剰余を取って対処します。

# snip

def _fix_length(
    a_finite: tuple[bool, ...],
    a_repetend: tuple[bool, ...],
    b_finite: tuple[bool, ...],
    b_repetend: tuple[bool, ...],
) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
]:
    a_length_diff = max(len(b_finite) - len(a_finite), 0)
    b_length_diff = max(len(a_finite) - len(b_finite), 0)
    a_finite = a_finite + a_repetend[:a_length_diff]
    b_finite = b_finite + b_repetend[:b_length_diff]
-   a_repetend = a_repetend[a_length_diff:] + a_repetend[:a_length_diff]
-   b_repetend = b_repetend[b_length_diff:] + b_repetend[:b_length_diff]
+   a_repetend = (
+       a_repetend[a_length_diff % len(a_repetend) :]
+       + a_repetend[: a_length_diff % len(a_repetend)]
+   )
+   b_repetend = (
+       b_repetend[b_length_diff % len(b_repetend) :]
+       + b_repetend[: b_length_diff % len(b_repetend)]
+   )

    return todo()

# snip

有限節を伸ばす部分はそれに加えて整除法を使います。これで完璧です。

# snip

def _fix_length(
    a_finite: tuple[bool, ...],
    a_repetend: tuple[bool, ...],
    b_finite: tuple[bool, ...],
    b_repetend: tuple[bool, ...],
) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
]:
    a_length_diff = max(len(b_finite) - len(a_finite), 0)
    b_length_diff = max(len(a_finite) - len(b_finite), 0)
-   a_finite = a_finite + a_repetend[:a_length_diff]
-   b_finite = b_finite + b_repetend[:b_length_diff]
+   a_finite = (
+       a_finite
+       + a_repetend * (a_length_diff // len(a_repetend))
+       + a_repetend[: a_length_diff % len(a_repetend)]
+   )
+   b_finite = (
+       b_finite
+       + b_repetend * (b_length_diff // len(b_repetend))
+       + b_repetend[: b_length_diff % len(b_repetend)]
+   )
    a_repetend = (
        a_repetend[a_length_diff % len(a_repetend) :]
        + a_repetend[: a_length_diff % len(a_repetend)]
    )
    b_repetend = (
        b_repetend[b_length_diff % len(b_repetend) :]
        + b_repetend[: b_length_diff % len(b_repetend)]
    )

    return todo()

# snip

2 については math.lcm() を使って最小公倍数を求めれば簡単です。ただし使えるのは Python 3.9 からなのでそれ以前で使いたい場合は math.gcd() を使って求めた最大公約数で二数の積を割ることで求められます。~~使いたい場合も何も使い道ねえだろこんな記事。~~

from __future__ import annotations

from fractions import Fraction
- from math import floor
+ from math import floor, lcm
from typing import TYPE_CHECKING

if TYPE_CHECKING:
    from collections.abc import Sequence
    from typing import Never

# snip

def _fix_length(
    a_finite: tuple[bool, ...],
    a_repetend: tuple[bool, ...],
    b_finite: tuple[bool, ...],
    b_repetend: tuple[bool, ...],
) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
]:
    a_length_diff = max(len(b_finite) - len(a_finite), 0)
    b_length_diff = max(len(a_finite) - len(b_finite), 0)
    a_finite = (
        a_finite
        + a_repetend * (a_length_diff // len(a_repetend))
        + a_repetend[: a_length_diff % len(a_repetend)]
    )
    b_finite = (
        b_finite
        + b_repetend * (b_length_diff // len(b_repetend))
        + b_repetend[: b_length_diff % len(b_repetend)]
    )
    a_repetend = (
        a_repetend[a_length_diff % len(a_repetend) :]
        + a_repetend[: a_length_diff % len(a_repetend)]
    )
    b_repetend = (
        b_repetend[b_length_diff % len(b_repetend) :]
        + b_repetend[: b_length_diff % len(b_repetend)]
    )
+
+   lcm_ab = lcm(len(a_repetend), len(b_repetend))
+   a_times = lcm_ab // len(a_repetend)
+   b_times = lcm_ab // len(b_repetend)
+   a_repetend = a_repetend * a_times
+   b_repetend = b_repetend * b_times

    return todo()

# snip

それと、本来は必要ないようにこの後の関数を組めるはずですが個人的なこだわりのため循環節が $\dot{0}$ になっている場合を有限小数に戻しておきます。これは両方が有限小数だった場合にのみ起こるはずです。

削除

# snip

def _fix_length(
    a_finite: tuple[bool, ...],
    a_repetend: tuple[bool, ...],
    b_finite: tuple[bool, ...],
    b_repetend: tuple[bool, ...],
) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
]:
    if not a_repetend:
        a_repetend = (False,)
    if not b_repetend:
        b_repetend = (False,)

    a_length_diff = max(len(b_finite) - len(a_finite), 0)
    b_length_diff = max(len(a_finite) - len(b_finite), 0)
    a_finite = (
        a_finite
        + a_repetend * (a_length_diff // len(a_repetend))
        + a_repetend[: a_length_diff % len(a_repetend)]
    )
    b_finite = (
        b_finite
        + b_repetend * (b_length_diff // len(b_repetend))
        + b_repetend[: b_length_diff % len(b_repetend)]
    )
    a_repetend = (
        a_repetend[a_length_diff % len(a_repetend) :]
        + a_repetend[: a_length_diff % len(a_repetend)]
    )
    b_repetend = (
        b_repetend[b_length_diff % len(b_repetend) :]
        + b_repetend[: b_length_diff % len(b_repetend)]
    )

    lcm_ab = lcm(len(a_repetend), len(b_repetend))
    a_times = lcm_ab // len(a_repetend)
    b_times = lcm_ab // len(b_repetend)
    a_repetend = a_repetend * a_times
    b_repetend = b_repetend * b_times
+   if a_repetend == (False,):
+       a_repetend = ()
+   if b_repetend == (False,):
+       b_repetend = ()

-   return todo()
+   return a_finite, a_repetend, b_finite, b_repetend

# snip

最後にこれらの値を返して実装完了です。

# snip

def _fix_length(
    a_finite: tuple[bool, ...],
    a_repetend: tuple[bool, ...],
    b_finite: tuple[bool, ...],
    b_repetend: tuple[bool, ...],
) -> tuple[
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
    tuple[bool, ...],
]:
    a_length_diff = max(len(b_finite) - len(a_finite), 0)
    b_length_diff = max(len(a_finite) - len(b_finite), 0)
    a_finite = (
        a_finite
        + a_repetend * (a_length_diff // len(a_repetend))
        + a_repetend[: a_length_diff % len(a_repetend)]
    )
    b_finite = (
        b_finite
        + b_repetend * (b_length_diff // len(b_repetend))
        + b_repetend[: b_length_diff % len(b_repetend)]
    )
    a_repetend = (
        a_repetend[a_length_diff % len(a_repetend) :]
        + a_repetend[: a_length_diff % len(a_repetend)]
    )
    b_repetend = (
        b_repetend[b_length_diff % len(b_repetend) :]
        + b_repetend[: b_length_diff % len(b_repetend)]
    )

    lcm_ab = lcm(len(a_repetend), len(b_repetend))
    a_times = lcm_ab // len(a_repetend)
    b_times = lcm_ab // len(b_repetend)
    a_repetend = a_repetend * a_times
    b_repetend = b_repetend * b_times

-   return todo()
+   return a_finite, a_repetend, b_finite, b_repetend

# snip

要素ごとの論理積を取る

_seq_bool_and を実装します。これは zip と内包表記を使えば簡単です。

# snip

def _seq_bool_and(a: Sequence[bool], b: Sequence[bool]) -> tuple[bool, ...]:
    assert len(a) == len(b)
-   return todo()
+   return tuple(a_bit and b_bit for a_bit, b_bit in zip(a, b))

# snip

有限節と循環節の対から有理数に復元する

_unite_from_finite_and_repetend を実装します。

循環小数を分数形式に直すという課題は学校でも取り上げられています。有名なのは定数倍することで循環節同士を「打ち消し合う」方式です。

$n$ 進数で一般化して考えてみます。求めるべき有理数を $a$ と置き、有限節の桁数を $d_f$、循環節の桁数を $d_r$ とします。再び十進数の例として $a = 0.123\dot{4}567\dot{8}$ を考えます。まず、有限節の桁数分ずらした $n^{d_f}a = 123.\dot{4}567\dot{8}$ は、有限節の部分だけが小数点よりも上にきます。さらに、有限節と循環節の桁数を合わせた分ずらした $n^{d_f + d_r}a = 12345678.\dot{4}567\dot{8}$ は、有限節と循環節 1 回分の部分だけが小数点よりも上に来ます。後者から前者を引くと小数点以下の循環節同士が「打ち消し合」い、${\left(n^{d_f + d_r} - n^{d_f}\right)}a = 12344555$ と自然数になります。あとは両辺を $n^{d_f + d_r} - n^{d_f}$ で割ってやれば分数形式がわかるというわけです。

では実装していきましょう。ヘルパー関数として tuple[bool, ...] を int に変換する _seq_bool_to_int を定義しておき、テストケースも書いておきます。

# snip

def _unite_from_finite_and_repetend(
    finite: tuple[bool, ...], repetend: tuple[bool, ...]
) -> Fraction:
    assert len(repetend) == 0 or any(not bit for bit in repetend)
    return todo()
+
+
+ def _seq_bool_to_int(a: Sequence[bool]) -> int:
+     result = 0
+    for bit in a:
+        result *= 2
+        result += 1 if bit else 0
+    return result


def todo() -> Never:
    raise NotImplementedError

# snip

あとはこれを用いて実装していきます。小数点以下の部分は最終的に「打ち消」されるので書く必要はありません。~~注意点として、 len(repetend) == 0 のとき、つまり有限小数の場合はこのままではゼロ除算になってしまうため場合分けが必要です。~~

# snip

def _unite_from_finite_and_repetend(
    finite: tuple[bool, ...], repetend: tuple[bool, ...]
) -> Fraction:
    assert len(repetend) == 0 or any(not bit for bit in repetend)
-   return todo()
+
+   numerator = _seq_bool_to_int(finite + repetend) - _seq_bool_to_int(finite)
+   denominator = 2 ** (len(finite) + len(repetend)) - 2 ** len(finite)
+   return Fraction(numerator, denominator)

# snip

これですべての実装が完了しました。テストをすべて通過することを確認して終了です。

問題を解いてみる

これにより、最初に上げたコードゴルフの問題は、以下のように愚直に書いたコードで同じ出力となることを確かめられます。

from __future__ import annotations

from fractions import Fraction

import fracbit  # type: ignore[unUsedImport]

while True:
    try:
        lhs_str, op_str, rhs_str = input().strip().split(" ")
        lhs = Fraction(lhs_str)
        rhs = Fraction(rhs_str)
        match op_str:
            case "+":
                print(lhs + rhs)
            case "-":
                print(lhs - rhs)
            case "&":
                print(lhs & rhs)
            case "^":
                print(lhs ^ rhs)
            case "|":
                print(lhs | rhs)
            case _:
                assert False
    except EOFError:
        break

ただし、あくまでも元の問題はコードゴルフであり、こんな大量のコードはお門違いです。+、-、&、^、| という 5 個の演算子しか登場しないこと、単位分数しか登場しないことなどから簡略化できるのでしょう。実際提出コード例を見るとなんでこれで解けてんのかわからないような HENTAI コードがたくさん出てきます。コードゴルファーこわちかよらんとこ。

今回書いたコード

ちなみにそんな日はない。 ↩
論理積で 1 となる桁は当然論理和でも 1 となるため、繰り下がりは起こらないので引き算で書ける。 ↩
本来テスト駆動開発はテストの追加とコーディング、リファクタリングを何度も繰り返す開発方式であり、今回のように最初に全部のテストを書いてしまうのは TDD ではない。ジョークの一つとして受け取ってもらいたい。 ↩
ここでいうポインタとは単に抽象的な「位置」を指示するものの意味であり、通常の変数。 ↩