From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Subject: Re: Can I compute a natural log? Date: 14 Aug 2000 19:29:21 -0400 Newsgroups: sci.math Summary: [missing] In article <8n9ske$mn6$1@nnrp1.deja.com>, wrote: : : :I'm trying to program a web page that requires a couple of natural logs, :and it appears that the available version of ASP (Visual Basic), which I :pretty much have to use, doesn't have a ln function. So I'm hoping to :find a formula I can use. : :On the web, I found a convenient Taylor series, but on further inspection :it looks like it doesn't converge if x > 1. For this purpose, x will be :way larger than 1. Can anyone suggest some kind of formula or algorithm? :how do calculators do it? : (You can get a wider, more experienced audience in sci.math.num-analysis) A crude solution (log means here natural logarithm): Suppose your arithmetical package has square roots (if it doesn't, it's time to upgrade). -- In fact, the absence of logarithms is also a strong hint. Given x>1, repeat taking square roots until y=sqrt(...sqrt(x)...) is <1.2; record n=(how many times you took these square roots). Then find t=(y-1)/(y+1), so that log(y) = log((1+t)/(1-t)). If 1 Subject: Re: Can I compute a natural log? Date: Tue, 15 Aug 2000 23:47:32 +0200 Newsgroups: sci.math jtanzer@my-deja.com schrieb in Nachricht <8n9ske$mn6$1@nnrp1.deja.com>... > > >I'm trying to program a web page that requires a couple of natural logs, >and it appears that the available version of ASP (Visual Basic), which I >pretty much have to use, doesn't have a ln function. So I'm hoping to >find a formula I can use. > >On the web, I found a convenient Taylor series, but on further inspection >it looks like it doesn't converge if x > 1. For this purpose, x will be >way larger than 1. Can anyone suggest some kind of formula or algorithm? >how do calculators do it? Scale the argument x as x = (2^k)*u, k integer, 0.5 <= u < 1 Let z = (u - w)/(u + w) with w = 0.707 106 781 19 Let y = z*( A + B*z^2 + C/(D - z^2) ) with A = 1.218 730 624 10 B = 0.107 642 740 19 C = 1.091 870 685 40 D = 1.397 559 816 20, then ln(x) = (k - 0.5)*0.693 147 180 56 + y with a relative error of ~ 10^-8 . (I hope there are no typos in the numbers ... ) Regards Hermann -- >Thanks, > >Joshua >jtanzer@deja.com > > >Sent via Deja.com http://www.deja.com/ >Before you buy. ============================================================================== From: Ronald Bruck Subject: Re: Can I compute a natural log? Date: Tue, 15 Aug 2000 22:04:58 -0700 Newsgroups: sci.math In article <8n9ske$mn6$1@nnrp1.deja.com>, jtanzer@my-deja.com wrote: :I'm trying to program a web page that requires a couple of natural logs, :and it appears that the available version of ASP (Visual Basic), which I :pretty much have to use, doesn't have a ln function. So I'm hoping to :find a formula I can use. : :On the web, I found a convenient Taylor series, but on further inspection :it looks like it doesn't converge if x > 1. For this purpose, x will be :way larger than 1. Can anyone suggest some kind of formula or algorithm? :how do calculators do it? Does it have an exponential function? If so, you could try applying Newton's method to solve exp(x) = c to get x = ln c. Let's see, that means you need to iterate the function g(x) = x - (exp(x)-c)/exp(x) = x - 1 + c * exp(-x). Four or five iterations ought to do it. There's another interesting trick, which only requires you to take square roots. It depends on the fact that d -- c^x = c^x ln c. dx As a consequence, 1/2^n c - 1 lim ---------- = ln c. n->oo 1/2^n You can compute the powers c^(1/2^n) by repeatedly extracting square roots. However, you have to do this cleverly, since there will be a loss of precision if you're careless. One way is to set a(0) = c-1, b(0) = c, then iterate b(n+1) = sqrt(b(n)), a(n+1) = 2a(n)/(1+b(n+1)). Then a(n) is the difference quotient 2^n (c^(1/2^n)-1) and therefore converges to ln c. This rearrangement is stable. Unfortunately, the convergence is only linear; it needs about twenty iterations to get ln 2 to six decimals. I remember seeing this in a lovely little book by Peter Henrici. Sigh. They're all disappearing :-( as I get older... --Ron Bruck -- Due to University fiscal constraints, .sigs may not be exceed one line. ============================================================================== From: Ronald Bruck Subject: Re: Can I compute a natural log? Date: Tue, 15 Aug 2000 22:32:09 -0700 Newsgroups: sci.math In article , Ronald Bruck wrote: :In article <8n9ske$mn6$1@nnrp1.deja.com>, jtanzer@my-deja.com wrote: : ::I'm trying to program a web page that requires a couple of natural logs, ::and it appears that the available version of ASP (Visual Basic), which I ::pretty much have to use, doesn't have a ln function. So I'm hoping to ::find a formula I can use. :: ::On the web, I found a convenient Taylor series, but on further inspection ::it looks like it doesn't converge if x > 1. For this purpose, x will be ::way larger than 1. Can anyone suggest some kind of formula or algorithm? ::how do calculators do it? : [content of my previous post deleted] After I posted I remembered a discussion in a paper by David Bailey on how he implemented the multiprecision logarithm in his MPFUN package (multi-precision for FORTRAN). I've extracted the relevant sections here (sorry for the TeX, and apologies for any copyright violation--but I think this falls within 'fair use'): :The advanced routine for log employs a quadratically convergent :algorithm due to Salamin, as described in \cite{brent3}. Inputs $t$ :that are extremely close to 1 are handled using a Taylor series. :Otherwise let $n$ be the number of bits of precision required in the :result. If $t$ is exactly two, select $m > n / 2$. Then the :following formula gives $\log 2$ to the required precision: :\begin{eqnarray*} :\log 2 &=& \frac{\pi}{2 m A (1, 4 / 2^m)} :\end{eqnarray*} : :\noindent :Here $A(a, b)$ is the limit of the arithmetic-geometric mean: let $a_0 := a$ and $b_0 = b$. Then iterate :\begin{eqnarray*} :a_{k+1} &=& \frac{a_k + b_k}{2} \\ :b_{k+1} &=& \sqrt{a_k b_k} :\end{eqnarray*} : :\noindent :For other $t$ select $m$ such that $s = t 2^m > 2^{n/2}$. Then the :following formula gives $\log t$ to the required precision: :\begin{eqnarray*} :\log t &=& \frac{\pi}{2 A (1, 4 / s)} - m \log 2 :\end{eqnarray*} : :The advanced routine for exp employs the following Newton iteration, :which converges to $e^t$: :\begin{eqnarray*} :x_{k+1} &=& x_k (t + 1 - \log x_k) :\end{eqnarray*} : :It might be mentioned that quadratically convergent algorithms for exp :and log were first presented by Brent in \cite{brent1}, and others :were presented in by the Borweins in \cite{borw1}. Based on the :author's comparisons, however, the Salamin algorithm is significantly :faster than either the Brent or the Borwein algorithm. For this :reason the Salamin algorithm was selected for inclusion in this :package. : The whole paper (A Portable High Performance Multiprecision Package, 1993) is available from David Bailey's web site. The citations are \bibitem{brent1} Brent, R. P., ``Fast Multiple-Precision Evaluation of Elementary Functions'', {\sl Journal of the ACM}, vol. 23 (1976), p. 242 -- 251. \bibitem{brent3} Brent, R. P., ``Multiple-Precision Zero-Finding Methods and the Complexity of Elementary Function Evaluation'', {\sl Analytic Computational Complexity}, Academic Press, New York, 1976, p. 151 -- 176. \bibitem{borw1} Borwein, J. M., and Borwein, P. B., ``The Arithmetic-Geometric Mean and Fast Computation of Elementary Functions'', {\sl SIAM Review} vol. 26 (1984), p. 351 -- 365. --Ron Bruck -- Due to University fiscal constraints, .sigs may not be exceed one line. ============================================================================== From: pete Subject: Re: Can I compute a natural log? Date: Wed, 16 Aug 2000 14:02:35 -0400 Newsgroups: sci.math jtanzer@my-deja.com wrote: > > I'm trying to program a web page that requires a couple of natural logs, > and it appears that the available version of ASP (Visual Basic), which I > pretty much have to use, doesn't have a ln function. So I'm hoping to > find a formula I can use. > > On the web, I found a convenient Taylor series, but on further inspection > it looks like it doesn't converge if x > 1. For this purpose, x will be > way larger than 1. Can anyone suggest some kind of formula or algorithm? > how do calculators do it? > > Thanks, > > Joshua > jtanzer@deja.com > > Sent via Deja.com http://www.deja.com/ > Before you buy. I like to record algorithms, in C code. For 80 bits of precission, the "while(x=c,a*=b,n+=2,c+=a/n,x!=c);" loop never executes more than 12 times. All positive numbers are equal to the product of (some number greater than sqrt(2)/2 and less than sqrt(2)) multiplied by (2, raised to some integer power). /* Ln.c */ #include #include long double Ln(long double x){ int n=0; long double a,b,c; static long double A,B,C; x>0||(printf("\"x\" must be greater than 0, for Ln(x) !\n"),exit(1),0); if(!A){ B=1.5; while(A=B,B=1/A+A/2,A!=B); B/=2,C=Ln(A); }/* A=sqrt(2), B=sqrt(2)/2, C=log(2)/2; */ while(x>A)x/=2,n++; while(x0 && printf("\nThe natural log of %Lf, is %Lf\n",x,Ln(x))); return 0; } -- pete