1
$\begingroup$

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.

  • 0
    @gardian06 From your comment I'm going to presume that you're trying to essentially solve some differential equations-of-motion with frictional drag under variable frame rates, in which case I think you're solving exactly the wrong problem here by taking the exponential approach you're trying here - there are much better ways of doing this. I'd heartily encourage posting your _original_ problem ('how do I simulate this motion?') to something like the gamedev stackexchange site; you'll get much better answers to your real question than you're likely to get from this approach.2012-03-18

4 Answers 4

1

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.

  • 0
    how many terms of eq1 will I need to make it convergent on x $ in [1,2)$2012-03-18
1

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

1

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.

0

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