Chrome中的Math.log2精度已更改 [英] Math.log2 precision has changed in Chrome

问题描述

我编写了一个JavaScript程序，该程序根据元素的数量来计算二叉树的深度.我的程序可以正常运行几个月，但是最近发现在Chrome和Firefox中浏览网页时有所不同.

I've written a JavaScript program that calculates the depth of a binary tree based on the number of elements. My program has been working fine for months, but recently I've found a difference when the web page is viewed in Chrome vs Firefox.

尤其是在Firefox上:

In particular, on Firefox:

Math.log2(8) = 3

但现在在Chrome中:

but now in Chrome:

Math.log2(8) = 2.9999999999999996

我的JavaScript程序最初是根据以下元素的数量来查找二叉树的深度的:

My JavaScript program was originally written to find the depth of the binary tree based on the number of elements as:

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

我对该公式进行了简单的修改，以使其在Chrome上仍然可以正常运行:

I made a simple modification to this formula so that it will still work correctly on Chrome:

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

我有2个问题:

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

是否有比上面通过添加epsilon进行的修改更优雅的修改?

Is there a more elegant modification than the one I made above by adding epsilon?

推荐答案

注意:自实施以来，Math.log2并没有实际更改 在V8中也许您记错了，或者您包含了一个垫片 碰巧在Chrome之前针对这些特殊情况获得了正确的结果 包括自己的Math.log2实现.

Note: Math.log2 hasn't actually changed since it's been implemented in V8. Maybe you remembered incorrectly or you had included a shim that happened to get the result correct for these special cases before Chrome included its own implementation of Math.log2.

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

Also, it seems that you should be using Math.ceil(x) rather than Math.floor(x) + 1.

我该如何解决?

要避免在不同的JavaScript实现中依赖Math.log或Math.log2准确(所使用的算法是实现定义的)，如果少于2个 ³² ，则可以使用按位运算符二叉树中的元素.显然这不是最快的方法(这只是O(n))，但这是一个相对简单的示例:

How can I solve this?

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

Math.log2当前如何在不同的浏览器中实现?

Chrome当前的实现方式不准确，因为它们依赖于将Math.log(x)的值乘以Math.LOG2E，从而很容易出现舍入错误(

How is Math.log2 currently implemented in different browsers?

The current implementation in Chrome is inaccurate as they rely on multiplying the value of Math.log(x) by Math.LOG2E, making it susceptible to rounding error (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功能(如果存在)，或者不使用本机功能(例如，

If you are running Firefox, it either uses the native log2 function (if present), or if not (e.g. on Windows), uses a similar implementation to Chrome (source).

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

The only difference is that instead of multiplying, they divide by log(2) instead:

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

double
js::math_log2_impl(MathCache *cache, double x)
{
    return cache->lookup(log2, x, MathCache::Log2);
}

double
js::math_log2_uncached(double x)
{
    return log2(x);
}

bool
js::math_log2(JSContext *cx, unsigned argc, Value *vp)
{
    return math_function<math_log2_impl>(cx, argc, vp);
}

所有其他代码仅用于将结果缓存在表中，而Chrome不会这样做.这对Firefox Math.log2函数的准确性没有任何影响.

All the other code is just to cache the results in a table, which Chrome does not do. This does not have any effect on the accuracy of Firefox's Math.log2 function.

要测试除以Math.LN2和乘以Math.LOG2E之间的区别，我们可以使用以下测试:

To test the difference between dividing by Math.LN2 and multiplying by Math.LOG2E, we can use the following test:

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

var pow = Math.pow;

// 2^1024 rounds to Infinity
for (var i = 0; i < 1024; ++i) {
  var resultD = log2d(pow(2, i));
  var resultM = log2m(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)将舍入为正确的值.

Please 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

这篇关于Chrome中的Math.log2精度已更改的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！