Calculating without electricity

A transformer in my neighborhood blew sometime in the night and my electricity was off this morning. I thought about the post I wrote last night and how I could have written it without electricity.

Last night's post included an example that if n = 8675309, n! has 56424131 digits, and that the last 2168823 digits are zeros. The previous post shows how you could compute the number of trailing zeros by hand. This post how you might compute the number of digits in n! by hand using only copy of Abramowitz and Stegun (A&S).

As shown here, the number of digits in n! is given by

log₁₀ n! + 1

which you could compute in Python as

 floor( gammaln(n+1)/log(10.0) ) + 1

A&S has tables of the log gamma function, but only for integer arguments up to 100. You're not going to compute log gamma of 8675310 that way. Instead, you'd want to use Stirling's approximation

log n! (n + 1/2) log(n+1) - n - 1 + log(2)/2.

Now we're after the log base 10 of (n + 1), which we could compute by finding the natural log and dividing by the natural of 10, as we did in the Python code above. But we could save a division by making a log base 10 version of Stirling's approximation:

log₁₀ n! (n + 1/2) log₁₀ (n+1) - (n+1) log₁₀(e) + log₁₀(2)/2

We can look up logarithms base 10 of e, 2, and in A&S on pages 2 and 3. The hard part is computing the log base 10 of 8675310.

A&S has tables of logarithms base 10 (common logarithms") for integer arguments up to 1350. We can find on page 98 that

log₁₀ 867 = 2.9380190975
log₁₀ 868 = 2.9385197252

We could linearly interpolate between these to estimate

log₁₀ 867.5310 2.9380190975 + 0.5310(2.9385197252 - 2.9380190975) = 2.9382849308

and so

log₁₀ 8675310 4 + 6.9382849308 = 6.9382849308.

Now we have all we need to estimate log₁₀ (8675310) as

8675909.5 * 6.9382849308 - 8675310 * 0.4342944819 + 0.5*(0.3010299957 + 0.4971498727) = 56428293.28.

From this we estimate that n! has 56428294 digits. The exact answer is 56424131, so our answer is correct to four significant figures.

The post Calculating without electricity first appeared on John D. Cook.