5.2.5 Example: 2 Power

The following Sage notebook session illustrates how to implement in Cython (entirely using the notebook) a function to quickly tell if a C integer is a power of

. The resulting function is over 200 times faster in Cython than in Python, though the actual code is identical.

{{{
%cython
def is2pow(unsigned int n):
    while n != 0 and n%2 == 0: 
        n = n >> 1
    return n == 1
}}}

{{{
time [n for n in range(10^5) if is2pow(n)]
///
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]
CPU time: 0.05 s,  Wall time: 0.06 s
}}}

{{{
# The same program but in Python:
def is2pow(n):
    while n != 0 and n%2 == 0: 
        n = n >> 1
    return n == 1
}}}

{{{
time [n for n in range(10^5) if is2pow(n)]
///
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]
CPU time: 13.04 s,  Wall time: 15.08 s
}}}

{{{
13.04/0.05
///
260.79999999999995
}}}

See About this document... for information on suggesting changes.