Find algorithm to base 2 of number without math module

Question

What is the most efficient way to find the logarithm to base 2 of a given number without using math module?

math.log and math.log2 are float operations therefore have inherent accuracy problems and may give false results, but they are very fast.

The number is guaranteed to be a power of 2, the function will only be executed if the following function returns True:

def power_of_2(n):
    return (n & (n-1) == 0) and n != 0

I want the result to be 100% accurate and I have already found a way to achieve this:

def log2(n):
    i = 0
    while n > 1:
        n >>= 1
        i += 1
    return i

performance:

In [244]: def log2(n):
     ...:     i = 0
     ...:     while n > 1:
     ...:         n >>= 1
     ...:         i += 1
     ...:     return i

In [245]: log2(33554432)
Out[245]: 25

In [246]: import math

In [247]: math.log2(33554432)
Out[247]: 25.0

In [248]: %timeit log2(33554432)
2.37 µs ± 208 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [249]: %timeit math.log2(33554432)
125 ns ± 1.34 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

I found bit manipulation more suitable than float operations for this task, how can I improve the performance of the function while using the same logic?

Answer 1

I have tried to run most of the methods from different answers from 1 and 2 where I found that power_of_2 and easy show a good performance.

import math
import timeit

def myLog(x, b):
    if x < b:
        return 0
    return 1 + float(myLog(x / b, b))


def easy(x):
    return x.bit_length() - 1


def brute(x):
    # determine max p such that 2^p <= x
    p = 0
    while 2 ** p <= x:
        p += 1
    return p - 1


def log2_approx(val):
    from math import floor
    val = floor(val)
    approx = 0
    while val != 0:
        val &= ~ (1 << approx)
        approx += 1
    return approx


def log2(n):
    i = 0
    while n > 1:
        n >>= 1
        i += 1
    return i


def power_of_2(n):
    return (n & (n - 1) == 0) and n != 0

def log2_fast(n):
    return  math.frexp(33554436)[1] - 1
import time
from functools import partial
 
import time

start_time = time.time()
math.log2(33554432)
print("math.log2 is %s microseconds ---" % ((time.time() - start_time) * 1000000))
start_time = time.time()
myLog(33554432.0, 2.0)
print(" myLog is %s microseconds ---" % ((time.time() - start_time) * 1000000))

start_time = time.time()
brute(33554432)
print(" brute is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))
start_time = time.time()

log2_approx(33554432) - 1
print("log2_approx is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))
start_time = time.time()
log2_fast = math.frexp(33554436)[1] - 1
print(" log2_fast is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))

start_time = time.time()
log2(33554432)
print("log2 is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))

start_time = time.time()
power_of_2(33554432)
print("power_of_2 is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))
start_time = time.time()
easy(33554432)
print("easy is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))

Running time

 math.log2 is 3.0994415283203125 microseconds ---
 myLog is 5.4836273193359375 microseconds ---
 brute is --- 6.4373016357421875 microseconds ---
 log2_approx is --- 6.4373016357421875 microseconds ---
 log2_fast is --- 1.6689300537109375 microseconds ---
 log2 is --- 2.1457672119140625 microseconds ---
 power_of_2 is --- 0.7152557373046875 microseconds ---
 easy is --- 0.476837158203125 microseconds ---

Using timeit shows delay

test_items=33554432
base=2
times = timeit.Timer(partial(math.log2, test_items))
print("math.log2 is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(myLog, test_items,base))
print("myLog is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(easy, test_items))
print("easy is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(brute, test_items))
print("brute is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(log2_approx, test_items))
print("log2_approx is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(log2, test_items))
print("log2 is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(power_of_2, test_items))
print("power_of_2 is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(log2_fast, test_items))
print("log2_fast is %s microseconds ---", (times.timeit(1000000)))

Running time

math.log2 is %s microseconds --- 0.05126429593656212
myLog is %s microseconds --- 4.137887543998659
easy is %s microseconds --- 0.10356121498625726
brute is %s microseconds --- 5.254867412033491
log2_approx is %s microseconds --- 3.81522585300263
log2 is %s microseconds --- 1.7966924259671941
power_of_2 is %s microseconds --- 0.1572157460032031
log2_fast is %s microseconds --- 0.21886748599354178

Answer 2

If your code needs to call this function repeatedly, and the inputs are guaranteed to be even integer powers of two (unlike your example!) I imagine it's going to be hard to beat a hard-coded dictionary lookup.

def precalculate_pow2(ceiling):
    i = 1
    result = dict()
    for n in range(ceiling):
        result[i] = n
        i <<= 1
    return result

powersof2 = precalculate_pow2(500) # or whatever your upper limit is

def log2(n):
    return powersof2[n]

Obviously, the loop to calculate the values is no more efficient than your current code, but memoizing it allows you to amortize that cost over all the calls to the log2 function.

As a variation, you could start with the dictionary containing only one value, and only populate the missing parts on subsequent calls, using a recursive function.

powersof2 = {1: 0}

def log2(n):
    if n not in powersof2:
        powersof2[n] = 1 + log2(n >> 1)
    return powersof2[n]

This has the obvious drawback that it will go into an endless loop if you call it with a negative value (though Python will then throw a traceback once you exhaust the maximum recursion limit).