[JavaScript] Math.log2は安易に使ってはいけない

Math.log2を安易に使うと起きる問題

Math.log2(x)は2を底とするxの対数を求める関数であり、ES2015で新規に追加された関数の一つである。
この関数の具体的な利用シチュエーションを安易に考えると、次のようなものが挙げられるだろう。

// ある数xが2の累乗数（1, 2, 4, 8, ...）であるかどうかを判定する
function isPowerOf2(x) {
  return x >= 1 && Number.isInteger(Math.log2(x));
}

// ある正整数xを2進数で表記するのに何桁必要かを調べる
function calcNumberOfDigits(x) {
  return Math.floor(Math.log2(x)) + 1;
}

ところが、これらのコードは次のような場合にうまく動かない。

// Math.log2が未実装の環境でbabel-polyfillのpolyfillを使う場合に再現する
isPowerOf2(Math.pow(2, 29)) // => false（本当はtrueであってほしい）

// こちらは自分が確認した範囲ではどんな環境でも再現する
calcNumberOfDigits(Math.pow(2, 53) - 1) // => 54（本当は53であってほしい）

問題の原因

何故望ましくない挙動になってしまうのかというと、浮動小数点数の丸め誤差が関係している。

babel-polyfillのMath.log2(x)はMath.log(x) / Math.LN2として定義されている。
Math.log(x)の丸め誤差と除算結果の丸め誤差によって、2の累乗数判定のコードは正しく動かない。

$\log_2(2^{53}-1)$は53よりもほんのわずかに小さい。
そのわずかな差は倍精度浮動小数点数では表現できないので、Math.log2(Math.pow(2, 53) - 1)は53に丸められ、桁数カウントのコードは正しく動かない。

このように、これらのコードは浮動小数点数の丸め誤差を発生させるため、2の累乗数付近の入力値では望ましくない挙動になってしまうのである。

問題に対する解決策

計算誤差にシビアなケースでは安易にMath.log2を使うのは避けるべきだと言うことができる。
では、上記のコードをうまく動作させるにはどうすればいいのだろうか？
解決策としては、以下のような、Math.log2を使わない実装が考えられる。

次のようなヘルパー関数を用意する。

function helper(x) {
  if (!(Number.isFinite(x) && x !== 0)) return x;

  let f, e;
  if (Math.abs(x) >= 1) {
    for (f = Math.abs(x), e = 0; f >= 2; f /= 2, ++e);
  } else { // 0 < Math.abs(x) < 1
    for (f = Math.abs(x), e = 0; f < 1; f *= 2, --e);
  }
  return {sign: x > 0 ? 1 : -1, fraction: f, exponent: e};
}

0でない有限の数について、正確に
$x = \mathrm{sign} \times \mathrm{fraction} \times 2^\mathrm{exponent}$（ただし$\mathrm{sign} \in \{1, -1\},,1 \leq \mathrm{fraction} \lt 2,,\mathrm{exponent} \in \mathbb{Z}$）となるようにしている。
浮動小数点数に2をかけたり割ったりする操作は（基本的に）計算誤差を発生させないのでこのようなことができる。

このヘルパー関数を使うことで、2の累乗数判定や桁数カウントが正確にできるようになる。

// ある数xが2の累乗数であるかどうかを判定する
function isPowerOf2(x) {
  const value = helper(x);
  return typeof(value) === "object" && value.sign === 1 && value.fraction === 1 && value.exponent >= 0;
}

// ある正整数xを2進数で表記するのに何桁必要かを調べる
function calcNumberOfDigits(x) {
  return helper(x).exponent + 1;
}

isPowerOf2(Math.pow(2, 29)) // => true
calcNumberOfDigits(Math.pow(2, 53) - 1) // => 53

まとめ

Math.log2を使っていいのは、Math.log2の結果が丸められても大丈夫な場合だけである。
それ以外の場合、Math.log2を使ったコードは、浮動小数点数の丸め誤差のせいで、2の累乗数付近の値でバグることが多い。
本当にそのコードで大丈夫か確認しておこう。