整数の対数

整数の平方根を求めるアルゴリズムは奥村先生の本やHacker's Delightで紹介されているけど、整数の対数を求めるアルゴリズムはないようだ。

いや、log2(x)やlog10(x)を求めるのはあるんだけど、使いたいのは1024*log2(x)とかのあらかじめスケーリングされた値。固定小数点形式で得たいというべきか。ちなみにNewton法は遅くて使い物にならなそうだった。

ちょっと考えてみたんだけど、(1<<K)*log2(x)についてはlog2(x)をベースにしてrange coder風の求め方でいけるんじゃないかなと思ってこんなのを作ってみた。

#define K 7

/**
 * (1<<K)*log2(x)を求める。
 * xは0≦x＜(1<<16)を満たす必要がある。
 */
unsigned ilog(unsigned x)
{
 int i;
 unsigned r, th, tl, tm;

 /* log2(x)の整数部分を得る  */
 for(i = 31; i > 0; --i) {
  if(x >= (1u << i)) {
   r = i;
   break;
  }
 }
 if(i == 0) return 0;

 /* range coderを使ってlog2(x)の小数点以下の桁をKビット決定する  */
 th = 0x10000;
 tl = 0x8000;
 x = x << (15 - r);
 for(i = 0; i < K; i++) {
  tm = isqrt(th * tl);
  if(x >= tm) {
   r = (r << 1) | 1;
   tl = tm;
  } else {
   r = r << 1;
   th = tm;
  }
 }
 return r;
}

intが32ビット(以上)のマシン用。どうでしょう?