在Chrome中，Math.log2精度已更改

Question

我写了一个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的修改，是否有更加优雅的修改方法？

- Stefan Musarra

---

实际上这是V8的一项变更。是的，它已经被注意到了。(链接为相关注释) - raina77ow

真正让我惊奇的是，一个众所周知的 shim (Math.log2 = function(x) { return Math.log(x) / Math.LN2 };) 在 Chrome 中实际上为精确的幂返回了正确的结果。 - raina77ow

谢谢 - 我认为使用 shim 比添加 epsilon 更加优雅。 - Stefan Musarra

你能不能直接使用Math.round而不是Math.floor呢？ - soktinpk

@soktinpk：OP正在寻找二叉树的深度，该深度不会在中间点处四舍五入。 - Qantas 94 Heavy

Answer 1

注意：自从V8实现以来，Math.log2并没有实际更改。也许你记错了，或者你包含了一个shim，在Chrome包含其自己的Math.log2实现之前恰好得到了这些特殊情况的正确结果。

此外，似乎你应该使用Math.ceil(x)而不是Math.floor(x)+1。

如何解决这个问题？

为了避免依赖于JavaScript的不同实现中Math.log或Math.log2的准确性（所使用的算法是实现定义的），如果您的二叉树元素少于2^32个，可以使用位运算符。显然，这不是最快的方法（只有O(n)），但这是一个相对简单的例子。

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

Math.log2在不同浏览器中是如何实现的？

目前Chrome的实现存在精度问题，因为它们依赖于将Math.log(x)的值乘以Math.LOG2E，使其容易受到舍入误差的影响（source）：

// 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上），将使用类似Chrome的实现（来源）。

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

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

乘法或除法：有多大的差别？

为了测试通过除以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);
}

请注意，无论使用哪个函数，它们仍然会在某些值上存在浮点误差¹。恰好发生的是，log(2)的浮点表示小于实际值，导致一个比实际值更高的值（而log2(e)则更低）。这意味着对于这些特殊情况，使用log(2)将向下舍入到正确的值。

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

- Qantas 94 Heavy

---

稍微相关：http://jsperf.com/integer-log2/6（它们都产生整数log2，如果这不是很明显的话） - copy

我打开了全新的Chrome和Firefox实例，进入开发者工具控制台，并输入Math.log2(8)。在Firefox中仍然得到3，在Chrome中得到2.9999999999999996，因此我认为我没有引起差异的垫片。 - Stefan Musarra

@StefanMusarra：如果我没有表达清楚，那我很抱歉。有时候人们会添加代码来支持在还没有该函数的浏览器中使用 Math.log2，所以他们会添加类似于 if (!Math.log2) Math.log2 = function (x) { return Math.log(x) / Math.LN2 }; 的内容。如果你之前在 Chrome 添加 Math.log2 函数之前进行过测试，那么现在的结果将与之前不同。 - Qantas 94 Heavy

Answer 2

你可以尝试这样做

// Math.log2(n_elements) to 10 decimal places
var tree_depth = Math.floor(Math.round(Math.log2(n_elements) * 10000000000) / 10000000000);

- mildog8