I commented on what I thought would be a better solution. Richard Jones pointed us at how pyglet solved how to find the net power of two and how to check if a number is a power of two using some nifty bit twiddling.

Will McGugan then timed

both his and pyglets code, but didn't implement my suggestion (I didn't give code).

I have added an implementation of my suggestion and timed all three sets.

The timing shows that although my implementation of is_power_of_2 is fastest by a smidgen; My implementation of next_power_of_2 by iterative comparison of a list is half way between Wills and pyglets implementation, with pyglet the winner.

I have not got timings with psyco.

The code

setup_1 = """

from math import log, ceil

def is_power_of_2(n):

return log(n, 2) % 1.0 == 0.0

def next_power_of_2(n):

return (2 ** ceil(log(n, 2)))

"""

setup_2 = """

def next_power_of_2(v):

v -= 1

v |= v >> 1

v |= v >> 2

v |= v >> 4

v |= v >> 8

v |= v >> 16

return v + 1

def is_power_of_2(v):

return (v & (v - 1)) == 0

"""

setup_3 = """

list_of_powers = [x**2 for x in range(32)]

set_of_powers = set(list_of_powers)

def next_power_of_2(v):

for x in list_of_powers:

if x >= v: return x

def is_power_of_2(n):

return n in set_of_powers

"""

from timeit import Timer

t1 = Timer("is_power_of_2(128)", setup_1)

t2 = Timer("is_power_of_2(128)", setup_2)

t3 = Timer("next_power_of_2(125)", setup_1)

t4 = Timer("next_power_of_2(125)", setup_2)

t5 = Timer("is_power_of_2(128)", setup_3)

t6 = Timer("next_power_of_2(125)", setup_3)

The Timings

float math is_power_of_2: 2.33588961726

bit-twiddling is_power_of_2: 0.573784377623

set-lookup is_power_of_2: 0.54499859619

float math next power of 2: 3.06279429369

bit-twiddling next power of 2: 2.08060354039

list-comparison next power of 2: 2.58548279181

Interesting results, thanks! The next_power_of_2 function has linear performance though. I wonder if it can be done in constant time...

ReplyDeleteAs a test, I just loaded your blog page using a new feature of the alpha version of crunchy[*] on my computer and found the bit-twiddling to be the fastest by a smidgen:

ReplyDeletefloat math is_power_of_2: 2.05480490349 bit-twiddling is_power_of_2: 0.614713742749 set-lookup is_power_of_2: 0.635365676879 float math next power of 2: 2.62028308706 bit-twiddling next power of 2: 1.44359330406 list-comparison next power of 2: 1.71020391571

[*] All I had to do is copy the url from your blog and the code was loaded ready to be executed. If you want to know how to do this, feel free to email me.

André, can you post a link to documentation on how you can run code from just a URL using Crunchy? I have been watching crunchy development posts, had tried out an early version but this ability is new to me.

ReplyDeleteOn the changes to the order of timings, I should note that I am using an AMD Turion64 notebook - maybe André is using an Intel chip?

ReplyDelete- Paddy.

As I had expected, psyco optimizes the bit-twiddling version to an enormous degree:

ReplyDeleteNon-psyco runs:

float math is_power_of_2: 3.45202616534

bit-twiddling is_power_of_2: 1.96388256049

set-lookup is_power_of_2: 0.6184283198

float math next power of 2: 4.55189640024

bit-twiddling next power of 2: 2.11398962717

list-comparison next power of 2: 3.02703835264

With pysco:

float math is_power_of_2: 4.00380746715

bit-twiddling is_power_of_2: 0.0121230491585

set-lookup is_power_of_2: 0.975068339691

float math next power of 2: 5.06961331678

bit-twiddling next power of 2: 0.0159525861527

list-comparison next power of 2: 3.34381911668

Paddy:

ReplyDeleteI used an Intel Core 2 Duo MacBook for the tests.

Regarding Crunchy, I can't point you to some relevant documentation (yet). You already have mentioned the basic link; download the

alphaversion and start crunchy.py, then typecrunchy.no_markup = 'editor'

at the interpreter prompt (the default is "interpreter"), click on the "tests" link in the text above, then on the "loading arbitrary tutorials" link. You can then enter the url of your blog and have fun.

I'm hoping that we'll have a non-alpha release of version 0.9 soon, with proper documentation of all the new features.

using a generator syntax instead of list-comprehension should make a difference

ReplyDeletelist_of_powers = (x**2 for x in range(32))

on my computer (Pentium 4 2.0Ghz), where set-lookup2 and list-comparison2 use the generator syntax:

float math is_power_of_2: 2.86237287521

bit-twiddling is_power_of_2: 0.939764976501

set-lookup is_power_of_2: 0.940165042877

set-lookup2 is_power_of_2: 0.871818065643

float math next power of 2: 3.69351601601

bit-twiddling next power of 2: 2.42883086205

list-comparison next power of 2: 3.53486704826

list-comparison2 next power of 2: 0.833928108215

the difference between set-lookup and set-lookup2 isn't consistent between runs.

Firstly, is 0 considered a power of two for your purposes?

ReplyDeleteSecond, isn't another definition of a power of two a number which, when the lowest bit is cleared, results in 0? Perhaps x & (x - 1) is a quicker test?