Fast power-of-two modulo

Here's a fast way to do power-of-two modulos that i found on the Wikipedia entry on power of two: If you want to "calculate the modulos of a non-negative integer (x) with a power of two (y) very quickly", just AND it with the desired modulo number minus one.

So if y is a power of two, then this formula applies:

x modulo y <=> (x & (y − 1))

This is pretty useful in Pure Data if you do music that is based on powers of two. Quite often you have a global counter running that just counts up. But then you want to get a "modulo 4" of this number to find the current beat in quarter notes. Or you want to get some "mod 32" to get even finer divisions. Generally for "four-to-the-floor" music your "mod X" number will be a power-of-two. In that case instead of [mod X] you can use [& X-1] instead. So replace [mod 32] with [& 31] or replace [mod 4] with [& 3] and so on. Here's how it looks like in Pd:

Fast power of two module with binary AND in Pd.

Note that we use the binary AND here, which in Pd is the object with just a single ampersand: [&] and not [&&].

More tricks with power of two on Chris' site.

Category: Pd
Tags: pd puredata math