メタ関数の再帰停止の方法についての質問です.

質問

メタ関数の再帰停止の方法についての質問です.
最大公倍数を求めるメタ関数を作ろうとして引数をintに固定したものはすぐ作れたのですが
引数を任意の整数にしたものを作ろうとしたところ,いろいろな方法を試みましたがどれもだめで結局以下のようにしました.
template<typename IntegerT, IntegerT Rhs, IntegerT Lhs>
struct gcd;
template<int Rhs, int Lhs>
struct gcd<int, Rhs, Lhs>
{
typedef int integer_type;
typedef gcd<integer_type, Rhs, Lhs> type;
typedef integer_type value_type;
static const value_type value =
gcd<integer_type, Lhs, Rhs % Lhs>::type::value;
};
template<int Rhs>
struct gcd<int, Rhs, 0>
{
typedef int integer_type;
typedef gcd<integer_type, Rhs, 0> type;
typedef integer_type value_type;
static const value_type value = Rhs > 0 ? Rhs : -Rhs;
};
template<long long Rhs, long long Lhs>
struct gcd<long long, Rhs, Lhs>
{
typedef long long integer_type;
typedef gcd<integer_type, Rhs, Lhs> type;
typedef integer_type value_type;
static const value_type value =
gcd<integer_type, Lhs, Rhs % Lhs>::type::value;
};
template<long long Rhs>
struct gcd<long long, Rhs, 0ll>
{
typedef long long integer_type;
typedef gcd<integer_type, Rhs, 0ll> type;
typedef integer_type value_type;
static const value_type value = Rhs > 0ll ? Rhs : -Rhs;
};
しかし,この方法だと考えられる整数全てに対して特殊化を定義せねばならず何のためにテンプレートを使っているのかわかりません.
テンプレートのインスタンス化の順序を考えてみるとコンパイル時に再帰を停止するための条件が普通に考えたものとは異なるように思うのですが,どのようにすればもっと簡単に一般の整数型(short,long等)に対してメタ関数を定義できるでしょうか?

回答No.5

Tacosan

とりあえず「多倍長整数」は「渡せたとしてもコンパイル時に計算できないから無意味」な気がします. 「整数のラッパ」は渡せるけど, 結局のところ「最も長い整数」で計算しちゃえば問題にならないと思いますよ.
メタ関数として定義するなら
template <typename Int, Int Lhs, Int Rhs> struct gcd;
template <long long Lhs, long long Rhs> struct gcd<long long, Lhs, Rhs> {
// それなりに
};
template <long long Lhs> struct gcd<long long, Lhs, 0LL> {
// それなりに
};
template <typename Int, Int Lhs, Int Rhs> struct gcd {
typedef Int value_type;
static const value_type value = gcd<long long, Lhs, Rhs>::value;
};
という形で, 一度 long long として計算してから適切な型にキャストしなおせばいいと思う.
あと, 次の C++ では constexpr が導入されるので
template <typename Int>
constexpr Int gcd(Int Lhs, Int Rhs)
{
return (Lhs < 0) ? gcd(Rhs, -Lhs) : (Rhs < 0) ? gcd(Lhs, -Rhs) : (Rhs == 0) ? Lhs : gcd(Rhs, Lhs % Rhs);
}
のような感じになるかと. ただ, 型の問題は難しいなぁ. 卑怯だけど
template <typename IntA, typename IntB>
constexpr auto gcd(IntA Lhs, IntB Rhs) -> decltype(Lhs+Rhs)...
のようにする?

回答No.4

麻野 なぎ（@AsanoNagi）

No.3 です。

> 作りたかったのはコンパイル時に最大公倍数を計算するものでした.

そういう意図でしたか。なるほど。やっとわかりました。

Ｃ＋＋のテンプレートは、引数に合わせた関数を（演算子も含めて）呼び出すだけなので、それは困難かと思います（少なくとも、私にはできません）
そして、関数呼び出しが絡むので、普通に書いただけではコンパイル時に計算してくれるほどの最適化も期待できません。

これだけでは何なので、boost の gcd がわざわざテンプレートになっているのは、多倍長整数のようなものを想定しているからです。
これとは別に、rational （有理数）クラスがあって、これが、内部的に分数表現を用いたクラスになっています。

gcd は、約分のために、このクラスから頻繁に呼び出されるわけですが、分母分子とも64bit幅とかではなく、多倍長（もしくは、任意精度）整数が使用可能な構成になっています。

失礼しました。

お礼

私はコンパイラの挙動等わからないことがいっぱいあるのでうまく説明できないところがあり,ご迷惑をおかけしたかも知れません.ただインスタンス化の順序で追っかけて考えたときの挙動とは異なる挙動をしているように思い,そこが良くわからないのでメタ関数を作ろうとすると試行錯誤的な作り方になってしまい先を見通すことがうまくできないでいます.
有理数の通分と似たことになりますが,実数の整数化に最大公倍数を利用しようと思っていたのでご紹介のBoostの関数が使えそうです(自分で作ったものよりそちらをつかったほうが良いでしょう)いろいろとお教えいただきどうもありがとうございます.
メタ関数を作るときの考え方については引き続き教えていただけるとありがたいです.

回答No.3

麻野 なぎ（@AsanoNagi）

失礼しました。再帰ですね。

こんなのでは（Boost のほとんど丸写し）
再帰呼び出しの際の引数の型を確定する必要があるので、いちいち、同じ型の変数で一度受けるのがミソ。

#include <iostream>

// Greatest common divisor for rings (including unsigned integers)
template < typename RingType >
RingType
gcd_euclidean
(
RingType a,
RingType b
)
{
// Avoid repeated construction
#ifndef __BORLANDC__
RingType const zero = static_cast<RingType>( 0 );
#else
RingType zero = static_cast<RingType>( 0 );
#endif

RingType c;

if ( a == zero )
return b;
else
{
c = a % b;
return gcd_euclidean(c, b);
}
}

int main()
{
unsigned short a = 1001;
unsigned short b = 13;

std::cout << gcd_euclidean(a, b) << "\n";
return 0;
}

補足

Boostにあるというのは知りませんでした.
わざわざ作ることは無いですね.
実は実行時関数版は別に作りました(車輪の再発明でしたが)
作りたかったのはコンパイル時に最大公倍数を計算するものでした.
私がよく理解していないところがあるかも知れませんが,このようにした場合
引数に定数を与えても実際の計算がなされるのが実行時ではないかと思いましたので
それとは別にメタ関数版を作ろうとしたわけです.
本当は引数が定数の関数は全てコンパイル時に計算して定数に置き換えるという最適化
をしてくれるなら良いわけですがそこが良くわかりませんでした.
でも私の作ったのは関数オブジェクトで関数ではありません.
関数オブジェクトだと使用時にインスタンスが必要なので実行時にしか計算できないと思うのですが,関数だと引数が定数のときコンパイル時に結果の定数に置き換えてくれるとかいうことはあるのでしょうか?

回答No.2

麻野 なぎ（@AsanoNagi）

たとえば、Boost というライブラリの中には、汎用的な整数型に対応した gcd() があります。

http://www.boost.org/doc/libs/1_44_0/boost/math/common_factor_rt.hpp

にあるヘッダの、
namespace detail
の中の、
gcd_euclidean()
がその実体です。

このソースの中でも、
RingType zero = static_cast<RingType>( 0 );
のように、あらかじめゼロを定義して使っていたりしますが。

これをそのまま使って、

#include <iostream>

// Greatest common divisor for rings (including unsigned integers)
template < typename RingType >
RingType
gcd_euclidean
(
RingType a,
RingType b
)
{
// Avoid repeated construction
#ifndef __BORLANDC__
RingType const zero = static_cast<RingType>( 0 );
#else
RingType zero = static_cast<RingType>( 0 );
#endif

// Reduce by GCD-remainder property [GCD(a,b) == GCD(b,a MOD b)]
while ( true )
{
if ( a == zero )
return b;
b %= a;

if ( b == zero )
return a;
a %= b;
}
}

int a;
double b = 0.11;

int main()
{
unsigned short a = 1001;
unsigned short b = 13;

std::cout << gcd_euclidean(a, b) << "\n";
return 0;
}

だけでも、ちゃんと動作することがわかります。
このあたり、少しずつ確認してみるというのは、どうでしょう。

ちなみに C++ のテンプレートは、引数の型から適切な型を判断してくれますから、実行時に型を指定する必然性はないです。
（Boost のものも、実行時には、gcd_euclidean(1001, 13) だけですね）

回答No.1

Tacosan

gcd の引数をどうするか (型を明示するかどうか) という問題はありますが, 型を含めて 3引数にするなら long long だけ特殊化すればいいんじゃないかなぁ?
「long long より大きい型」を見なくていいなら, それ以外は「long long で計算してから適切にキャスト」すればいいだけだし.

お礼

まだ最終解決には至っていないですが考えてみるとあなたの示唆なさったようにlong longに対して定義しておけばとりあえず他の型について定義しなくてもよいわけです.
なので取りあえずはそのように対応することにしました.
ご教唆いただきどうもありがとうございます.

補足

メタ関数については最近使い始めたばかりでよく理解できていないのですが
たとえば型として多倍長整数とか整数のラッパーのようなクラスを使うことは
できるのでしょうか?
素人目にはユーザー定義の型をコンパイル時に使ってくれるのかななどと思ってしまいます.
もしそのような型に対してもメタ関数が定義できるなら,ユークリッドの互除法が
使える任意のクラスに対して最大公倍数をいっぺんで定義できて便利かなと思いました.
もっともメタ関数として最大公倍数が必要かどうか疑問ですけど.
いろいろ試してみる段階で0を型にキャストしたものでの部分特殊化でできないだろうか
と思って以下のようにやってみたことがあります.
template<typename IntegerT, IntegerT Rhs, IntegerT Lhs>
struct gcd
{ ... }
template<typename IntegerT, IntegerT Rhs>
struct gcd<IntegerT, Rhs, static_cast<IntegerT>(0)>
{ ... }
これはstatic_cast<IntegerT>(0)がテンプレートパラメータIntegerTに依存しているので
エラーとなってしまいます.
しかし,考えてみるとインスタンス化の段階でIntegerTは具体的な型(intやlong等の)が
決まっているはずなので何故できないんだろうと思ってしまいます.
このあたりのことがわからないので質問しました.