c++boost.gif (8819 bytes) Greatest Common Divisor
Least Common Multiple

<boost/math/common_factor.hpp> にあるクラステンプレート、関数テンプレートは、2つの整数の最大公約数(GCD)と最小公倍数(LCM)の実行時、 及びコンパイル時における評価を提供する。これらの機能は多くの数学指向のジェネリックプログラミングの問題に対して有用である。

Contents

Header <boost/math/common_factor.hpp>

このヘッダは単に <boost/math/common_factor_ct.hpp><boost/math/common_factor_rt.hpp> をインクルードしているのみである。以前はコードを含んでいたが、 コンパイル時及び実行時の機能が(これらは独立していたので)別々のヘッダに移されたため、このヘッダは互換性のために維持されている。

Synopsis

namespace boost
{
namespace math
{

template < typename IntegerType >
class gcd_evaluator;
template < typename IntegerType >
class lcm_evaluator;

template < typename IntegerType >
IntegerType gcd( IntegerType const &a, IntegerType const &b );
template < typename IntegerType >
IntegerType lcm( IntegerType const &a, IntegerType const &b );

template < unsigned long Value1, unsigned long Value2 >
struct static_gcd;
template < unsigned long Value1, unsigned long Value2 >
struct static_lcm;

}
}

Header <boost/math/common_factor_rt.hpp>

GCD Function Object

template < typename IntegerType >
class boost::math::gcd_evaluator
{
public:
// Types
typedef IntegerType result_type;
typedef IntegerType first_argument_type;
typedef IntegerType second_argument_type;

// Function object interface
result_type operator ()( first_argument_type const &a,
second_argument_type const &b ) const;
};

boost::math::gcd_evaluatorクラステンプレートは2つの整数の最大公約数を返す関数オブジェクトクラステンプレートを定義している。 テンプレートはここでIntegerTypeと呼ばれている単純な型によってパラメタ化される。この型は整数を表現する数値型でなければならない。 たとえどちらかの引数が負であっても、関数オブジェクトが返す値はつねに非負である。

この関数オブジェクトクラステンプレートは対応する GCD function template で使用されている。もしある数値型の最大公約数の評価方法をカスタマイズしたいならば、gcd_evaluatorクラステンプレートをその型で特殊化すること。

LCM Function Object

template < typename IntegerType >
class boost::math::lcm_evaluator
{
public:
// Types
typedef IntegerType result_type;
typedef IntegerType first_argument_type;
typedef IntegerType second_argument_type;

// Function object interface
result_type operator ()( first_argument_type const &a,
second_argument_type const &b ) const;
};

boost::math::lcm_evaluatorクラステンプレートは2つの整数の最小公倍数を返す関数オブジェクトクラステンプレートを定義している。 テンプレートはここでIntegerTypeと呼ばれている単純な型によってパラメタ化される。この型は整数を表現する数値型でなければならない。 たとえどちらかの引数が負であっても、関数オブジェクトが返す値はつねに非負である。 もし最小公倍数が整数型の範囲を超える場合、その結果は未定義である。

この関数オブジェクトクラステンプレートは対応する LCM function template で使用されている。もしある数値型の最小公倍数の評価方法をカスタマイズしたいならば、lcm_evaluatorクラステンプレートをその型で特殊化すること。

Run-time GCD & LCM Determination

template < typename IntegerType >
IntegerType boost::math::gcd( IntegerType const &a, IntegerType const &b );

template < typename IntegerType >
IntegerType boost::math::lcm( IntegerType const &a, IntegerType const &b );

boost::math::gcd関数テンプレートは渡された2つの整数の(非負の)最大公約数を返す。boost::math::lcm関数テンプレートは 渡された2つの整数の(非負の)最小公倍数を返す。この関数テンプレートは引数のIntegerTypeによりパラメタ化される。 また返り値の型も同様である。内部的には、これらの関数テンプレートは対応する gcd_evaluatorlcm_evaluator クラステンプレートのオブジェクトを使用する。

Header <boost/math/common_factor_ct.hpp>

template < unsigned long Value1, unsigned long Value2 >
struct boost::math::static_gcd
{
static unsigned long const value = implementation_defined;
};

template < unsigned long Value1, unsigned long Value2 >
struct boost::math::static_lcm
{
static unsigned long const value = implementation_defined;
};

boost::math::static_gcdとboost::math::static_lcmクラステンプレートは2つのunsigned long型の値ベースの引数を取り、 同じ型の静的定数データメンバvalueを1つ持つ。メンバのvalueはテンプレートの引数の最大公約数か最小公倍数である。 最小公倍数がunsigned longの範囲を超える場合にはコンパイルエラーが起こるだろう。

Example

#include <boost/math/common_factor.hpp>
#include <algorithm>
#include <iterator>


int main()
{
using std::cout;
using std::endl;

cout << "The GCD and LCM of 6 and 15 are "
<< boost::math::gcd(6, 15) << " and "
<< boost::math::lcm(6, 15) << ", respectively."
<< endl;

cout << "The GCD and LCM of 8 and 9 are "
<< boost::math::static_gcd<8, 9>::value
<< " and "
<< boost::math::static_lcm<8, 9>::value
<< ", respectively." << endl;

int a[] = { 4, 5, 6 }, b[] = { 7, 8, 9 }, c[3];
std::transform( a, a + 3, b, c, boost::math::gcd_evaluator<int>() );
std::copy( c, c + 3, std::ostream_iterator<int>(cout, " ") );
}

Demonstration Program

プログラム common_factor_test.cpp は実行時のGCDとLCM関数テンプレート、およびコンパイル時のGCDとLCMクラステンプレートのいくつかの例を 実体化した結果のデモンストレーションである。 (実行時のGCDとLCMクラステンプレートは実行時関数テンプレートを通して間接的にテストされる。)

Rationale

最大公約数と最小公倍数はいくつかの他のBoostライブラリを含むいくつかの数学のコンテキストでよく使われる。 これらの関数を1つのヘッダにまとめることはコードの局所化を促進し、メンテナンスを容易にする。

History

2 Jul 2002
コンパイル時と実行時の項目を新しいヘッダに分割した。
7 Nov 2001
初版

Credits

GCDとLCMの計算のBoost compilation の作者は Daryle Walker である。このコードは Paul Moorerational ライブラリとSteve Clearyの pool ライブラリに潜在していたコードに喚起されたものだ。コードはHelmut Zeiselによって更新されている。


Revised July 2, 2002

© Copyright Daryle Walker 2001-2002. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.