Chrome 中的 Math.log2 精度已更改

我编写了一个 JavaScript 程序，它根据元素的数量计算二叉树的深度。我的程序几个月来一直运行良好，但最近我发现在 Chrome 和 Firefox 中查看网页时存在差异。

特别是在 Firefox 上：

Math.log2(8) = 3

但现在在 Chrome 中：

Math.log2(8) = 2.9999999999999996

我的 JavaScript 程序最初是为了根据元素数量查找二叉树的深度而编写的，如下所示：

var tree_depth = Math.floor(Math.log2(n_elements)) + 1;

我对这个公式做了一个简单的修改，以便它在 Chrome 上仍然可以正常工作：

var epsilon = 1.e-5;
var tree_depth = Math.floor(Math.log2(n_elements) + epsilon) + 1;

我有两个问题：

1. 有没有其他人注意到 Chrome 最近的精度发生了变化Math.log2?

2. 还有比我上面添加 epsilon 更优雅的修改吗？

Note: Math.log2自实施以来实际上没有改变 在V8中。也许您记错了，或者您添加了一个垫片 在 Chrome 之前碰巧得到了这些特殊情况的正确结果 包括它自己的实现Math.log2.

另外，看来你应该使用Math.ceil(x)而不是Math.floor(x) + 1.

我该如何解决这个问题？

To avoid relying on Math.log or Math.log2 being accurate amongst different implementations of JavaScript (the algorithm used is implementation-defined), you can use bitwise operators if you have less than 2³² elements in your binary tree. This obviously isn't the fastest way of doing this (this is only O(n)), but it's a relatively simple example:

function log2floor(x) {
  // match the behaviour of Math.floor(Math.log2(x)), change it if you like
  if (x === 0) return -Infinity;

  for (var i = 0; i < 32; ++i) {
    if (x >>> i === 1) return i;
  }
}

console.log(log2floor(36) + 1); // 6

How is Math.log2目前在不同浏览器中实现？

Chrome 中当前的实现是不准确的，因为它们依赖于乘以Math.log(x) by Math.LOG2E，使其容易受到舍入误差的影响（source https://code.google.com/p/v8/source/browse/trunk/src/math.js?r=24772#236):

// ES6 draft 09-27-13, section 20.2.2.22.
function MathLog2(x) {
  return MathLog(x) * 1.442695040888963407;  // log2(x) = log(x)/log(2).
}

如果您运行的是 Firefox，它要么使用本机log2函数（如果存在），或者如果不存在（例如在 Windows 上 https://stackoverflow.com/questions/758001/log2-not-found-in-my-math-h/766669#766669），使用与 Chrome 类似的实现（source https://github.com/mozilla/gecko-dev/blob/4bb9cac09b222a97c99e3be93419936d1e693d08/js/src/jsmath.cpp#L1028).

唯一的区别是，它们不是乘法，而是除法log(2)反而：

#if !HAVE_LOG2
double log2(double x)
{
    return log(x) / M_LN2;
}
#endif

乘法或除法：相差多少does它使?

测试除以之间的差异Math.LN2并乘以Math.LOG2E，我们可以使用以下测试：

function log2d(x) { return Math.log(x) / Math.LN2; }
function log2m(x) { return Math.log(x) * Math.LOG2E; }

// 2^1024 rounds to Infinity
for (var i = 0; i < 1024; ++i) {
  var resultD = log2d(Math.pow(2, i));
  var resultM = log2m(Math.pow(2, i));

  if (resultD !== i) console.log('log2d: expected ' + i + ', actual ' + resultD);
  if (resultM !== i) console.log('log2m: expected ' + i + ', actual ' + resultM);
}

Note that no matter which function you use, they still have floating point errors for certain values¹. It just so happens that the floating point representation of log(2) is less than the actual value, resulting in a value higher than the actual value (while log2(e) is lower). This means that using log(2) will round down to the correct value for these special cases.

^1: log(pow(2, 29)) / log(2) === 29.000000000000004