# $\log_2$ approximation in $[1,2)$

this is realistically for a programming project, but is more math centric then CS centric. I am attempting to write a function that approximates a power function, but in order to complete I need to approximate log2(x). using the understanding that

$$x^y = x^{a+b+c+d+\dots} = x^a*x^b*x^c*x^d\dots || y = a+b+c+d+\dots$$

and that

$\displaystyle x^y = 2^{y\log_2(x)}$ computers think in base $2$ easier then base $10$, or $e$

since this would only be used for values $y \in [1,2)$ the solution only needs to be accurate on those bounds. considering that $log_c(a*c^x) = log_c(a) + x$ by factorization (not necessarily prime) I can reduce the input to a value on those bounds.

I need the RHS of $\displaystyle log_2(x) = || x \in [1,2)$

defined in addition, subtraction, multiplication, and division. whole number exponents are also acceptable.

EDIT: did some analysis, and updated question.

-
Is it $x$ or $y$ in $[0,1)$? You might want to avoid $\log 0$. – Henry Mar 18 '12 at 17:39
@henry log(0) will be avoided by breaking out of the function if x = 0 resulting in 0. considering 0^x = 0, except 0^0 which is by calculus definition 1. will think on the bounds. please keep question open for edits – gardian06 Mar 18 '12 at 17:46
@gardian06 I strongly recommend not defining log(0) as 0. Return NaN or -Inf if you have access to it, throw an exception if you need to, but given that log(1)=0 and log(x) is negative for x &lt; 1, returning log(0) as 0 is only begging for a host of subtle bugs. – Steven Stadnicki Mar 18 '12 at 17:53
Which do you want, $\log_2(x)$ or $x^y$? Are you using floating-point or fixed-point? How much accuracy do you need? – Robert Israel Mar 18 '12 at 17:55
@stevenstadnicki I didn't say that I would define log(0) = 0. I said that it would be avoided by if the base of the exponent is 0 to return 0, or 1 depending on the power. as 0^x || x != 0 = 0, and 0^0 is 1 – gardian06 Mar 18 '12 at 18:41

I assume that you are working with floating-point numbers ala IEEE 754. In this case, I do not see how base $2$ is going to give you any significant advantage. Instead, I would use the identities

$$\ln(x) = 2\cdot\sum_{k=0}^\infty \left(\frac{x-1}{x+1}\right)^{2k+1} \cdot \frac{1}{2k+1}$$

and

$$\exp(x) = \sum_{k=0}^\infty \frac{x^k}{k!},$$

both of which are very fast converging series. Then, $x^y = \exp(y\cdot\ln(x))$. See also the wiki page on computing the logarithm.

-
how many terms of eq1 will I need to make it convergent on x $in [1,2)$ – gardian06 Mar 18 '12 at 18:48

On the interval $[1/2, 1]$, an approximation to $\log_2(x)$ accurate to about $1.7 \times 10^{-14}$ is

f(x) = (-.2119568027628040757e-1+(-.38815224340108325886+(-.8900051141728954376+ (.4001641794691007527 + (.79615191430677253059+.10303694407435362078*x)*x)*x)*x)*x)/ (.298115002929551095e-2+(.1066700361116609290+(.6070463053447878628+ (.8584931203106122717+(.30170842595823793523+.16863931436090069014e-1*x)*x)*x)*x)*x)

For $2^{-n+1} \le y \le 2^{-n}$, use $-n + f(2^n y)$.

-

The CORDIC algorithm can be used to give good $\log$ and $\exp$ approximations. I wrote such functions using fixed point math for QuickDraw GX. All that is required is shifting, adding, and subtracting.

-

$$log_2(x) = \sum_{k=0}^\infty \frac{-(-1)^K(x-1)^k}{\ln(2^k)},$$ convergent on $x \in [1,2)$ after about $10$ terms though may needs about 12 terms to be mostly convergent on those bounds,

and for the cs application a table of the $\ln(2^k)$ values should suffice. though a table of $\frac{1}{\ln(2^k)}$ may be more beneficial depending on the actual values there in, and that multiplication by a floating point number is more efficient then division.

-