互いに素である 2 つの自然数を効率的に列挙する方法について、2 通りのアルゴリズムを紹介する。
Stern-Brocot tree を使い列挙する
この木がどんなものであるかは、Wikipedia を読むのが一番手っ取り早い。 とはいっても、英語版にはそのもののページがあるが、日本語版には無いようだ。しかし、ファレイ数列のページでこの木について触れられているので、そこのリンクを貼っておく。
ユークリッドの互除法を逆算する要領で列挙する
最大公約数を求める際にユークリッドの互除法が使われるが、それを逆の手順で計算する事によっても、互いに素である組を網羅する事が出来る。つまり、
である事を利用し、
C++ と Scheme による実装
まずは C++ で書いたものから。
そして Scheme で書いたもの。
2 つのアルゴリズムの違い
まず 1 つ目に、再帰関数に渡さなければならない引数の数が違う。引数の数が違えば、再帰呼び出しにおけるスタックの消費量が違い、また push/pop の要不要によって処理速度も変わってくる。その為、Stern-Brocot tree によるものは、ユークリッドの互除法を逆の手順にしたものよりも、メモリを食い速度も若干遅くなる。
2 つ目に、特定の区間にある既約分数を列挙出来るかどうかといった差異がある。Stern-Brocot tree を用いたものでは、enum_coprimes_with_stern_brocot_tree(N, 0, 1, 1, 1)
として、enum_coprimes_with_stern_brocot_tree(N, 1, 3, 1, 2)
とすれば良い。これは他の区間でも同様である。
ちょっとした応用
これまで、互いに素となる a,b の組、つまり
こうしてやれば、互いに素である a,b の組を生成する都度 n を掛けるより、若干効率が良い。
0 件のコメント:
コメントを投稿