CODEWITHSUNDEEP
javascriptdoublebit-manipulationieee-754
MaiaVictor
MaiaVictor

Reputation: 53037

Fast nearest power of 2 in JavaScript?

Is there any faster alternative to the following expression:

Math.pow(2,Math.floor(Math.log(x)/Math.log(2)))

That is, taking the closest (smaller) integer power of 2 of a double? I have such expression in a inner loop. I suspect it could be much faster, considering one could just take the mantissa from the IEEE 754 representation of the double.

Upvotes: 18

Views: 8257

Answers (8)

Zibri
Zibri

Reputation: 9857

Oh and I forgot the one-liner:

a=3764537465
console.log(2**~~Math.log2(a))

In other words, here we raise 2 to the power of the rounded logarithm in base 2 of the number. But alas, this is 140 times slower than the winner: blpo2 https://stackoverflow.com/a/74916422/236062

Upvotes: 0

Zibri
Zibri

Reputation: 9857

Here is also a branchless 32 bit version which is the fastest (9x) (on cellphones even more!) as of now. It can also be scaled to 64 or 128 bits adding 1 or two lines:

x = x | (x >> 64);
x = x | (x >> 128);

on my computer:

2097152,blpo2: 118 ms **FASTEST**
2097152,nearestPowerOf2: 973 ms
2097152,pow2floor: 2033 ms

on my phone:

2097152,blpo2: 216 ms **FASTEST**
2097152,nearestPowerOf2: 1259 ms
2097152,pow2floor: 2904 ms


function blpo2(x) {
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);
  x = x | (x >> 32);
  return x - (x >> 1);
}

function pow2floor(v) {
  var p = 1;
  while (v >>= 1) {
    p <<= 1;
  }
  return p;
}

function nearestPowerOf2(n) {
  return 1 << 31 - Math.clz32(n);
}

function runner(fn, val) {
  var res;
  var st = new Date().getTime()
  for (var i = 0; i < 100000000; i++) {
    res = fn(val);
  }
  dt = new Date().getTime() - st;
  return res + "," + fn.name + ": " + dt + " ms"
}

var source = 3000000;

console.log(runner(blpo2, source), "**FASTEST**")
console.log(runner(nearestPowerOf2, source))
console.log(runner(pow2floor, source))

Upvotes: 4

bob
bob

Reputation: 7985

Here's another alternative, with benchmarks. While both seems to be comparable, I like being able to floor or ceil.

function blpo2(x) {
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);
  x = x | (x >> 32);
  return x - (x >> 1);
}

function pow2floor(v) {
  var p = 1;
  while (v >>= 1) {
    p <<= 1;
  }
  return p;
}

function pow2ceil(v) {
  var p = 2;
  while (v >>= 1) {
    p <<= 1;
  }
  return p;
}

function MATHpow2(v) {
  return Math.pow(2, Math.floor(Math.log(v) / Math.log(2)))
}


function nearestPowerOf2(n) {
   return 1 << 31 - Math.clz32(n);
}

 function runner(fn, val) {
  var res;
  var st = new Date().getTime()
  for (var i = 0; i < 100000000; i++) {
    fn(val);
  }
  return (new Date().getTime() - st)
}

var source = 300000;

var a = runner(pow2floor, source);
console.log("\n--- pow2floor ---");
console.log(" result: " + pow2floor(source));
console.log(" time: " + a + " ms");

var b = runner(MATHpow2, source);
console.log("\n--- MATHpow2 ---");
console.log(" result: " + MATHpow2(source));
console.log(" time: " + b + " ms");

var b = runner(nearestPowerOf2, source);
console.log("\n--- nearestPowerOf2 ---");
console.log(" result: " + nearestPowerOf2(source));
console.log(" time: " + b + " ms");

var b = runner(blpo2, source);
console.log("\n--- blpo2 ---");
console.log(" result: " + blpo2(source));
console.log(" time: " + b + " ms");

// pow2floor: 1631 ms
// MATHpow2: 13942 ms
// nearestPowerOf2: 937 ms
// blpo2 : 919 ms   **WINNER**

Upvotes: 7

Zibri
Zibri

Reputation: 9857

And another way (this one is slow but it's fun to code recursive ones):

function calc(n, c) {
  c = c || 0;
  n = n >> 1;
  return (n > 0) ? calc(n, c + 1) : 2 ** c;
}

console.log(calc(345367));
console.log(calc(34536));
console.log(calc(3453));
console.log(calc(345));
console.log(calc(34));

Upvotes: 0

Zibri
Zibri

Reputation: 9857

And this is another.

function nP2(n) {
  return 1 << Math.log2(n);
}

console.log(nP2(345367));
console.log(nP2(34536));
console.log(nP2(3453));
console.log(nP2(345));
console.log(nP2(34));

Upvotes: 0

Zibri
Zibri

Reputation: 9857

Without ES6...

x=Math.floor(Math.random()*500000); //for example
nearestpowerof2=2**(x.toString(2).length-1);
console.log(x,">>>",nearestpowerof2);

In other words: the result is 2 to the power of the length of the binary representation of the number subtracted by 1.

Upvotes: 0

le_m
le_m

Reputation: 20248

Making use of ES6's Math.clz32(n) to count leading zeros of a 32-bit integer:

// Compute nearest lower power of 2 for n in [1, 2**31-1]:
function nearestPowerOf2(n) {
  return 1 << 31 - Math.clz32(n);
}

// Examples:
console.log(nearestPowerOf2(9));  // 8
console.log(nearestPowerOf2(33)); // 32

Upvotes: 23

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

Unfortunately, you would need an equivalent of the C function frexp. The best I've been able to find is in JSFiddle, and its code uses Math.pow.

There are a couple of alternatives you could benchmark, using real data, along with your current attempt:

  1. Starting at 1.0, multiply repeatedly by 2.0 until it is greater than or equal to the input, then multiply by 0.5 until it is less than or equal to the input. You would need special handling for values at the ends of the double range.
  2. Store an ascending value array of all the exact powers of two in the double range, and do a binary search.

The first one is likely to be fastest if your data is typically close to 1.0. The second one requires up to 11 conditional branches.

Upvotes: 0

Related Questions