20
$\begingroup$

I'm thinking of making a table of logarithms ranging from 100-999 with 5 significant digits. By pen and paper that is. I'm doing this old school.

What first came to mind was to use $\log(ab) = \log(a) + \log(b)$ for reduction.
And then use the taylor series for $\log(1-x)$ when $-1 < x \leq 1$ But convergence is rather slow on this one.

Can you come up with a better method?

  • 0
    I very nearly needed to do this today when I forgot my calculator for a chemistry test, and was unable to borrow one. Fortunately the problems were all overcooked and I didn't need to use anything past long division, but you never know...2015-10-23

6 Answers 6

10

For $1 \le x \le 2$, $\begin{eqnarray*} \ln(x) &\approx - 1.941064448+ \left( 3.529305040+ \left( - 2.461222169+ \left( \right.\right.\right.\cr & \left.\left.\left. 1.130626210+ \left( - 0.2887399591+ 0.03110401824\,x \right) x \right) x \right) x \right) x \end{eqnarray*}$ with error less than $10^{-5}$. For $2^n \le x \le 2^{n+1}$, $\ln(x) = n \ln(2) + \ln(x/2^n)$.

  • 1
    Rounding the coefficients might introduce a little bit more error, but not much. In fact, -1.941064+(3.529305+(-2.461222+(1.130626+(-.288740+0.031104*x)*x)*x)*x)*x would make the maximum error just slightly greater than $10^{-5}$.2017-05-18
9

According to Wikipedia, http://en.wikipedia.org/wiki/Logarithm#Power_series, you can try $\ln(z)=2\sum_{n=0}^\infty\,\frac{1}{2n+1}\left(\frac{z-1}{z+1}\right)^{2n+1}$ And using that convergence is quickler for $z$ near to $1$, according to wikipedia for $z=1.5$ the first three terms of the series give an error of about $3\cdot 10^{-6}$.

6

Another way, appropriate for making a table, is to start with $\ln(100) = 4.605170186$, and then for each $n$, $\ln(n+1) \approx \ln(n) + \frac{1}{n} - \frac{1}{2n^2} + \frac{1}{3n^3}$. The accumulated truncation error (not counting roundoff) will always be less than $10^{-7}$.

6

EDIT: This is the short, streamlined version. My original answer is below, and the motivation, background, and error discussion can be found there.

  1. Find approximations for $\ln(1.00)$ to $\ln(2.00)$ iterating the argument by $0.01$. $\ln(1.00)=0$ $\ln(x+0.01)\approx\ln(x)+\frac{1}{600}\left(\frac{1}{x}+\frac{4}{x+0.005}+\frac{1}{x+0.01}\right)\qquad(1)$
  2. Find approximations for $\ln(2.01)$ to $\ln(3.00)$. If $\ln(x/2)$ is already tabulated, $\ln(x)=\ln(x/2)+\ln(2.00)$ Otherwise, use equation $(1)$.
  3. Find approximations for $\ln(3.01)$ to $\ln(5.00)$. If $\ln(x/2)$ or $\ln(x/3)$ is already tabulated, $\ln(x)=\ln(x/2)+\ln(2.00)\qquad\textrm{or}\qquad\ln(x)=\ln(x/3)+\ln(3.00)$ Otherwise, use equation $(1)$.
  4. Find approximations for $\ln(5.01)$ to $\ln(7.00)$. If $\ln(x/2)$, $\ln(x/3)$, or $\ln(x/5)$ is already tabulated, $\ln(x)=\ln(x/2)+\ln(2.00)\qquad\textrm{or}\qquad\ln(x)=\ln(x/3)+\ln(3.00)$ $\textrm{or}\qquad\ln(x)=\ln(x/5)+\ln(5.00)$Otherwise, use equation $(1)$.
  5. Find approximations for $\ln(7.01)$ to $\ln(10.00)$. If $\ln(x/2)$, $\ln(x/3)$, $\ln(x/5)$, or $\ln(x/7)$ is already tabulated, $\ln(x)=\ln(x/2)+\ln(2.00)\qquad\textrm{or}\qquad\ln(x)=\ln(x/3)+\ln(3.00)$ $\textrm{or}\qquad\ln(x)=\ln(x/5)+\ln(5.00)\qquad\textrm{or}\qquad\ln(x)=\ln(x/7)+\ln(7.00)$ Otherwise, use equation $(1)$.
  6. Now approximations for $\ln(1.00)$ to $\ln(10.00)$ are tabulated. Add $2\ln(10.00)$ to obtain a table of $\ln(100), \ln(101), \ldots, \ln(1000)$. Personally, I would leave the table with arguments from $1.00$ to $10.00$ and instruct the reader to add $\ln(10.00)$ as necessary.

This method uses equation $(1)$ roughly $100+50+33+33+27+27+23+23+23\approx340$ times. That means that you will do about $3(340)=1360$ divisions by numbers with at most four significant figures. You will divide by $600$ (comparatively simple) $340$ times. When you use equation $(1)$, you do $3$ additions, totalling about $1020$ additions. When you do not use equation $(1)$, you do addition once, and this happens about $900-340=560$ times. All together that's:

  • $1360$ divisions by numbers with at most 4 significant digits
  • $340$ divisions by $600$
  • $1580$ additions
  • no time-consuming multiplications or raising to powers, as most other methods involve

I think this is excellent considering that you will be producing $900$ numbers to five decimals of accuracy.


Original posted answer:

Here's an idea that has nothing to do with power series. First, read up on the Runge-Kutta method for approximating solutions to differential equations at http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods. Just stick to the "common fourth-order" method. Most introductory differential equations courses cover Euler's method, which is a great concept, but usually impractical for its slowness. Runge-Kutta works a lot faster.

$y=\ln(x)$ is the solution to the differential equation y'=\frac{1}{x} with initial condition $y(1)=0$. Apply Runge-Kutta with a step size of $0.01$ and iterate nine hundred times from $1.00$ up to $10.00$. You'll have approximate values for $\ln(1.01)$ up to $\ln(10.00)$. Then you can add the approximation for $\ln(10.00)$ (twice) to get approximations for $\ln(100)$ to $\ln(1000)$.

Error:

I do not know of any theorems for bounding the error with this method, but errors are usually very small in practice. I used Excel to do all of this, and the error on the final approximation for $\ln(10.00)$ was just less than $2.1\times10^{-11}$. If you did all of this by hand, then used some other method to find $\ln(10.00)$ with very high known precision, you could establish a bound on the error for $\ln(10.00)$. Then the monotonicity of $\frac{1}{x}$ would imply that all the errors on the intermediate steps were even smaller.

Complexity:

Given the specifics of this problem, each iteration will require you to do three decimal divisions by numbers that have at most four significant digits. (Note that since the differential equation is pure-time, $k2=k3$.) Each iteration will also have two doublings, several additions, and one division by 6, but the three decimal divisions will take most of your time. Also, each of these three quotients only gets used later in additions, doublings, and division by $6$, so I would bet that you would be safe recording only 7 decimals for each quotient. My feeling is that this will give you the results that you want much quicker than most methods based on power series. Just like this method, those require several divisions at each step. But power series methods also require raising to powers, and this method does not.

Improved Speed

To cut the computation time roughly in half, you could use some other method to find a decimal for $\ln(2)$ to high accuracy, and add use $\ln(2x)=\ln(x)+\ln(2)$. Specifically, after running Runge-Kutta ninety times up through $2.01$, you could approximate $\ln(2.02)$ with the approximations you have for $\ln(1.01)$ and $\ln(2)$. Alternate back to RK for $\ln(2.03)$, and continue alternating the methods. This would drop you from $900$ RK iterations down to $500$. Adding this modification to my Excel spreadsheet brought the final error on $\ln(10.00)$ up to a perfectly acceptable $7.1\times10^{-11}$.

  • 0
    @J.M.: I cannot see the article, but can you clarify what you mean? The only quantity that needs to be recalled to find, say $\ln(2.57)$ is $\ln(2.56)$. And the OP wants to have $\ln(2.56)$ recorded anyways as part of the final table. (That is, after adding $2\ln(10)$.) Is Gill's formulation trying to get to the end (that is, $\ln(10.00)$) with fewer steps in between? The OP wants a table of $900$ numbers no matter what the method.2019-05-12
1

If you want to make a table of natural logarithms, you could do it fairly effectively using Newton Raphson. For each x ∈ [100,999], choose an initial y0 ∈ (4.6, 6.9) to taste, and then iterate: $ y_{j+1} \;\;=\;\; y_j - \left[\dfrac{\exp(y_j) - x}{\exp(y_j)}\right] \;\;=\;\; y_j + x \exp(-y_j) - 1. $ The Taylor series for exp(−yj) should converge quickly, unlike that of ln(1 − yj). For base 10 logarithms, you can do the conversion by dividing your natural logarithms by ln(10), which you can also find quickly by the above method.

  • 0
    @Michael Hardy: good point; but he can convert by dividing by ln(10) throughout, which is similar to a computation he would have to do with a direct Talyor series computation anyhow.2011-09-01
1

Making a log table by pen and paper is not for the faint of heart; you must have perfect accuracy. I recommend pencil, eraser, and paper.

All of the above methods are great for natural logs, but to get logs to base 10, you must divide each by the natural log of 10. That's no fun. I would try to get logs to base ten directly by Euler's method of finding upper and lower bounds that have known logs, so you have an upper and lower bound for the log. Then bisect that interval for the logs by taking the arithmetic mean and for the argument by taking the geometric mean. You have to be quick and accurate at taking square roots like Euler.

You could build a table of certain logarithms: 10^(-1/2), 10^(-1/4), etc. Twenty such entries would allow you to calculate logs to 5 places by multiplying your target number by the appropriate power of ten and adding the negative of that log to the total. You could probably use two soroban: one for the division, and one to accumulate the log.

Another method is to square the argument, and if greater, divide by 10 if the result is greater than ten. When you divide by 10, append a binary 1 to the log (which is represented in binary), otherwise, append a binary 0. Knuth has a discussion of this in chapter 1 of Fundamental Algorithms and gives the breakdown of the squaring method as a problem for the student.

I would start with the first few prime numbers, then use those to build the logs of the other numbers. For a number x that you cannot factor, find a nearby number y that you can factor. Then calculate Ln(x/y) by a power series. A really good one is the Pade approximation Ln(x+1)=x(6+x)/(6+4x). The smaller x, the better the approximation. Then multiply this by the log(e) = .4342944819. Add that to the log of the nearby number, and you will have it. Of course it is helpful to memorize a few things to ten or more places. I would start with the logs of 2, e, 3, and 7. (The logs of 4, 5, 6, 8, and 9 can be computed from these).

There are some other marvelous Pade approximations using the transformation y = (x-1)/(x+1). The simple approximation Ln(x) = 2y is amazingly good, but with a Pade approximation like 2y*N(y)/D(y), where N and D are polynomials, you can do amazingly well. (but you still have to multiply the result by Log(e))

Another approach is one I got from Nate Grossman of UCLA. As you know, the arithmetic-geometric mean algorithm converges quadratically. Here is a variant:

a(0) = 1, g(0) = x, thereafter, a(1+j)=(a(j)+g(j))/2 and g(1+j)=sqrt(a(1+j)g(j))

Note the slight difference from the standard AGM formula. The a's and g's converge to a common limit, but not quadratically. You can use Richardson extrapolation to speed convergence. The limit is d, and (x-1)/d is your approximant for the natural log. This was a popular method in the Forth Interest Group.

Hope I gave you some ideas. Creative factoring can greatly extend the first few simple results.

. . . Richard

Have fun!