japan.internet.com翻訳記事

テンプレートによるメタプログラミングと数論

テンプレートとマクロによるC++のメタプログラミング

Zeeshan Amjad[著] / japan.internet.com[訳]

2007/10/01 14:00

ポスト

3. いくつかの数論関数

3.1. 因数の個数

　すべての正の整数は1つ以上の正の因数を持っており、1以外の整数には少なくとも2つの因数（1とその数自体）があります。例えば、「12」には1、2、3、4、6、12の6つの因数があります。正の整数nの因数の個数は算術関数t(n)として定義できます。この関数を数式で表すと次のようになります。

　メタプログラミングでは、次のようにテンプレートの部分的な特殊化を使用してループ処理をエミュレートすることにより、与えられた数が持つ因数の個数を計算できます。

// loop for total no of divisors
template <int Start, int End>
struct NumDivisorsLoop
{
   enum { value = Divisible<End, Start>::value +
          NumDivisorsLoop<Start + 1, End>::value };
};

// partial specialization to terminate loop
template <int End>
struct NumDivisorsLoop<End, End>
{
   enum { value = 1 };
};

// number of divisor of any digit
template <int n>
struct NoOfDivisor
{
   enum { value = NumDivisorsLoop<1, n>::value };
};

　ここで、既存のルーチンを適用できる興味深い問題を1つ解いてみましょう。次の問題は『Programming Challenges』[14]の7.6.1に掲載されているものです（この問題はオンラインでも公開されています[9]）。

　私たちの大学には電灯の点灯/消灯係の「mabu」という男がいて、廊下の電灯のオン/オフを担当しています。すべての電灯には1つずつ専用のトグルスイッチがあります。つまり、電灯が消えている状態でスイッチを1回押すと明かりがつき、もう1回押すと消えた状態に戻ります。電力を節約するために（あるいはもともと変わり者なのかもしれませんが）彼は奇妙な方法で作業を進めます。廊下に'n'個の電灯がある場合、彼はその廊下を'n'回往復します。そして、各電灯には手前から奥に向かって電灯1、電灯2というように順番に番号が付いていると考え、i回目に奥に向かって進むときには、iで割り切れる番号を持つ電灯のスイッチのみを切り替えます。逆に廊下の奥から最初の位置に戻るときにはスイッチにはまったく手を触れません。奇妙な規則に従ってスイッチを操作しながら廊下の奥に向かって進み、最後の電灯のところで引き返して元の位置まで戻ってきたら、その時点でi回目の往復が完了します。

　この場合、一番奥の電灯は最終的にはどのような状態になるでしょうか？電灯はついているでしょうか、それとも消えているでしょうか？ この問題を解く方法の1つとして、実際にスイッチを操作しながら電灯の列を電灯の個数と同じ回数だけ往復する作業をシミュレートすることを思いつくかもしれません。この方法は1つの解法として有効ではありますが、答えが出るまでに時間がかかりすぎ、しかも、その時間は電灯の個数が増えるにつれてますます延びていきます。この問題を少し深く考えてみると、i回目の往復時にスイッチが押されるのは番号がiの倍数の電灯だけであることに気付くでしょう。逆に考えれば、スイッチkが押されるのは、iがkの因数である場合のみと言えます。例えば、6番目のスイッチが押されるのは1回目、2回目、3回目、6回目の往復時だけであり、1、2、3、6はいずれも6の因数です。初期状態ではすべての電灯が消えているので、ある数の因数の個数が奇数ならば、その番号の電灯は最終的についている状態となり、因数の個数が偶数ならば消えている状態となります。このように、任意の電灯の最終状態は、それ以外の電灯の状態の推移を一切調べなくても計算できるので、それを判定するコードを書くことはそれほど難しくありません。

   cout << IsOdd< NoOfDivisor <3>::value>::value  << endl;
   cout << IsOdd< NoOfDivisor <25>::value>::value << endl;
   cout << IsOdd< NoOfDivisor <47>::value>::value << endl;

3.2. 約数の総和（シグマ関数）

　シグマ関数は、約数の個数を示す関数に類似しており、与えられた数の約数の個数の代わりに約数の総和を示す点だけが異なります。シグマ関数を数式で表すと次のようになります。

// loop for sum of divisor
template <int Start, int End>
struct SumOfDivisorLoop
{
   enum { value = divisibleDigit<End, Start>::value +
          SumOfDivisorLoop<Start + 1, End>::value };
};

template <int End>
struct SumOfDivisorLoop<End, End>
{
   enum { value = divisibleDigit<End, End>::value };
};

3.3. 約数関数

　約数関数はシグマ関数の一般形です。言い換えれば、シグマ関数は約数関数の特別な場合です。約数関数は、与えられた数nの正の約数のx乗の総和として定義されます。約数関数を数式で表すと次のようになります。

　xの値が1の場合、約数関数はシグマ関数になります。またxが0の場合は、与えられた数の約数の個数を示す関数となります。

// to calculate the power
template <nt a, int b>
struct Power
{
   enum { value = a*Power<a, b-1>::value };
};

template <int a>
struct Power<a, 0>
{
   enum { value = 1 };
};

// loop for divisor function
template <int Start, int End, int x>
struct DivisorLoop
{
   enum { value = (Divisible<End, Start>::value == 1
          ? Power<Start, x>::value : 0) +
          DivisorLoop<Start+1, End, x>::value };
};

template <int End, int x>
struct DivisorLoop<End, End, x>
{
   enum { value = Power<End, x>::value };
};

// to calculate divisor function
template <int n, int x>
struct Divisor
{
   enum { value = DivisorLoop<1, n, x>::value };
};

3.4. パイ関数

　この関数は、「素数の個数」関数とも呼ばれます。この関数は、与えられた数以下の素数の個数を示します。数論の最も重要な定理の1つである「素数定理」は、このパイ関数と関係があります。素数定理の内容は「Nが十分に大きな数であるとき、パイ関数の値は、Nをその自然対数で割った数にほぼ等しい」というものです。

　言い換えれば、任意の大きな数を選んだ場合、その数が素数である確率は1/ln(n)ということになります。

// pi function
template <int n>
struct PiFunc
{
   enum { value = IsPrime<n>::value + PiFunc<n-1>::value };
};

template <>
struct PiFunc<2>
{
   enum { value = 1 };
};

3.5. トーティエント関数

　トーティエント関数（「ファイ関数」や「オイラーのトーティエント関数」とも呼ばれます）は、「与えられた数より小さく、かつその数と互いに素である自然数の個数」と定義されます。例えば、9より小さくて9と互いに素な自然数は1、2、4、5、7、8の6個なので、phi(9) = 6となります。また、11は素数であり、11より小さい自然数はすべて11と互いに素であるため、phi(11) = 10です。トーティエント関数を数式で表すと次のようになります。

　トーティエント関数の定義から、「p」が素数ならば次の式が成り立ちます。

　これは、ある素数より小さい自然数はすべてその素数と互いに素であるからです。トーティエント関数は素数と強い関係があり、実際、次のように素数の積の形で表すこともできます。

// helper template loop for calculate totient function
template <int Start, int End>
struct TotientLoop
{
   enum { value = CoPrime<Start, End>::value +
          TotientLoop<Start + 1, End>::value };
};

template <int End>
struct TotientLoop<End, End>
{
   enum { value = 0 };
};

// totient function
template <int n>
struct Totient
{
   enum { value = TotientLoop<1, n>::value };
};

template <>
struct Totient<1>
{
   enum { value = 1 };
};

template <>
struct Totient<0>
{
   enum { value = 1 };
};

　トーティエント関数は暗号への応用において非常に重要な意味を持っており、RSA公開鍵暗号アルゴリズムで使用されています[1][8]。RSAアルゴリズムはトーティエント関数の次のような性質に基づいています。次のように、pとqはどちらも素数で、nはpとqの積であるとします。

　この場合、次の関係が成り立ちます。

　また、オイラーのトーティエント定理により、aとnの2つの数が互いに素であれば、次の式が成り立ちます。

4. 参考文献

A Method for Obtaining Digital Signatures and Public Key Cryptosystems. R.L Rivest, A. Shamir, L. Adleman. Communication of the ACM, February 1978.
"C++ Templates: The Complete Guide." David Vandevoorde, Nicolai Josuttis. Addison Wesley, 2002.
"C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Beyond." David Abrahams, Aleksey Gurtovoy. Addison Wesley, 2004.
"Concrete Mathematics 2nd edition." Ronald L. Graham, Donald E Knuth, Oren Patashnik. Addison Wesley, 1994.
"Expression Templates." Veldhuizen, T. L. "C++ Report," 1995.
"Generative Programming bo?=. Methods, Tools and Applications." K. Czamecki, U.W. Eisenacker. Addison Wesley, 2000.
"Impact of Economics on Compiler Optimization." Arch D. Robison. Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande
"Introduction to Algorithms, Second edition." Thomas H. Cormen, Charles E. Lieserson, Ronald L. Rivest, Clifford Stein. MIT Press, 2001.
Light, more Light. http://online-judge.uva.es/p/v101/10110.html
"Making Patterns Explicit with Meta-programming." Daniel von Dincklage. Proceedings of the second international conference on Generative programming and component engineering, 2003.
"Meta-programming and Free Availability of Sources." Francois-Rene Rideau. http://fare.tunes.org/articles/ll99/mpfas.html
"Meta-Programming in C++." Johannes Koskinen, 2004. http://www.cs.tut.fi/~kk/webstuff/MetaprogrammingCpp.pdf
"Modern C++ Design: Generic Programming and Design Patterns Applied." Andrei Alexandrescu. Addison Wesley, 2001.
"Programming Challenges: The Programming Contest Training Manual." Steven S. Skiena, Miguel A. Revilla. Springer Science+Business, 2003.
"Reflection Support by means of template Meta-programming." Guiseppe Attardi, Antonio Cisternino. http://lcgapp.cern.ch/project/architecture/ReflectionPaper.pdf
"Static Data Structure: Reconciling Template Meta-programming and Generic Programming." Michael C. Burton, William G. Griswold, Andrew D. McCulloch, Gray A. Huber. http://www.cs.ucsd.edu/~wgg/Statements/mburton-ifip-gw-07-2002.pdf

この記事は参考になりましたか？

連載通知を行うには会員登録(無料)が必要です。
既に会員の方はを行ってください。

印刷用を表示

ポスト

japan.internet.com翻訳記事連載記事一覧: 式ツリーからラムダ式を構築する

Microsoft Visual Studio 2010の紹介

分散DBMS「Mnesia」の並列処理

もっと読む

この記事の著者: japan.internet.com（ジャパンインターネットコム）

japan.internet.com は、1999年9月にオープンした、日本初のネットビジネス専門ニュースサイト。月間2億以上のページビューを誇る米国 Jupitermedia Corporation (Nasdaq: JUPM) のニュースサイト internet.com や EarthWeb.com からの最新記事を日本語に翻訳して掲載するとともに、日本独自のネットビジネス関連記事やレポートを配信。

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この著者の最近の執筆記事; Zeeshan Amjad（Zeeshan Amjad）

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この著者の最近の執筆記事