I have a problem trying to create a function in a programming language that does not support any functions other than that of basic arithmetic (addition, subtraction, exponentiation, division...). This function should replicate that of the natural logarithm, or $\ln(x)$ function. Currently, I have $e=\sqrt[y]{x}$ (from $e^y=x$). As of now, I have not found any way to isolate $y$ in that equation without also using the $\log()$ function. Is this possible to do without using said function? Once I have the $\ln(x)$ function, I can construct the $\log_{base}(x)$ function as $$\log_{base}(x)=\dfrac{\ln(x)}{\ln(base)}.$$ And, with the Taylor series, I can create dynamic functions for $\sin,\cos,$ and $\tan$ as well as there inverses. From there, I've got a more or less functional programming space.
Answer
Obviously, since $y=\ln(x)$ is the solution, this is equivalent to writing $\log$ in terms of "elementary" functions. This can't be done - a simple argument to this fact would be that there is no way to, in terms of the map $x\mapsto e^x$ and rational functions, create a function tending to infinity, but having vanishing derivative. (A more sophisticated argument could proceed by noting that $\ln(x)$ is as "well-defined" as the other operations, since $\ln(1)$ could be argued to be $2\pi i$ since $e^{2\pi i}=1$ - then tossing the word "holomorphic" around a few times, we'd get a result).
However, if you're okay with Taylor series, then the following may be useful:
$$\ln(x+1)=x-\frac{x^2}2+\frac{x^3}3-\frac{x^4}4+\frac{x^5}5+\ldots$$
and, if you want to limit the number of terms you must compute, you could compute, for instance, $\alpha=\sqrt{e}$ (or a higher root; you just need to be able to precompute $\ln(\alpha)$ and, before computing $\ln(x)$ multiply by $\alpha^n$ for an integer $n$ such that $x$ is in $[\alpha^{-\frac{1}2},\sqrt{\alpha})$ - that is, let $x=y\alpha^n$ where $y$ is in that interval, then $\ln(x)=\ln(y\alpha^n)=\ln(y)+n\ln(\alpha)$ and if you use the Taylor series for $\ln(y)$ near $y=1$, you should be able to get reasonable accuracy on any input, since you're only using the Taylor series in a relatively small interval.
Another method would be to abuse the identity $\ln(x^a)=a\ln(x)$ and to use a linear approximation of $\ln$ In particular, if you chose some large integer $n$, then you could compute
$$\ln(x)=n\ln(\sqrt[n]x)\approx n(\sqrt[n]x-1).$$
You could also use Newton's method or something similar to numerically solve the equation - you could use one of the above methods to approximate a good place to start, and then iterate Newton's method until you reach acceptable accuracy.
No comments:
Post a Comment