はいちょっと今緊急で記事書いてるんですけども。
本来この記事は来年か再来年の国際ビット演算デー1のために温めていたネタなのですが、とある事情で急いで形にしています。
この記事ではビット単位の論理積、排他的論理和、論理和の演算子にそれぞれ $\wedge$、$\oplus$、$\vee$ を使用します。
先に狂われたら立つ瀬がない
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)}
さらに、ビット演算は当然以下の式を満たすべきです2。
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 len(repetend) == 0 or 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 ちゃんですか3。
整数部と小数部の分割
_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 (), ()
+
return todo()
# snip
$\frac{a}{b}$ の $n$ 進数での小数展開は
- $na$ を $b$ で整除し、商が次の桁となる
- その余りを新たな $a$ とする
という手順を繰り返していくことで実現できます。この手順 1 回を「1 歩」と呼ぶことにします。
有限小数であれば余りが $0$ となり、循環小数ならどこかで同じ余りが出るはずです。後者のケースでどこから循環が始まり、循環節がどれだけの長さがあるかを知るための方法を考えます。ナイーブな方法は 1 歩 1 歩で商と余りを記録して同じ余りが登場するかを毎回走査する方法があるでしょう。
今回は「うさぎとかめのアルゴリズム」とも呼ばれるフロイドの循環検出法を使ってみます。
アルゴリズムの簡単な手順は以下の通りです。「うさぎ」と「かめ」の二つの「ポインタ」4を用意します。
ステップ 1 (下準備および有限小数の検出)
このステップでは「うさぎ」は 2 歩一気に進み、「かめ」は 1 歩ずつ進みます。有限小数の検出のため、「かめ」は各歩数での商を記録します。
もしも「かめ」側の余りが $0$ になれば、そこで割り切れる有限小数ということになるので、「かめ」の記録と空タプルを返却できます。
循環小数の場合は循環している部分の中で後ろから「うさぎ」が「かめ」に追いつきます。ここでステップ 1 を終了します。「かめ」の記録は残念ながら一旦破棄します。
# snip
def _split_to_finite_and_repetend(a: Fraction) -> tuple[
tuple[bool, ...],
tuple[bool, ...],
]:
assert 0 <= a < 1
if not a.numerator:
return (), ()
+
+ # 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), ()
+ if hare == tortoise:
+ 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 (), ()
# 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), ()
if hare == tortoise:
break
+
+ # step 2
+ finite.clear()
+ 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 (), ()
# 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), ()
if hare == tortoise:
break
# step 2
finite.clear()
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, ...],
]:
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]
+ 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, ...],
]:
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]
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, ...],
]:
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]
- 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, ...],
]:
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
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
要素ごとの論理積を取る
_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()
+
+ if repetend:
+ numerator = _seq_bool_to_int(
+ finite + repetend,
+ ) - _seq_bool_to_int(
+ finite,
+ )
+ denominator = 2 ** (len(finite) + len(repetend)) - 2 ** len(finite)
+ else:
+ numerator = _seq_bool_to_int(finite)
+ denominator = 2 ** len(finite)
+ return Fraction(numerator, denominator)
# snip
これですべての実装が完了しました。テストをすべて通過することを確認して終了です。
問題を解いてみる
これにより、最初に上げたコードゴルフの問題は、以下のように愚直に書いたコードで同じ出力となることを確かめられます。
from __future__ import annotations
from fractions import Fraction
from operator import add, and_, or_, sub, xor
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 "+":
op = add
case "-":
op = sub
case "&":
op = and_
case "^":
op = xor
case "|":
op = or_
case _:
assert False
print(op(lhs, rhs))
except EOFError:
break
ただし、あくまでも元の問題はコードゴルフであり、こんな大量のコードはお門違いです。+、-、&、^、| という 5 個の演算子しか登場しないこと、単位分数しか登場しないことなどから簡略化できるのでしょう。実際提出コード例を見るとなんでこれで解けてんのかわからないような HENTAI コードがたくさん出てきます。コードゴルファーこわちかよらんとこ。
今回書いたコード