[PD] nearest power of 2

[Mathieu Bouchard]

On Fri, 12 Dec 2008, hard off wrote:

> what's the easiest way for pd to find the nearest power of 2 for any float?

depends how you define «nearest». multiplication-wise, 92 is closer to 128 
than to 64, because 92*92 > 64*128, whereas addition-wise, it's closer to 
64 because 92+92 < 64+128.

For nearest powers of something, I'd use the multiplication-wise 
definition, whereas for nearest multiples of something, I'd use the 
addition-wise definition.

To get the position of the highest bit of x, you can do log(x)/log(2), 
though there is an int-only algorithm in gridflow.h:

#define Z(N) if ((x>>N)&(((typeof(x))1<<N)-1)) { x>>=N; i+=N; }
static int highest_bit(uint32 x) {int i=0;Z(16)Z(8)Z(4)Z(2)Z(1)return i;}

... this splits a number in two sets of bits repeatedly to find where the 
top bit is.

However, I suspect that log(x)/log(2) could be faster than the version 
without log, because interpretation of pd patches is slow.

when you have the highest bit you have the previous-or-equal power-of-two 
as 1<<highest_bit. To find the multiplication-wise nearest power-of-two 
for x, you could round half of the highest bit of x*x, but if 
log(x)/log(2) is better for you, then you could round log(x)/log(2).

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec