Solution: The key here is you need to know log2(1+x) = x/ln2 = x/0.69 when x is very close to 1. Therefore the algorithm first use sqrt() to reduce x to be very close to 1 then we can use the formular.
double log2(double x)
{
assert(x>0);
double res = 1.0;
while(x-1 > threshold)
{
x = sqrt(x);
res = res *2;
}
return res * x/0.69;
}
It doesn't work.
ReplyDeleteThe right way to do it is to observe that log2(log2(N)) grows (or shrinks) comparable to sqrt(n).
ReplyDeleteFor example, log2(log2(N)) is the number of times you need to apply sqrt() to N, to bring it down to 2.0.
i.e. log2(log2(65536)) = 4.0
and sqrt(sqrt(sqrt(sqrt(65536)))) = 4.0
Hence, while the following should work, it's a gross approximation and the values will be way off for larger N.
def logBase2(N):
iters = 0
while N > 2.0:
N = sqrt(N)
iters = iters + 1
return 1 << iters