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

No comments: