固定小数点乗除算

雑談

おとといのa24zに固定小数点とかの話。乗除算。


固定小数点で、加減算はまあいいだろう。多分。そのまんまだ。
けど、乗除算はどうしようか、と、少し迷ったのである。


と、思ったけど、背景事情を書くの面倒になったので略。よーするに、上のほうのビットが潰れるって話。32bitレジスタで、10bit左シフトしてる場合は、整数部分は実質12bitしか使えない、とかそういう感じ。


で、それはそういう話なんだが、32bit同士の積は、64bitあれば十分なので、大体のCPUには、32x32=64bit乗算というのが付いている。たとえば、x86の場合だと、積の上位32bitがedxに、下位32bitがeaxに入る、といった感じだ。なんとなく、そういう計算ができるのに、上位ビットをみすみす潰してしまうというのはもったいない。


そこで、long longな型の乗算をして、そっからシフトすればコンパイラがうまくやってくれるんじゃないか、と思って、

int mul64(int x, int y)
{
  long long z = x*y;
  return z>>10;
}

こんな感じにしてみたら、

	movl	12(%ebp), %eax
	imull	8(%ebp), %eax
	cltd
	shrdl	$10, %edx, %eax
	sarl	$10, %edx

大体こんな感じになった。最後のが無駄っぽいけど、あんまり問題無いようだ。（ちなみに、shrdというのは、32ビットレジスタふたつの64bitをシフトする、という命令らしい）
ちなみにARMでもSHでも問題無かった。


で、乗算はいいとして、除算だ。とりあえず、おとといのa24zでは、同じような考えかたで

int div64( int x, int y )
{
  long long xl = x;
  return (xl<<10)/y;
}

大体こんな感じでやってた。（今見直したら間違ってたけど…）
けど、これをコンパイルしたらわかるのだけど、ちょっとあんまりなコードになる。普通のCPUは、64bit/32bit除算なんてできないので、多分、32bit値で64bit除算をエミュレーションするライブラリ呼び出しが入るはずだ。
で、なんとかならんかと思って、トライ&エラーやら、「除算は剰余が一緒に出るはずだから、剰余をうまく使えばいけるはず」とか、そんなわけのわからない直感やらをたよりに、

#define FIX_SHIFT 10
int fixdiv( int x, int y )
{
  int q = x/y;
  int r = x%y;
  int rq = (r<<FIX_SHIFT)/y;

  return (q<<FIX_SHIFT)+rq;
}

こんな感じでやってみた。大体良い値が出るようだ。多分。
ただし、除算が二回になる。


あと、FIX_FLOATという名前はおかしいと思った。直しとこう。