2010-03-23

ごはんを炊くとき

生活

ご飯を炊く。サラダ油をちょっと足して炊き上げると、ご飯にツヤが出るらしい。やってみた。

炊けた。つやつやだ！！

でも対照比較になってないなあ。できれば二重盲検化もしたい所だけど、一人じゃ無理かな。

まあ、おまじないだと思って、これからも入れよう。

2010-03-20

最大公約数を求める2つのアルゴリズムを書いてみた

プログラミング C

Cで多倍長整数演算のプログラムを書くのに熱中していた。既存のライブラリ*1を参考にしながら、自分でコードを書いてみている。勉強になるなあ。

アルゴリズムの参考にしたのは、クヌース先生の『The Art of Computer Programming Volume 2 Seminumerical Algorithms』。バイブルの名は伊達ではないようで。どれだけの知見を持っていたらこんなものが書けるのか……読み物としても結構面白い。

ただ、まだ乗算とか面倒な部分は実装していないので、本格的に役に立つのはまだ先。Karatsuba法とかFFTを使った高速乗算法、うまく書けるかなあ。

互除法ともう一つ

ここで話が変わる。TAOCPの他の部分を読んでいたら、最大公約数を求めるアルゴリズムが載っていた。有名なユークリッドの互除法の他に、もう一つ。今ここに書き残しておかないと忘れる自信があるので、忘れる前に書いておく。

まず、ユークリッドの互除法。

int gcd_euclid(int u, int v) {
  int r;
  while (0 != v) {
    r = u % v; u = v; v = r; /* swap */
  }
  return u;
}

きれいだ。この方法は十分に簡潔で高速なように思われる。

ところが、まだあるらしい。

Euclidによる始祖的アルゴリズムは何世紀にもわたって使われてきているから、実はそれが必ずしも最大公約数を求める最良の方法ではないという事実にはかなり驚く。
主に二進の算術演算に適した全く別のアルゴリズムをJosef Steinが1961年に考案している。

これもCで書いてみた。

int gcd_stein(int u, int v) {
  int k, t;

  /* u, vどちらかが奇数になるまで2で割り続ける */
  k = 0;
  while((0 == (u & 1)) && (0 == (v & 1))) {
    k++;
    u /= 2;
    v /= 2;
  }

  if ((u & 1) == 0) {
    t = u / 2;
  } else {
    t = -v;
  }

  do {
    /* tが偶数である限り、2で割り続ける */
    while ((t & 1) == 0) t /= 2;

    if (t > 0) {
      u = t;
    } else {
      v = -t;
    }

    t = u - v;
  } while (0 != t);
  return u * (1 << k);
}

えらくゴチャゴチャしてしまった。除算が必要ないのがポイントのようだ（2で割る部分はビットシフトで置き換えることができる）。

実測

Steinの方法は、ユークリッドの互除法より高速な可能性があるらしい。さっそく実測してみなければ。

……この辺で力尽きた。徹夜つらい。パラメータや最適化オプションを色々変えて実行してみると、Steinの方法はやや遅い模様。ほとんど差はないので、環境によってはいくらでもひっくり返ると思う。

でも、これぐらいの差なら、単純なユークリッドの互除法のほうが好きだなあ。僅かでもパフォーマンスを上げたい数値計算の専門家とかであれば、こういった所も強く気にしなければならないのかもしれない。

おわり

どちらのプログラムもかなり効率はよい。しかし、Euclidの互除法ほど古くからある手続きにさえ、改良すべき点は残っている。

アルゴリズム道は深い。

*1:Google ソースコード検索で引っかかったGMPの古いやつ

2010-03-03

ここ数日の間に色々あった

生活

2chが停止。DDoSを受けたらしい

現在は復旧済み。なかなか迷惑なものだ

Opera10.5正式版発表

明らかに軽くなっている。UIもおおむね改善の方向で進んでいるようだ。フォントが若干汚いけど許容範囲。

ただアップグレードしちゃったためなのか、挙動が不安定。ページによっては読み込みがおかしかったり、ブラウザ自体がフリーズすることもある。クリーンインストールが必要かもしれない。

東方Project第12.5弾「ダブルスポイラー〜東方文花帖」発表

前代未聞の弾幕撮影ゲーム、第二弾。文花帖のシステムではカメラで弾幕の一部を消せる。これを利用して、サテライトヒマワリのようなパズル弾幕も成立していた。弾幕の可能性に注目。

ひな祭りの余波？

近くのコープでは牛肉が4割引。思わずサーロインステーキを買ってしまった。こういう機会でもないと食べられないしね。

2010-03-02

Alternative Sphere

STG

時おり、同人ゲーム「Alternative Sphere」をやっている。良作。

弾を撃って敵を倒す。STGは本質的にそれだけ。単純なルールの上に、いかにゲーム性を作り上げるかが製作者の腕の見せ所なのだろう。

その点Alternative Sphereはやってて楽しい。ザコ敵をわらわらとなぎ払いながら、撃ってくる弾を大回りに、時には小刻みに避け回る。適当にやっててもそれなりに立ち回れるが、パターンを組めばもっと奥深いのだろう。

人間の原始的な快楽に近いんじゃないかなあ。抽象化すればドッジボールとよく似ていると思う。あれもルールの根幹は「ボールを当てて・避ける」小学校低学年のスポーツ*1だった。

東方のジリジリと濃密な弾幕を避けるデザインも好きだが、こういう爽快なプレイ感覚もまた良いものだと思う。

STGは一回のプレイ時間が短い。空き時間の暇つぶしとかにはもってこい。ルールもシンプルでとっつきやすい。ジャンルとしてもう少し再評価されていいと思うんだけどな。

*1:いや偏見かもしれないけど

2010-02-23

これは気付かないわ

プログラミング Lisp メモ

Common Lispについて。CLtL2の仕様書には邦訳があったので、今ちょっとだけ読んでいる。なぜそうしたのか？なぜそうあるべきなのか？膨大な仕様記述の中に大量の解説が埋め込まれていて勉強になる。

そもそも、CLOSとかコンディションシステムとかは複雑でよくわからんので、言語自体の学習も目的の一つだったり。

ちょっと驚いたのがコレ

X3J13は1989年1月に、defconstantで定義された定義シンボルをレキシカルあるいはスペシャル変数として再束縛することはエラーであることの明確化<48>を議決した。結局defconstantで定義されたシンボルの値は常にグローバルな値を参照する。（不幸にもこれは参照透明性（referential transparency）を破壊する。つまり、まわりの文脈を考慮することなしに、レキシカル変数として使うことのできる名前を選ぶことができない。）

定数を宣言するdefconstantオペレータの仕様は、参照透明性を破壊するらしい。……なるほど言われてみれば分からなくもないが、微妙すぎる。プログラミング言語はきわどいバランスの上に成立しているようだ。

そういえば、Schemeでもcall/ccが参照透明性を崩すという話題を聞いたことがあるような。

2010-02-03

視線の流れ

プログラミング関数型言語 Haskell

プログラミング言語には、プログラマの意図をコンピュータに伝えるという大事な仕事がある。そしてもちろん、プログラマ間でもコードを読み合うわけだから、読まれるという点では自然言語と同じ意味で「言語」でもある。

どうしても気に食わない事がある

『Real World Haskell』から引っ張ってきた、ごく普通のHaskellコード

let capCount = length . filter (isUpper . head) . words

これを読むときは、どう考えてもコードを右から左へ……それどころか、右へ左へ視線をさまよわせながら読むことになると思う*1。どうしてこんな記法にしたんだろう？何か深遠な理由があるのか、他にどうしようもなかったのか。

どうしてこうなった

少し考えてみた。たぶんHaskell（とかMLとかの関数型言語）が意識しているのが数学の合成関数の記法。
$h(g(f(x))) = h \circ g \circ f (x)$
右から左だ。とはいえ今更のように、この記法を発明した数学者*2に文句を言うわけにもいかない。xにf、g、hと順番に適用してるだけなんだから、こんな記法でも良いと思うんだけどなあ
$(x).f.g.h$
……これがまさにオブジェクト指向ってことかな。オブジェクト指向は記法的にも読みやすいというメリットがあるのかもしれない。

視線の流れで何かを測定できないか

「視線移動が複雑なコードは、人間にとって複雑である」と仮定する。ソースコードの複雑さを、視線の流れの複雑さで測定できないかなあ。「視線移動の複雑さ」をどう表現するかが問題だが、ソースコードを、ソースコードだけを解析するよりは楽なはず。ソフトウェアメトリクスとかの分野で絶対にやってる人がいると思うんだけど。

*1:まあHaskellに慣れれば違うのかもしれないが

*2:誰だろう？ライプニッツさんとかになるの？

2010-01-30

C++にも手を出す

プログラミング C++

C++は外見からして使う気が起きなかったのだけれど、それじゃあただの食わず嫌いっぽくもあったので独習してみることにした。

とりあえず二冊。

C++に対する現在の印象

言語的には「化け物」というほかない。プログラムとして望ましい性質とは、信頼性であったりパフォーマンスであったり柔軟性であったり、様々なのだろう。C++は巨大な言語仕様を提供することで、あらゆる状況において最適の選択肢をプログラマに提供できるように設計されていると感じる。

ただし、おかげでバッドノウハウの塊になっている。言い換えると、言語が提供する大量の選択肢から正しいものを的確に組み合わせねばならない。それに失敗したら容易に破綻したコードが生まれる。Effectiveシリーズを熟読しないと、使いこなすどころか危険な気がする。

こりゃ当分は怖くて使えない。ないしは、比較的安全っぽい部分だけを慎重に使おう。まあ使う予定はそもそもないのだけれど。