Monday, 4 March 2019

Log approximation

Something that I noticed when going through Olympiad questions. There is a common type of questions asking about particular properties of a big number. It can be the last few digits, the appearance count of some digits, sum of digits,...or the length of the number. Some(most) of them involves number theory (or nasty computer programming, if you are a fan of projectEuler), but the length of the number is usually calculated using log function.

Since log is such basic element in secondary education, such questions are accessible to most students. In fact, they appear frequently in one of Taiwan's university qualifying exam AST. You are given the value of log 2 and log 3, then you are required to approximate some logged numbers, without calculator of course.

Ironically when you are asked to approximate something that is not a multiple of 2, 3 and 5, the best approach is to go back to natural log...

Wait. The natural number e is irrational right? How can we approximate natural log without using calculator?

Let us define our rule before proceeding.

(1) The approximation log 2 ~= 0.30103 and log 3 ~= 0.44712 can be used. Here log always mean log base 10 and ln is the natural log.

(2) Arithmetic and integral powers may be used.

(3) Calculating the log function is not allowed, unless it is an approximation already made.


Consider the simplest non-trivial log-number.

Question: Approximate log 7. (A. 0.8450980...)

Solution 1. Approximate by the average of log 6 and log 8, which are products of 2 and 3s.

That gives 0.84062 with an error of 5% and is only correct to 1dp. Can we do better?

Solution 2. Observe that 7^2 = 49 is also sandwiched by two nice numbers, 48 and 50, so

$\log 7 \approx \frac{1}{4}(2+3\log 2+\log 3) \approx 0.84505$

That gives an error of 0.00005 and is accurate up to 4dp. That should be enough for most question.


But some are not satisfied, because there is no error analysis. We get the right answer because we calculate accurate enough, but we have no idea on why this is accurate enough. To do this we need can go back to our good ol' partner: the linear approximation. Derivative says

$\frac{d \log x}{dx} = \frac{1}{x \ln 10}$

so linear approximation says

$\log (x+a) \approx \log x + \frac{a}{x\ln 10}$

If you are using a calculator then it gives 0.84514... (both from 48 and 50), which is of the same accuracy as Solution 2. The problem to calculate ln 10?

The only way to do it is to compare the powers. We know we it is a bit more than 2, so we can prove something like

$\ln 10 > 2.2 \Leftrightarrow e < 10^5 e^{-10}$

Using the approximation $e\approx 2.71828$ we have $1.33 < 10e^{-2} < 1.36$, so $10^5e^{-10} > 1.33^5 > 4 > e$.

Similarly, we can prove $\frac{9}{4} < \ln 10 < \frac{7}{3}$. In fact, $\ln 10 \approx 2.302$, but it would be too hard to compare $e^{2.3}$ and $10$. Going back to our linear approximation. For the sake of killing off the denominator we multiply all terms by 50:

$50 \log 50 - \frac{50}{49 \ln 10} < 100 \log 7 < 50 \log 50 - \frac{1}{ \ln 10}$

Apply $\ln 10 > 2.25$ and $(\ln 10)^{-1} > 0.42857$ here:

$84.9485 - \frac{50}{49 \times 2.25} < 100 \log 7 < 84.9485 - 0.42857$

$0.8449499 < \log 7 < 0.8451993$

with a maximum error of 0.0001247. This is really accurate just by hand.

In a more general set up, one may argue that even calculating Taylor series by hand would be more accurate, but if you sense something nice about the number and its neighbors there is nothing bad on taking a shortcut.


Knowing the approximate value of ln 10, we can actually bound the error terms from the two solutions, still without calculator but rather painlessly.

Exercise:  Prove that in solution 2, the error is less than 0.0001. That is, to prove that

$| \log 7 - \frac{1}{4} (\log 48 + \log 50)| < 10^{-4}$.

Hint: when you apply linear approximation to get log 49 from either log 48 or log 50, both estimates are larger than the actual value. From there it suffices to find a quadratic error term that is accurate enough. Oh of course you may want to use calculus here :)


No comments:

Post a Comment