Log approximation 2: analytical approach

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.

19/5/2025: 千年之別

中學時被教過仲夏夜是五月夜，但我只知道北半球的五月熱得讓我失眠。

「又失眠了……」我嘀咕著，一邊把冷氣打開。思緒卻沒切回到睡覺模式，只是停留在剛剛夢到某本十幾年前追過的同人作品。

那是極其稀有的、以祖世代為引子的非現世穿越同人。

大家都知道子世代本傳的漏洞太多太多，到今天我看這本祖世代同人才又發現一個。這個漏洞很容易被忽略，連我看MWPP這本親世代巨著都沒發現，不過一但發現了又令人難以忘懷：劫盜地圖的材質。

先不說這四人有沒有可能在四年級前後就探清學校「所有」結構並開始製作如此高深的魔法物件，這東西這麼好用最少也得人手一件吧？為甚麼沒有這樣做？又或者，這麼高深的魔法真的是普通物件能承載的嗎？如果羊皮紙本身是特殊的，那麼他們能做出這地圖也比較合理了。這本祖世代同人覺得這張羊皮紙說不定可以直接追溯到祖世代時期，聽上去也不是不可能。

哈利世界觀的問題是祖世代和現代中間的缺失太多了，而且中間「甚麼事都沒發生」這點就跟中學歷史老師跟你說中世紀的歐洲人混沌地混了一千年一樣荒誕。中間就沒有人有好奇心探索學校祕密嗎？就沒人成績比MWPP優秀？沒有人哪怕接近四巨頭的遺產？他們的初代學生呢？基本上本傳所有秘密要不出自祖世代，要不出自親世代，當我們就這不合理溯本追源時卻被告知中間的一千年都是混沌、不可知的，這實在難以使我這種讀者信服。還有那比四巨頭更早的時代呢？亞瑟王是個魔法師嗎？那個卑鄙的海爾波是希臘人吧，那魔法史怎不能再往前推幾百年？還是說，這些都像現實中同時期的威爾斯史一樣已經佚散到找不回來的程度了嗎－－

正因為如此，我才會對那些專攻舊世代的同人如此感興趣。不是為尋找「正確」的答案，而是為看別人的推敲過程，就像小市民一樣。

我還有很多問題想問。比如帷幕、比如索命咒的本質(cf那隻為課堂而犧牲的蜘蛛)……我越是用力思考，在被窩裡就更覺燥熱。即使打開了冷氣也沒用，被子裡累積的熱量可沒那麼容易散去。

……好可惜啊。

現實網絡已找不到那篇原文，再下一次夢到這文不知道是何年何月了……