2^x と log2(x) の高速な近似計算

C言語のfloat型のバイナリ表現形式に着目すると、2^x と log2(x) の近似値を高速に計算できます。

float型のバイナリ表現形式

float型は32ビットで、仮数部が23ビット(ケチ表現)、指数部が8ビット、MSBが符号ビットです。

このように上位ビットが指数を表してることを利用します。

2^xの計算

実質、足し算1回で計算できます。
(ここでは検証のために浮動小数点⇒固定小数点の換算をしています。)

  // y = 2^x (x=-10～10)
  for (float x = -10.0; x <= 10.0; x += 0.25)
  {
    // xの固定小数点表現 (小数部23ビット)
    int32_t fxp_x = x * (float)(1 << 23);
    
    // 整数部に127をオフセット(float型の指数部の仕様のため)
    int32_t tmp = fxp_x + (127 << 23);
    // float型として解釈すれば概ね 2^x の値となる
    float y = *(float*)&tmp;

    printf("%f, %f\n", x, y);
  }

縦軸を対数軸でプロットすると概ね直線になります。

f:id:licheng:20210203200620p:plain

拡大すると細部が周期的に少し歪んでいます。これはfloat型の下位23ビットは指数表現ではないためです。

f:id:licheng:20210203200634p:plain

log2(x)の計算

実質、引き算1回で計算できます。
(ここでは検証のために固定小数点⇒浮動小数点の換算をしています。)

  // y = log2(x) (x=0.001 ～ 1000)
  for (float x = 0.001; x <= 1000; x *= 1.1)
  {
    // int32_t型として解釈
    int32_t tmp = *(int32_t*)&x;
    // 指数部に-127をオフセット(float型の指数部の仕様のため)
    // 概ね log2(x) の固定小数点表現となる (小数部23ビット)
    int32_t fxp_y = tmp - (127 << 23);

    // 浮動小数点に換算
    float y = (float)fxp_y / (float)(1 << 23);

    printf("%f, %f\n", x, y);
  }