Math.log2 precision has changed in Chrome

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.

In particular, on Firefox:

Math.log2(8) = 3

but now in Chrome:

Math.log2(8) = 2.9999999999999996

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;

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;

I have 2 questions:

1. Has anyone else noticed a change in the precision in Chrome recently for Math.log2?

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

Solution 1:

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.

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

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

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).
}

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).

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

Multiplying or dividing: how much of a difference does it make?

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; }

// 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