Recursive/iterative/native integer log2 algorithm comparison in Python

log2.py

#
# Recursive/iterative/native integer log2 algorithm comparison in Python
#
# (c) 2017 Heiko Schaefer <[email protected]>
#

import sys, time, math

# recursive
def log2r(a, b = 0):
  if a == 1: return b + 1
  return log2r(long(a >> 1), b + 1)

# iterative
def log2i(a):
  r = a
  b = 0
  while(r != 1):
    r >>= 1
    b += 1
  return b + 1

# benchmarking
x   = long(sys.argv[1])
ln2 = math.log(2)

rce = time.clock()
rln = log2r(x)
rce = time.clock() - rce
ice = time.clock()
iln = log2i(x)
ice = time.clock() - ice
pce = time.clock()
pln = long(math.floor((math.log(x)/ln2) + 1))
pce = time.clock() - pce

fcr = time.clock()
for n in range(1, 100000): log2r(x)
fcr = time.clock() - fcr

fci = time.clock()
for n in range(1, 100000): log2i(x)
fci = time.clock() - fci

fcp = time.clock()
for n in range(1, 100000): long(math.floor((math.log(x)/ln2) + 1))
fcp = time.clock() - fcp

# output
print "1 time:"
print "recursive int log2(" + str(x) + ") = " + str(rln) + " [t=" + str(rce) + "]"
print "iterative int log2(" + str(x) + ") = " + str(iln) + " [t=" + str(ice) + "]"
print "   native int log2(" + str(x) + ") = " + str(pln) + " [t=" + str(pce) + "]"
print
print "100000 times:"
print "recursive int log2(" + str(x) + ") = " + str(rln) + " [t=" + str(fcr) + "]"
print "iterative int log2(" + str(x) + ") = " + str(iln) + " [t=" + str(fci) + "]"
print "   native int log2(" + str(x) + ") = " + str(pln) + " [t=" + str(fcp) + "]"