Teaching Kids Programming: Videos on Data Structures and Algorithms
Since 
is monotonously increasing, we can use the Binary Search Algorithm (Binary Search Algorithm to Find the Inverse of a Monotone Increasing Function) to compute the Logarithm Base Two Function i.e. 
.
The input x is given strictly larger than zero, so we can initialize the left boundary to zero, and upperbound to x when given x is larger than 1. However, when it is below 1 and larger than 0, the lowerbound is negative infinity and upperbound is zero, we can use the following equation to turn it into the case when x is larger than 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | def log2(x): if x <= 0: return None if x < 1: return -log2(1.0/x) left, right = 0, x mid = (left + right) / 2 cur = pow(2, mid) while abs(cur - x) >= 1e-8: mid = (left + right) * 0.5 cur = pow(2, mid) if cur >= x: right = mid else: left = mid return mid print(log2(0.1)) # -3.321928095538169 print(log2(1)) # 7.450580596923828e-09 print(log2(2)) # 1.0 print(log2(1024)) # 10.0 print(log2(8)) # 3.0 print(log2(234)) # 7.870364719601639 |
def log2(x):
if x <= 0:
return None
if x < 1:
return -log2(1.0/x)
left, right = 0, x
mid = (left + right) / 2
cur = pow(2, mid)
while abs(cur - x) >= 1e-8:
mid = (left + right) * 0.5
cur = pow(2, mid)
if cur >= x:
right = mid
else:
left = mid
return mid
print(log2(0.1)) # -3.321928095538169
print(log2(1)) # 7.450580596923828e-09
print(log2(2)) # 1.0
print(log2(1024)) # 10.0
print(log2(8)) # 3.0
print(log2(234)) # 7.870364719601639–EOF (The Ultimate Computing & Technology Blog)
GD Star Rating
loading...
390 wordsloading...
Last Post: Teaching Kids Programming - Palindrome Permutation Algorithm
Next Post: Algorithms to Compute the Length of a Linked List
