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

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()
print
print "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.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

8 comments:

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

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

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

    ReplyDelete
  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?

    - Paddy.

    ReplyDelete
  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

    ReplyDelete
  6. Paddy:

    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.

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

    ReplyDelete
  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?

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us