Notice Log2(1+y) = y/ln(2) = 1.442695*y (when x is very small) So the solution is: when x >= 2, divide x, until 1

This code doesnt work .. it will return 4 for log2(10), log2(12) etc .. until log2(16) : public static double log2(double num) { if(num<=2) return 1; double y = Math.sqrt(num); if(y*y == num) { return (2*log2(y)); } else { return (log2(num/2)+1); } } Specifically I think return log2(x / 2) + 1 is true for all odd and even ..I wonder if sqrt is used only because it has been asked to be used .. can you please explain your approach again ? Thanks

Used formulas: log ab = loga + logb, eg: log32 = log16 + log2 loga^2 = 2 loga To clarify a little bit more: Let x be 2^k number. If k is odd, we can divide by 2 and add 1. The recurrence goes on with this odd/even loop. As clearly can be seen, complexity is O(logn). Improvement: The division might be changed to increase the precision with handling the remainder.

ln(1+x) = x(6+x)/(6+4x) (see http://www.nezumi.demon.co.uk/consult/logx.htm) So, log2(1+x) = (x(6+x)/(6+4x))/ln(2) Using Sumer Cip's code and modifying it a bit: def log2(x): if x <= 2: z = x-1 return (1.442695*z*(6+z)/(6+4*z)) else: y = sqrt(x) return 2*log2(y)

Solution might be: from math import sqrt def log2(x): if x <= 2: return 1 y = sqrt(x) if (y*y != x): return log2(x / 2) + 1 else: return 2*log2(y) Note that algorithm rounds roughly the logarithms of non 2-base numbers. This can be improved.

#include #include using namespace std; double log2(double x, double precision) { if(x > x) { cout << log2(x, 0.00000005) << endl; } }