Saturday, October 23, 2010

コードの短い人

Project eulerで、他の人のコードを見ていると感心することがあります。

私がC++で30行ばかり消費していることろで、この人は10行くらいでやっているのですな。

まず、数字ばかりからなる集合の操作をしたい箇所。私はC++のsetをつかって
a.insert(x); 

として、後でaの要素をカウントしているところを、配列で
b[x] = y;

とするのです。yはゼロでない適当な数字。集合集合と思っていると頭が固くなるのかもしれないなあ。頻度のグラフを作るようなときにはこうしますからね。b[i]がゼロでないものを集めれば、これが求める集合。

もう1つ、私が
for(i=10;i>=0;i--)

とやるようなところで
for(i=10;i--;)

と言っている。これは嫌だなあ。でも短い。しかも正しい。

a[i] = b;
if (b > 0) {
r += 1;
}


と言うようなところを
r += (a[i] = b) > 0;

と言っている。これも嫌だなあ。しかし、なるほどねと感心。

「線形代数とその応用」

学生のころ、つまり20年くらい前、赤門の前の古本屋で見つけた本。工学部の学生の私としては、抽象的な説明に辟易していた線形代数が具体的で楽しかった。

誰が書いたかなんて考えたこともなかったけど、ホームページがあるのね。
http://www-math.mit.edu/~gs/

この本です。まだ売っているんだと感心。

Saturday, June 05, 2010

カオス

chaosとは数学の用語でもあって、「カオス」と書かれます。
だいたい何でも英語風に読むことが多いと思いますが、英語風にいうならば「ケイオス」ではないだろうか。
「カオス」はイタリア語ですよね。なんでここでイタリア語なのでしょうか。

Thursday, April 29, 2010

整数の割り算

話せば長いことながら、Linuxカーネルの中で、割り算がどうなっているか調べたのです。

BSDでは昔から例えばシリンダグループの計算で/だの%を使っていたので、まあ前からあったのですね。
(当時その計算のシリンダグループの計算のマクロの意味がよくわからなかった。今読んだらわかるんだろうか。)

Linuxでは(1)/や%がないのはgccがリンクしているライブラリの事情らしいのだけれど、(2)64ビットの場合と32ビットの場合で定義が違っていて、64ビットでは/や%がそのまま使われていて、32ビットではアセンブラで実装されている様子でした。(3)四則演算はCの一部じゃなくて、ライブラリなのかねという疑問もあります。
(1),(2),(3)の事情がことごとくわかりません。あとで考えましょう。

ところで、割り算がCで実装されているところがあって、それは確かにそうだな、と思ったのでメモしておきます。

n/bの割り算は本質的にはn-bの引き算の繰り返しで可能です。しかしそれでは効率が悪いのでn-2^x * bを繰り返すというのがポイントです。以下は同じやり方をpythonで書いてみたものです。以下でdが2^x * bに相当、tが2^xに当たります。


def int_division(n, b):
d = b
t = 1

while d <= n:
d <<= 1
t <<= 1
d >>= 1
t >>= 1

result = 0
remainder = n

while remainder >= b:
if remainder >= d:
remainder -= d
result += t

d >>= 1
t >>= 1

return result, remainder