📐

Elixirで拡張ユークリッドの互除法

2022/12/23に公開1件

Elixir

tech

本記事は Elixir Advent Calender 12の8日目の記事です。

拡張ユークリッドの互除法というアルゴリズムがあります。

ユークリッドの互除法という２つの数字のGCD(最大公約数)を求めるアルゴリズムを拡張し、次のような1次方程式の解を求めることができるアルゴリズムです。

ax + bx = gcd(a, b)

Elixirでの拡張ユークリッドの互除法

では実際にElixirで実装してみましょう！と言いたいところですが、実はElixirにはIntegerモジュールにすでに実装されていたりします。
(1.12から入ったようです)

試しに実行してみましょう

# 240と162の最大公約数は6
iex> gcd = Integer.gcd(240, 162)
6
iex> {^gcd, x, y} = Integer.extended_gcd(240, 162)
{6, -2, 3}
iex> 240 * x + 162 * y == gcd
true

ちゃんと解けていそうですね！

実装を見てみると次のようなシンプルな実装です

  @spec extended_gcd(integer, integer) :: {non_neg_integer, integer, integer}
  def extended_gcd(0, 0), do: {0, 0, 0}
  def extended_gcd(0, b), do: {b, 0, 1}
  def extended_gcd(a, 0), do: {a, 1, 0}

  def extended_gcd(integer1, integer2) when is_integer(integer1) and is_integer(integer2) do
    extended_gcd(integer2, integer1, 0, 1, 1, 0)
  end

  defp extended_gcd(r1, r0, s1, s0, t1, t0) do
    div = div(r0, r1)

    case r0 - div * r1 do
      0 when r1 > 0 -> {r1, s1, t1}
      0 when r1 < 0 -> {-r1, -s1, -t1}
      r2 -> extended_gcd(r2, r1, s0 - div * s1, s1, t0 - div * t1, t1)
    end
  end

0 when r1 > 0 0 when r1 < 0 はガード節をうまく使って、正負の場合分けをしているようです。
値に固定値を書いてガード節で場合分けを表すというのは目から鱗でした。

実装の中身の解説はこちらの記事がわかりやすかったです。
(言語はC++ですが、実装方法はおそらく同じだと思います)

Rangeモジュールでの`Integer.extended_gcd/2`の活用

Elixirのコードを見ていたら面白いところで、この Integer.extended_gcd/2が使われていることに気づきました。
RangeモジュールのRange.disjoint?/2の実装の中でInteger.extended_gcd/2が使われています。

  def disjoint?(first1..last1//step1 = range1, first2..last2//step2 = range2) do
    if size(range1) == 0 or size(range2) == 0 do
      true
    else
      {first1, last1, step1} = normalize(first1, last1, step1)
      {first2, last2, step2} = normalize(first2, last2, step2)

      cond do
        last2 < first1 or last1 < first2 ->
          true

        abs(step1) == 1 and abs(step2) == 1 ->
          false

        true ->
          # We need to find the first intersection of two arithmetic
          # progressions and see if they belong within the ranges
          # https://math.stackexchange.com/questions/1656120/formula-to-find-the-first-intersection-of-two-arithmetic-progressions
          {gcd, u, v} = Integer.extended_gcd(-step1, step2)

          if rem(first2 - first1, gcd) == 0 do
            c = first1 - first2 + step2 - step1
            t1 = -c / step2 * u
            t2 = -c / step1 * v
            t = max(floor(t1) + 1, floor(t2) + 1)
            x = div(c * u + t * step2, gcd) - 1
            y = div(c * v + t * step1, gcd) - 1

            x < 0 or first1 + x * step1 > last1 or
              y < 0 or first2 + y * step2 > last2
          else
            true
          end
      end
    end

Range.disjoint?/2は２つのRangeが重なっていないかどうかを判定する関数ですが、この中でInteger.extended_gcd/2 を使っているようです。
重なっているかどうかの判定は単純に終わりと始まりを比べればいいだけでは？と思ったのですが、Rangeにはstepを指定することができるので、話はそう簡単ではないようです。

Integer.extended_gcd/2自体がこちらのPRで追加されたものなので、どうやらRangeがstepをサポートするにあたって必要になったので実装されたみたいですね✨

まとめ

今回はElixirで実装されていた拡張ユークリッドの互除法の紹介をしました。
競技プログラミングでしか需要がないのでは？と思っていたら、意外なところで必要になって実装されていたのが興味深かったです！

Discussion

zacky1972

とても興味深かったです！

Elixirでの拡張ユークリッドの互除法

RangeモジュールでのInteger.extended_gcd/2の活用

まとめ

Discussion

Rangeモジュールでの`Integer.extended_gcd/2`の活用