Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this 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
1  
@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 < 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
show 7 more comments

4 Answers

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.

share|improve this answer
    
how many terms of eq1 will I need to make it convergent on x $ in [1,2)$ –  gardian06 Mar 18 '12 at 18:48
add comment

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)$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

$$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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.