This is a sequel to my previous entry on approximating log values without calculators.
Why would I revive such a primitive topic? These questions certainly won't appear at high level Olpmpiads anyway. Well, when I came across to questions like this I always like to flex a bit. On top of that, the last entry was in 2019: six years later let us revisit the question from a higher perspective.
So yeah, let us forget about calculators and have fun with numbers. Also, log always refer to log base 10.
Problem 1. Find the first 2 digits of $A = 41^{25}$.
Recall the few well known log constants: $\log 2 \approx 0.30103$, $\log 3 \approx 0.47712$, and $\log 7 \approx 0.84510$. The last one might be less familiar but shouldn't be too hard to approximate up to good precision (which I demonstrated in my previous entry).
From here you know $\log 40 = 1+2\log 2 \approx 1.60206$ and $\log 42 = \log 2 + \log 3 + \log 7 \approx 1.62325$, so $\log 41 \approx 1.612655$. Now $\log A = 25 \log 41 \approx 40.316375$, which we only care about the decimals.
How do we compute $10^{0.316375}$? Well we don't even need to. Note that $\log 20 < 1.316375 < \log 21$ which shows that the first two digits are 20.
Now, what if the question asks the first 3 digits of $41^{2025}$? You may try but the above trick fails simply due to lack of precision. 5 decimal places aren't enough when you are going to multiply with 2025 and ask for 3 digits precision (recall the asymptotics of log).
In order to have a glimpse on the precision we need, let us consider the original problem again but with a twist -- we want to do it rigorously.
Problem 2. Find the first 2 digits of $A = 41^{25}$, provided that $\log 2 \approx 0.30103$, $\log 3 \approx 0.47712$, $\log 7 \approx 0.84510$, $\ln 10 \approx 2.30259$ are accurate up to 5 decimal places.
We can express the upper and lower limit of our approximations as follows:
$\log 2 \in (0.301025, 301035)$
$\log 3 \in (0.477115, 0.477125)$
$\log 7 \in (0.845095, 0.845105)$
$\log 40 = 1+2\log 2 \in (1.60205, 1.60207)$
$\log 42 = \log 2 + \log 3 + \log 7 \in (1.623235, 1.623265)$
What about the possible range of $\log 41$?
Surely we have $\log 41 > \frac{1}{2}(\log 40 + \log 42) \geq 1.612642$ by convexity but the upper bound is less obvious and we need the power of calculus again. Note that
$\ln x^2 = \ln (x^2-1) + \ln (1 + \frac{1}{x^2-1}) \leq \ln (x^2 - 1) + \frac{1}{x^2-1}$.
Here the constant $\ln 10$ kicks in:
$\log 41 \leq \frac{1}{2}(\log 40 + \log 42 + \frac{1}{1680\ln 10}) \leq 1.612798$.
Gathering the bounds we have
$\log 41 \in (1.612642, 1.612798)$.
Notice how the gap suddenly widens with a single log interpolation.
From here we multiply and get
$\log A \in (40.31605, 40.31995)$.
Since $\log 21 = \log 3 + \log 7 > 1.32223$, we know that $A$ must start with 20.
Our approximation almost failed! I made a mistake and forgot to halve the difference $\frac{1}{1680 \ln 10}$. With that mistake the upper bound of $\log A$ would exceed 40.323 failing the argument. The fact that the actual value of $A$ starts with 2087... only makes it worse.
*
Not enough?
Then how about doing the calculation from scratch, without the assumption of the log constants?
Problem 3. Estimate $\ln 2$ up to 5 decimal places. (0.693147...)
There are so little we can do without advanced calculations:
- One may think about Newton's method but forgetting we can't calculate exponents.
- One may also think about the series of $\log (1+x)$, but the expansion at $x=1$ converges too damn slow (we need like a million terms...).
- We can also try $x = \sqrt{2}-1$ for $\ln \sqrt{2}$ hoping for quicker convergence. It indeed converges quickly but $\sqrt{2}$ is simply another nasty number to approximate. We could group the positive and negative terms and find the sum separately but then we run into hyperbolic inverse trigonometric functions (!!).
- Back to basic we have the integration $\ln 2 = \int ^2_1 x^{-1}dx$, but the problem what kind of partition do we need for such precision? Say, the upper bound is by tripizodal estimation and the lower bound by rectangular estimation. Assume a uniform partition of $N$ parts. Then the error is given by
$E = \sum \frac{1}{2}(\frac{1}{x_i}-\frac{1}{x_i+N^{-1}}) \cdot \frac{1}{N} \geq \frac{1}{2(N+1)}$.
And to have a $N$ large enough for $E< 10^{-5}$ is just...ridiculous for manual computation.
Is all hope lost? Not yet. We need a series that projects $(0,1)\mapsto (1,\infty)$ so that we can enjoy geometric convergence. What's better than the series $\ln \frac{1+x}{1-x} = 2 \sum _{k=0}^{\infty}\frac{x^{2k+1}}{2k+1}$? The value of $\ln 2$ corresponds to $x = \frac{1}{3}$ and a quick convergence is guaranteed.
We compute the first five terms:
$\ln 2 \approx 2\cdot (\frac{1}{3} + \frac{1}{81} + \frac{1}{1215} + \frac{1}{15309} + \frac{1}{177147}) = \frac{4297606}{6200145} \geq 0.693146$.
The above is taken as a lower bound. As for the upper bound, we loosely say that sum of the tail is less than, say 1.5 times the first remainder term, i.e. $3 \cdot (3^{11} \cdot 11)^{-1} \leq 2 \times 10^{-6}$, meaning that $\ln 2 \leq 0.693148$. Therefore the approximation $0.69315$ is accurate up to 5 decimal places.
What about $\ln 7$ then? We can easily estimate that using $\ln 7 = \ln 8 + \ln \frac{7}{8}$ with the help of the series of $\ln (1-x)$, but the brilliance of AI kicks in: we can also flip that into $-\ln \frac{8}{7}$ and apply the series of $\ln \frac{1+x}{1-x}$ again. We would end up with a smaller ratio, hence quicker convergence.
I am not going to do all the calculations, and I am not going to ask you to try as well -- knowing how is far more important than being able to, especially when you know you actually have more tools around than simple calculators.
Lessons for today is ummm...I guess...there was a reason behind why people needed slide rule or log tables?
No but seriously, the same question can be asked for many common functions and have very practical applications (except that we loosen the scope from hand computable to quick algorithm for computers).
According to Wikipedia, the last series approximation for log is indeed accepted as an accurate and quickly converging approach in approximating log values. Of course there are other perhaps better approach like the use of AG-mean, but that is out of the scope of manual calculation. The only other possible mean by hand that never came to my mind is the use of Padé approximant, as laid out in this MSE question, which looks pretty accurate too.
No comments:
Post a Comment