Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

Sunday, July 01, 2007

bit twiddling extras

As a follow up to this
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 xdef is_power_of_2(n):    return n in set_of_powers"""from timeit import Timert1 = 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)print "float math is_power_of_2:", t1.timeit()print "bit-twiddling is_power_of_2:", t2.timeit()print "set-lookup is_power_of_2:", t5.timeit()printprint "float math next power of 2:", t3.timeit()print "bit-twiddling next power of 2:", t4.timeit()print "list-comparison next power of 2:", t6.timeit()`

The Timings
`float math is_power_of_2: 2.33588961726bit-twiddling is_power_of_2: 0.573784377623set-lookup is_power_of_2: 0.54499859619float math next power of 2: 3.06279429369bit-twiddling next power of 2: 2.08060354039list-comparison next power of 2: 2.58548279181`

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

2. As 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:

float 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.

3. 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.

4. On 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?

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

Non-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

6. I 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 alpha version and start crunchy.py, then type

crunchy.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.

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

list_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.

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

Second, 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?