More than 3 years have passed since last update.

「フゥーハハハ! これが運命石の扉の選択か……

 これより、オペレーション・GCDを開始する!!」

前回、C++11で黒魔術的NTZとNLZを実装する話をやりました。今回はその続きです。

まあ、続きと言っても、NTZを使えばこういうことができるよ! ってだけなのですが。


SteinのGCDアルゴリズム

タイトルと冒頭で謎のシュタゲネタをぶち込みましたが、今回実装するのは「バイナリGCDアルゴリズム」とか「Steinのアルゴリズム」と呼ばれるアルゴリズムです。

Steinというのは別に運命石ではなくて、人名です。Josef Steinさんという方が発見した最小公倍数アルゴリズムらしいです。

前回と同じくネタ元のブログ記事を紹介します。

sh-2の日記: 最大公約数を求める2つのアルゴリズムを書いてみた

前回のNTZ/NLZと比較するとそれほど黒魔術的ではありません。

考え方はこうです。


  • ユークリッドの互除法は美しいが最速ではない。

  • なぜ速くないか→剰余が遅いから

  • なら剰余をを使わなければいい

  • 剰余の代わりに全部シフト演算にできたら速くなるんじゃね?

上記のブログ記事では非常に素直な実装を行っていますが、私のような狂気のマッドC++erはこう考えます。


  • ループ回してシフト演算してる所、NTZに置き換えられるんじゃね?

  • C++11らしくconstexprにしたいよね。再帰しかないな!

やってみました。


gcd_stein.hpp

#include <ntz_nlz.hpp>


// std::minがconstexprじゃないのが悪い
template<typename T> inline constexpr T min(T x, T y) noexcept { return x<y?x:y; }

template<typename T>
struct gcd_stein_
{
using result_type = decltype(std::declval<T>()%std::declval<T>());
static inline constexpr result_type func1(T x, T y, int n, int m) noexcept {
return func2(x>>n, y>>m) << min(n, m);
}
static inline constexpr result_type func2(T x, T y) noexcept {
return x==y? x: (x>y ? func2(func3(x-y),y) : func2(func3(y-x),x));
}
static inline constexpr result_type func3(T x) noexcept { return x >> ntz(x); }
};

template<typename T>
inline constexpr typename gcd_stein_<T>::result_type gcd_stein(T x, T y) noexcept {
return gcd_stein_<T>::func1(x, y, ntz(x), ntz(y));
}


意外と短い。そして元記事のサンプルコードが影も形もない。

なお、ここで実装したGCDは、x, yのどちらかが0以下であった場合を考慮していません。あくまで正の2つの整数の最大公約数を求める関数であることをご了承ください。

それでは、短いですが本日はここまで。