CodeZine(コードジン)

特集ページ一覧

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

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

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2007/10/01 14:00

C++ではホスト言語とドメイン言語が同一のため、他の言語の構文を新たに習得する必要なしにメタプログラム(別のプログラムを生成するプログラム)を作成できます。本稿では「数論」を対象に、その適用例を紹介していきます。

目次

1. はじめに

 メタプログラミングとは、別のプログラムを生成できるプログラムを書くことです。この技法はさまざまな言語においてさまざまな目的で使用されています。メタプログラミングは、部分的な評価を行うことによって1つのプログラムを別のプログラムに変換する方法、言い換えれば、プログラミングを自動化する手段であるとも言えます[11]。メタプログラミングの典型例の1つは、出力としてプログラムを生成するLexやYACCなどのコンパイラ構築ツールです。コンパイラ自体もこのカテゴリに含めることができますが、コンパイラの場合は一般にホスト言語とドメイン言語が異なります[3]。通常、コンパイラは特定の文法に従って書かれたソースを入力として受け取り、CやC++、Javaなどのプログラムを出力します。

 C++ではテンプレートとマクロを使用してコードを作成することができます。ただし、この方法は綿密に設計された機能というよりはむしろコンパイラの乱用に近いという面が多少あります[12]。C++コンパイラは、テンプレートがインスタンス化される時点でコードを生成します。同様に、メタプログラミングの手段として多分最も古いものであるプリプロセッサも、マクロを展開してコードを生成します。C++のメタプログラムでは、プログラムのホスト言語とドメイン言語はどちらもC++であり、テンプレートがインスタンス化される時点で、C++のコンパイラによってC++のコードが生成されます。つまり、テンプレートによるメタプログラムの実行は、プログラムの実行時ではなくコンパイル時に行われます。従って、C++は2つのレベルから成る言語であるとも考えられます[6][12][15]。

 メタプログラミングについては、なぜそれを使用すべきなのかという問題があります。その最も適切な答えは、コンパイル時の最適化と言えるかもしれません[7]。メタプログラミングの技法はさまざまな領域に適用可能であり、例えば、科学アプリケーションやグラフィックアプリケーションにおいてsinやcosなどの三角関数や指数関数、対数関数の値をコンパイル時に前もって計算し、その結果をメモリに格納しておくと、実行時のオーバーヘッドを削減できます。メタプログラミングはその他にも、静的データ構造[16]、アルゴリズム[3]、デザインパターン[10][13]、リフレクション[15]、式テンプレート[2][5]などの多様な分野に適用することができます。また、C++ではホスト言語とドメイン言語が同一であり、他の言語の構文を新たに習得する必要なしにメタプログラムを書けるので、そのこともメタプログラミングを使用する理由の1つとして挙げられます[3]。

 数論も、メタプログラミングを活用して興味深い処理を実行することが可能な分野の1つです。数論は整数の性質を研究対象とする学問です[4]。数論は数学の中でおそらく最古の分野であり、「数学の女王」とも呼ばれています。整数を表すには、通常、Zという記号が使用されます。これはドイツ語で「数」を意味するZahlという単語の頭文字です。

 数学者のド・モルガンがかつて言ったように、代数と幾何は、それぞれ別々に研究されていたのが一緒に扱われるようになってから研究の進歩が加速しました。数論についても同じことが言えます。初期の数学者たちは、ある個数の点を並べるとどのような図形ができるかに基づいて、数を三角数、四角数(平方数)、五角数などのカテゴリに分類していました。また、ピタゴラスの三角形や、それに対応する「ピタゴラスの3つ組」と呼ばれる数も知られていました。これは幾何と代数のつながりを示す多くの事例の1つであり、ピタゴラスの定理としても知られています。数論の研究は幾何と代数の視点に限られたものではなく、確率論的研究、組み合わせ論的研究、解析的研究など、次に示すような、いくつもの細かい専門分野に分かれています。これらはいずれも現在、非常に活発に研究が行われている分野です。

  1. 初等数論
  2. 代数的数論
  3. 幾何的数論
  4. 確率論的数論
  5. 組み合わせ数論
  6. 解析的数論
  7. 計算数論
  8. 算術数論
  9. 加法的数論
  10. 乗法的数論
  11. 応用数論

 数論研究の真髄はさまざまな問題の見事な証明にあり、より複雑な問題は既存の証明に基づいて解決されます。1つ注意すべきなのは、ある推論や仮定が数論によって証明されていない場合でも、実用上はそれを有効に適用できる可能性があることです。例えば、有名なRSA暗号アルゴリズムは、「非常に大きな複数の素数の積である巨大な数の素因数を見つけるのは容易ではない」という仮定に基づいています。もし大きな整数の因数を容易に発見できる方法が存在するとすれば、RSAに基づくシステムのセキュリティは簡単に破られてしまいます[1][8]。

2. 初等関数

2.1. 整除性

 整数aと0でない整数bの比a/bが整数である場合、「aはbで割り切れる」と言い、bをaの「約数」または「因数」と呼びます。この場合、次の式を満たす第3の整数cが存在します。

a = b * c

 aとbがどちらも正の数であるならば、cも必ず正の数になります。aはbで割り切れるという関係は、b|aと表記することもできます。20|100は、「100は20で割り切れる」という意味です。

 例えば、100の正の約数は次のとおりです。

1、2、4、5、10、20、25、50、100

 ある数の約数を考える場合、1とその数自体は「自明な約数」と呼ばれます。上記例の100の場合、自明な約数は1と100です。

 整除性には、いくつか非常に興味深い性質があります。以下に整除性の性質の一部を示します。

  1. 反射性: x|x
  2. 推移性: x|yかつy|zならば、x|z
  3. 乗法: x|yならば、cx|cy
  4. 簡約: cx|cyならば、x|y(cが0でない場合)
  5. a|bかつa|cならば、a|(b + c)
  6. a|bかつa|cならば、a|(b - c)
  7. a|bかつa|cならば、a|(b * c)
  8. (b * c)|aならば、b|aかつc|a
  9. 1|n(すべての整数は1で割り切れる)
編集部注
 一部おかしいと思われる部分を、原文から修正しています(リストの5~7)。

 この整除性の概念は、次の例のようにC++のテンプレートクラスを使用して容易に実装できます。

// check divisibility
template <int u, int v>
struct Divisible
{
   enum { value = u % v == 0 ? 1 : 0 };
};

// check divide by zero condition
template <int u>
struct Divisible<u, 0>
{
   enum { value = -1 };
};

 uがvで割り切れるときは1が返され、割り切れないときは0が返されます。0による除算という特別な場合については、テンプレートの部分的な特殊化によって対処しています。このクラスの2番目のパラメータが0である場合(任意の数を0で割ろうとした場合)、出力は-1になります。この値はこのコンテキストではエラーを意味します。このクラスは、対象の数が割り切れるかどうかを示す1か0の2種類の出力しか持たないので、エラーを示すために-1という負のエラー番号を使用してもまったく問題はありません。

2.2. 天井値と床値の関数

 「天井値」(a ceiling value)は、与えられた数以上で最小の整数と定義されます。同様に、「床値」(a floor value)は、与えられた数以下で最大の整数と定義されます。これらの関数の入力は実数ですが、出力は整数です。

// to calculate the celing value
template <typename T>
struct Ceil
{
   static inline int value (T a)
   { return (a > 0 ? a + 1 : a ); }
};

// to calculate the floor value
template <typename T>
struct Floor
{
   static inline int value (T a)
   { return (a > 0 ? a : a - 1); }
};

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

あなたにオススメ

著者プロフィール

バックナンバー

連載:japan.internet.com翻訳記事

もっと読む

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5