No (refractory) title : spectrally stable

本、アニメ、映画の感想。時々まじめに物理。ごくたまに日記。

その数式、プログラムできますか? を読んだ

巷ではコーディングテストの類が人気を博し、様々なテスト対策が実しやかに囁かれている昨今、しかしアルゴリズムだけを勉強するというのには何故か興が乗らず、どうしたもんかなぁ、と思っていたらこんな本を見つけた。

原題``From Mathematics to Generic Programming''、 著者はあの有名なC++STLに関わった例のStepanovさんと、Appleなどで活躍されたDaniel E. Roseさん。原題に to generic programming と書いてあるけれども、そこまでテンプレートテクニックの話をするわけではない。数学的抽象化とその概念を有するgeneric programming について、昔から知られているアルゴリズムとそれにまつわる数学の話、そこから派生する数学的抽象化とそのプログラムへの表現、最適化について、思想面、歴史面から紹介する。章末問題や例題、コーディングの例も付録され、手を動かしてアルゴリズムの実装と原理を学べる。

本書はA9.comにて行われたStapanovの講座の内容を一冊にまとめたもので、内容が導入から深化していく過程はまさに講義、という感じで引き込まれた。自分としては歴史的な経緯と数学の話が混ざって紹介されるところ、数学的抽象化とそのアルゴリズムとしての実装、拡張、最適化ということが、思想的に連続性をもって繋がっていることが語られていて、面白かった。数学に関する深い知識と、それらがアルゴリズムという形でプログラムに関連していく内容は、「プログラムを通して偉大な数学的抽象化に触れいている」という感覚を読み手に沸き立たせるようで、読んでいてわくわくした。

ぶっちゃけ、プログラムの世界で代数学が使われていること、公理論や圏論が使われていることは知っていたけれども、物理数学に毒された自分は「幾何学こそが世界の記述言語であり至高。代数学は人間の言葉でしかない」とか思っていました。しかしこの本を読むと、抽象化された概念がアルゴリズムを介してプログラムとして実現され、今や人類の文化活動になくてはならないものとなったことを考えると、「いやあなどれねぇ」って気持ちになりました。反省します。

この本は面白かったのだけれども、ただ、講義形式だからこそかアルゴリズムについてはそれほどたくさん書いているわけでもないので、「たくさんのアルゴリズムの実装と理解を経て強くなりたい!」って人にはお勧めできない。ある種の啓蒙書、思想書として読むと「ふぇぇ、おもしろぉ」ってなる、と思う。

何度も読んで理解していきたい、という気持ちになった。

以下雑感とメモ。

第1章はいわば序章で、本書の内容の目的、概観と読み方について説明している。

第2章、「アーメスによるアルゴリズム」或いは「エジプト乗法 (Egyptian multiplication)」或いは「ロシア農民のアルゴリズム (Russian Peasant Algorithm)」について。位取り記法なんてものがない時、そして足し算だけで何とか大きな乗算を計算したい時、さてどうする?方法としては2の累乗で掛け算を実行する2の累乗を行うことで、例えば4倍の計算はそのままやると4回足す必要があるけれども、2倍を2回足す (2倍を作るのに1回足し算 + 2倍同士の足し算1回) と考えると2回で済む、という話。ここで奇数を判定するには、1との論理積を取ればよい (そりゃそうだ、ビットの末尾は1を足すかどうかなので、奇数かどうかはここだけで決まる。1は一桁目以外はすべて0なので、論理積を取れば一桁目の0,1のみで結果が決まる)。右シフトは一桁目の情報が落ちるので、結果的に7だったら3が出てくる。これで大体、任意の乗数はO(log(n))で計算できる。とのこと。情弱なので、実装の再起呼び出しは使ったことがなく、へーと勉強になった。for で書いてしまうけど、再起呼び出しって使うメリットがあるんかな (実装の簡潔さ以外に)。

第3章は、有名なエラトステネスの篩とピタゴラス(学派)の話。面白かったのは、エラトステネスの篩で計算を進めると、必然的にある素数の篩は、自身の次は自身の2乗になるって話(当たり前ではあるんだけれども)。

第4章はユークリッドの互除法。その昔紀元前300年頃、ファラオがパトロンになってムセイオンという研究所で学者を飼っていたのかぁ。そのうちの一人がユークリッド。コラム面白い。3世紀ごろ中国の劉徽(りゅうき)は円周率が3よりも大きいことを証明したそうな。ただし彼の九章算術という数学本の注釈を書いた業績の一部。この九章算術、調べてみるとガウスの消去法がすでに載っていたとか。すごい。0と位取り記数法って紀元前1500年にもすでにバビロニアで使われてたんだ。え、全然知らなかったのだけれど、ビットシフトって実装されてないアーキテクチャってあるの?要調べ。

第5章は15世紀末から始まる近代数論で、第6章には合同演算と群論、そこから圏論の話が簡単に紹介される。ちょっと雑多な感じがするけれども、ここで言いたいのは数学の抽象化がアルゴリズムの一般化の思想につながっている、と言いたいのかも。圏論の話は言語仕様の話に少しだけ関わっている。

導入の流れが面白い。ここでのフェルマーの小定理の話は次の合同演算の話の導入に、そして合同演算はそれによって出来る群をもとにその小定理がより簡単に導かれると同時に、この群論の抽象化が圏論になる。ものすごい導入だ。[tex:{ \displaystyle 2n-1 }]であらわされる素数は257以下においてすべてわかっているそうな。これをメルセンヌ素数と呼ぶ。最大はn=257の時。これが1644年頃に見つかっている。フェルマーの小定理って面白い。{ \displaystyle a^{p-1} -1 }素数pで割り切れるっていう話。面白い。

第7章ではアルゴリズムを演算を満たすいかなる型においても可能なように一般化するという話。第8章では環や体と言った群以外のその他の代数構造の話とかする。第9章では数学を数学する話。ペアのの公理とか。第8章から第9章は数学一般の話に行って、あまりプログラムの話はしない。

飛んで第12章のGCDの拡張は、それまでの伏線もあって面白かった。