Closest Power Of Two

davesch · 2017-08-13 07:38:49

Expand///next_pow2(val);

return power(2,clamp((ceil(log2(argument0))),1,100000000000000000000));

I know this script already exists here but this one is about 3x as fast as the old one below.

Expand/// next_pow2(n)
//
//  Returns the next power-of-two greater than or equal to a given value.
//
//      n       positive integer
//
/// GMLscripts.com/license
{
    var n = argument0 - 1;
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    n |= (n >> 32);
    return n + 1;
}

Last edited by davesch (2017-08-13 07:42:32)

xot · 2017-08-15 14:12:57

This is one of those cases where there really isn't an optimal solution nor, I suspect, is one really needed.

I did tests of 100 iterations of a set of 30,000 random values (ie. 3,000,000 total iterations per test). Under the Window VM, I measure your version as being about twice as fast. Under the Windows YYC, the speed is almost the same. Under HTML5 the original is significantly faster. I then removed the clamp() function because it is a bit superfluous and causes the wrong value to be returned in the case of n = 1. That boosted the speed of yours by around 10% under Windows VM and Windows YYC.

Platform Original Yours*
Windows VM 3066 ms 1362 ms
Windows YYC 560 ms 496 ms
HTML5 27 ms 178 ms

I wasn't able to test other platforms. This isn't the sort of function I imagine being speed-critical and in no case is it especially slow. The slowest was only 1 microsecond per call.

All that said, I think with the removal of the clamp() function yours edges out the original in terms of aesthetics, so I'll be updating the script in the library.

Thanks for the update.

xot · 2017-08-19 13:42:50

I was able to gain a bit of performance by replacing the power() to a bit-shift which is faster for powers-of-two. Windows VM improved by 5%, Windows YYC by 33%, and HTML5 by 17%. Teamwork!

Expand/// next_pow2(n)
//
//  Returns the next power-of-two greater than or equal to a given value.
//
//      n       positive integer
//
/// GMLscripts.com/license
{
    return 1 << ceil(log2(argument0));
}

davesch · 2017-08-22 18:56:45

Awesome! Love that solution both aesthetically and functionally over the others.

GMLscripts.com

#1 2017-08-13 07:38:49

Closest Power Of Two

#2 2017-08-15 14:12:57

Re: Closest Power Of Two

#3 2017-08-19 13:42:50

Re: Closest Power Of Two

#4 2017-08-22 18:56:45

Re: Closest Power Of Two

Board footer