miauのブログ

はてなダイアリー「miauの避難所」をはてなブログに移行しました

ユークリッドの互除法について勘違いしてた

Google Code Jam なんかでよく最大公約数を求める必要が出てきて、こんなときに使うのがユークリッドの互除法なんですが。

引き算による実装と割り算による実装があって、今まで引き算でやってたんですが、割り算のほうが効率いいみたいなのでその反省とかです。

二つの実装

Wikipedia に載っているのは

def gcj_div(m, n) {
    if (m < n) { (m, n) = [n, m] }
    if (n == 0) { return m }
    return gcj_div(n, m % n)
}

こんな感じの割り算(剰余)による実装(Groovy で書いてます)なんですが、私はいつのまにか

def gcj_sub(m, n) {
    if (m < n) { (m, n) = [n, m] }
    if (n == 0) { return m }
    return gcj_sub(n, m - n)
}

といった感じの引き算による実装を使ってしまっていました。

剰余の代わりに減算を用いる方法もあるが、両者の間に本質的な差異は何もない。

とあるように結果は同じなのですが、計算量が全然違っていて。

割り算による実装であれば Wikipedia にあるように

割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の 5 倍繰り返せば、最大公約数に達する(ラメの定理)。

くらいの計算量なんですが、引き算による実装の場合は引数に 10000000 と 10000001 が渡されたら 10000000 回くらいループしないといけないわけで。どう考えても割り算で実装したほうが効率がいいですね・・・。

なんで引き算の実装にしてしまったか(謎)

最初は私も Wikipedia か何かを見て割り算で実装した覚えがあるんですけど、数年前アルゴリズムコンテスト系の何かで引き算の実装を見かけて、試しに計算してみたら引き算のほうがやや速かったから、それ以降こちらで実装してしまっている気がします。

確かに除算の速度は ここ にあるように減算とかの 30 倍くらい遅かったりするんですが・・・演算速度の差が計算オーダーを上回るくらいに小さな数で検証してしまったか、剰余の結果が BigDecimal になって極端に速度が遅くなるような処理系で検証してしまったのか・・・今となっては謎です。

ブレントの手法?

ユークリッドの互除法 引き算」とかでググっていると見かけた手法。

上記とは別の、ビット演算&ビットシフト&引き算を使った実装があるんだとか。これ使ったら速くなるの?

と期待してちょっとググってみると・・・

CPU によって違うけど、そんなに効果はないんだとか。

Wikipedia(英語)を見ると、

「Efficiency」のところに「理屈ほど速くならないよ」みたいなことが書いてました。残念。

ちなみにブレントとかで検索してもあまりヒットしない気がします。上記の Wikipedia ページも「Binary GCD algorithm」というタイトルだし、外部リンクに Brent の名前はあるものの、冒頭の説明は「Stein のアルゴリズム」でした。

C とかで速くならないことはわかったけど、CPU 側で命令として持ったら速くなるんじゃないの?と期待して調べてみたけど、ブレントの手法は見つかりませんでした。ふつうの互除法での実装なら

に載っていたので、ブレントの手法でも実装できたり・・・しないかなぁ。