  |
 |
2008年10月7日     |
テンプレートによるメタプログラミングと数論 海外internet.com発の記事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つ注意すべきなのは、ある推論や仮定が数論によって証明されていない場合でも、実用上はそれを有効に適用できる可能性があることです。例えば、有名な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で割り切れるという関係は、 例えば、100の正の約数は次のとおりです。 1、2、4、5、10、20、25、50、100 ある数の約数を考える場合、1とその数自体は「自明な約数」と呼ばれます。上記例の100の場合、自明な約数は1と100です。 整除性には、いくつか非常に興味深い性質があります。以下に整除性の性質の一部を示します。
編集部注
一部おかしいと思われる部分を、原文から修正しています（リストの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); } }; 2.3. パリティ数を分類する最も単純な方法は、おそらく偶数と奇数に分けることでしょう。この偶数と奇数の区別（偶奇性）のことをパリティと言います。定義により、2では割り切れる数はすべて偶数、2で割りきれない数は奇数となります。例えば、2、4、100、5000はすべて偶数であり、1、3、51、277はいずれも奇数です。偶数と奇数には、同等の2進形式に変換した場合に現れる興味深い性質があります。2進形式に変換すると、その数が偶数の場合は最下位桁が必ず0になり、奇数の場合は最下位桁が必ず1になるのです。そのため、数を2進形式で表せば、その数が偶数と奇数のどちらであるかを容易に判定することができます。 4 = 1002 9 = 10012 20 = 101002 23 = 101112 2つの整数が両方とも偶数または両方とも奇数である場合、その2つの数のパリティは一致します。そうでない場合は、相反するパリティを持ちます。 以下に、数のパリティを調べるためのコードを示します。 // check number is even or not template <int u> struct IsEven { enum { value = Divisible<u, 2>::value }; }; // check number is odd or not template <int u> struct IsOdd { enum { value = Divisible<u, 2>::value == 0 ? 1 : 0 }; }; 数が持つこの単純な特性（パリティ）は、データ通信において伝送中のエラーをチェックするために活用されています。このエラーチェックを使用する場合は、データを相手方に送信する前に、偶（even）と奇（odd）のどちらのパリティを使用するかを選択し、バイト内の1ビットをこのパリティのために確保しておく必要があります。そしてビットの個数の偶奇とパリティが一致すればパリティビットを1に設定し、一致しなければ0に設定します。例えば、偶のパリティを選択した場合は、データ内のビットの個数が偶数ならばパリティビットをオンにし、奇数ならばオフにします。奇のパリティを選択した場合は、パリティビットをまったく逆に設定することになります。 データの伝送中または伝送後に、データの1つのビットがなんらかの理由で本来とは逆の状態に変化してしまった場合、受信側ではパリティビットを利用したチェックによってその誤りを検出することができます。ただし、この単純なチェックではエラーの発生を検出できるだけで、エラーを訂正することはできません。また、このチェック方法では、奇数個のビットの状態が変化した場合はエラーを検出できますが、偶数個のビットで誤りが発生した場合はエラーを検知できません。 2.4. 最大公約数の計算どちらも0ではない2つの整数aとbの最大公約数（GCD）とは、aとbの両方を割り切れる最大の整数のことです。最大公約数は「最大共通因数（HCF）」と呼ばれることもあります。uとvの最大公約数は次のように表すことができます。 k = gcd(u, v) また、次のように表すこともできます。
gcd(u, v) = max { k | k u and k v}
この式の 1つの整数が0である場合の最大公約数については、慣例的に次の式を使用します。 gcd(u, 0) = u ユークリッドのアルゴリズムは、2数の最大公約数を計算するための最古のアルゴリズムです。これは現在でも誤りなく結果を求めるために使用できる最も古いアルゴリズムの1つであると言えるかもしれません。このアルゴリズムは対象の2つの数がいずれも正の整数であることを前提としています。 負でない任意の整数uとvの最大公約数は、次の関係を再帰的に適用することによって計算できます。 gcd(u, v) = gcd(v, u mod v) // calculate gcd template <int u, int v> struct gcd { enum { value = gcd<v, u % v>::value }; }; template <int u> struct gcd<u, 0> { enum { value = u }; }; template <> struct gcd<0, 0> { enum { value = -1 }; }; 2つの整数aとbを座標とする平面上の点(a, b)と原点を直線で結ぶと、その2つの数の最大公約数は、この直線上で原点に最も近い格子点によって表されます。この格子点のx座標とy座標は、それぞれaとbをその最大公約数で割った値になります。  2.5. 最小公倍数の計算最小公倍数（LCM）とは、両方の数の倍数である（0ではない）最小の数のことです。最小公倍数は「最小公分母（LCD）」と呼ばれることもあります。 最小公倍数は次の式で定義できます。
lcm(u, v) = min { k | k > 0, u k and v k}
この式の 最大公約数（GCD）と最小公倍数（LCM）の間には次のように密接な関係があります。 gcd(u, v) * lcm(u, v) = u * v // calculate lcm template <int u, int v> struct lcm { enum { value = u * v / gcd<u, v>::value }; }; 2.6. 互いに素な数2つの数が1以外の共通因数を持たない場合、その2つの数は「互いに素である」と言います。つまり、2つの数の最大公約数が1であるならば、それらの数は互いに素であると言えます。 // check if numbers are coprime (relative prime) or not template <int u, int v> struct CoPrime { enum { value = gcd<u, v>::value == 1 ? 1 : 0 }; }; 2つの数が互いに素であるとすると、幾何学的には、その2つの数がそれぞれx座標とy座標である平面上の点と原点を直線で結んだ場合、その直線上には両端の点以外には格子点が1つも存在しません。2つの数が互いに素でないならば、その直線は途中で格子点を通過し、その中で原点に最も近い格子点によって2数の最大公約数が示されます。  2.7. 素数任意の自然数が1とその数自体の2つしか約数を持たない場合、その自然数は「素数」と呼ばれます。素数を小さいものから順番に5つ挙げると、2、3、5、7、11となります。4、6、9などのように3個以上の約数を持つ数は「合成数」と呼ばれます。「1」は約数を1つしか持たないので、素数と合成数のどちらとも見なされません。 すべての数は素数の積として表すことができます。このことに関して注意すべき重要な点は、ある数を素数の積として表す方法は1とおりしか存在しないことです。言い換えれば、ある数を素因数に分解することによって得られる素数の集合は常に一意的です。次に素因数分解の例を示します。 100 = 2 * 2 * 5 * 5 4235 = 5*7*11*11 すべての自然数を一意的に素因数分解できることは「算術の基本定理」として知られています。 // check the given number is prime or not template <int n> struct IsPrime { enum { value = NoOfDivisor<n>::value == 2 ? 1 : 0 }; }; 約数の個数を調べる 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をその自然対数で割った数にほぼ等しい」というものです。  言い換えれば、任意の大きな数を選んだ場合、その数が素数である確率は // 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個なので、  トーティエント関数の定義から、「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. 参考文献
著者紹介Zeeshan Amjad（Zeeshan Amjad）
|
Zeeshan Amjad
