Written by Colin+ in arithmetic, logarithms.
Some time ago, someone asked Uncle Colin what the last two digits of $19^{1000}$ were. That caused few problems. However, Mark came up with a followup question: how would you estimate $19^{1000}$?
I like this question, and set myself some rules:
[I will, however, put some refereetype comments in square brackets as commentary on the work, but not as part of it.]
I did the 'obvious' thing at first, and said "$20^{1000} = 2^{1000} 10^{1000} \approx 10^{300} 10^{1000} = 10^{1300}$". I could then use some adjustments:
$\left(1 + \frac{6}{250}\right)^{100} = \left( \left( 1+ \frac{6}{250}\right)^\frac{250}{6} \right)^{2.4} \approx e^{2.4}$  which is a factor of about 10, so $20^{1000} \approx 10^{1301}$.
However, we want $19^{1000}$, which is that multiplied by $(0.95)^{1000}$, or $\left(1  \frac {1}{20}\right)^{1000} = \left( \left( 1  \frac1{20} \right)^{20} \right)^{50} \approx e^{50}$. Because $50 \div 2.3 \approx 21.7$, that's an adjustment of about $2 \times 10^{22}$, giving an estimate of $2 \times 10^{1279}$.
[That's not bad  the real answer is $5 \times 10^{1278}$; off by a factor of 4, which is actually pretty good.]
Rough stuff is all well and good. What if we want an answer correct to several significant figures? That's going to require some careful logarithm calculation.
The plan of attack is to work out $1000 \ln(19)$, casting out powers of 10 as much as possible, and then get something relatively small and simple to take the exponential of in the end. Ready?
$\ln(19) = \ln\left( \frac{19}{20} \right) + \ln(20)$, obviously.
So, how to get $\ln\left( \frac{19}{20} \right)$? There's a Taylor expansion for that.
$\ln\left( \frac{19}{20} \right) =  \frac{1}{20}  \frac{1}{2 \times 20^2}  \frac{1}{3 \times 20^3} ...$
Setting it out carefully, ditching the minus sign, and doing everything to 12dp, that gives:
$\frac{1}{20} = 0.05$  0.05 

$\frac{1}{20^2} = 0.002 5$  $\frac{1}{2\times 20^2}=$  0.001 25 
$\frac{1}{20^3} = 0.000 125$  $\frac{1}{3\times 20^3}=$  0.000 041 666 667 
$\frac{1}{20^4} = 0.000 006 25$  $\frac{1}{4\times 20^4} = $  0.000 001 562 5 
$\frac{1}{20^5} = 0.000 000 312 5$  $\frac{1}{5\times 20^5} = $  0.000 000 062 5 
$\frac{1}{20^6} = 0.000 000 015 625$  $\frac{1}{6\times 20^6}=$  0.000 000 002 604 
$\frac{1}{20^7} \approx 0.000 000 000 781$  $\frac{1}{7\times 20^7}=$  0.000 000 000 112 
$\frac{1}{20^8} \approx 0.000 000 000 039$  $\frac{1}{8\times 20^8}=$  0.000 000 000 005 
Adding up that last column gives 0.051 293 294 388.
[Spot on.]
So, now what? We're after $1000 \ln\left( \frac{19}{20} \right) + 1000 \ln(20)$. Let's split that second term up as $1000 \ln(2) + 1000 \ln(10)$; the $\ln(10)$ bit is of no interest to us, as we're getting rid of powers of 10; instead, let's focus on the $1000 \ln(2)$.
We can rewrite that as $100 \ln \left( 2^{10} \right) = 100 \ln(1024) = 100 \ln( 1.024 ) + 300 \ln(10)$  and again, the $\ln(10)$ bit is of no interest. What's $\ln(1.024)$? Time for another table, using $\ln(1+x) = x  \frac 12 x^2 + \frac 13 x^3  ...$ :
$x = 0.024$  0.024 

$x^2 = 0.000 576$  $\frac 12 x^2 =$  0.000 288 
$x^3 = 0.000 013 824$  $\frac 13 x^3 =$  0.000 004 608 
$x^4 = 0.000 000 331 776$  $\frac 14 x^4 = $  0.000 000 082 944 
$x^5 \approx 0.000 000 007 963$  $\frac 15 x^5 = $  0.000 000 001 593 
$x^6 \approx 0.000 000 000 019$  $\frac 16 x^6 = $  0.000 000 000 032 
That comes out to be 0.023 716 526 617 [again, bang on].
Now to put it all together: $1000 \ln\left( \frac{19}{20} \right) + 100 \ln(1.024) + 1300 \ln(10) \approx 51.293 294 388 + 2.371 652 6617 + 1300 \ln(10) = 1300 \ln(10) 48.921 641 726$.
Goodo. Now, how do we turn $e^{48.9}$ into something that we can read off? We already know that's about $10^{21}$, but there's not much sense in getting 9 decimal places of accuracy and then saying "it's about...". It would be really handy to know $\ln(10)$!
We do have one good bit of information already: $10 \ln(2)  3\ln(10) = 0.023 716 526 617$. That's nice: if we can get something else that links $\ln(2)$ and $\ln(10)$ (or either value), we can solve a simultaneous equation!
Our best bet looks like $\ln(0.8)= 3\ln(2)  \ln(10)$, which converges painfully slowly. At least, it's painfully slow if you don't have a trick up your sleeve, and guess what? I do!
$\ln\left(\frac{4}{5}\right) = \ln\left( \frac{1  \frac{1}{9} }{1 + \frac{1}{9} }\right)$. And $\ln \left( \frac{1x}{1+x} \right) = \ln(1x)  \ln(1+x)$. Looking at the expansions:
$\ln(1x) = x  \frac 12 x^2  \frac 13 x^3  ...$
$\ln(1+x) = x  \frac 12 x^2 + \frac 13 x^3  ...$
So $\ln \left( \frac{1x}{1+x} \right) = 2x  \frac23 x^3  \frac 25 x^5  ...$, which converges much more quickly than the 'regular' way.
One more table: let's find $\frac 12 \ln(0.8)$
$x \approx 0.111 111 111 111$  0.111 111 111 111 

$x^3 \approx 0.001 371 742 112$  $\frac 13 x^3 =$  0.000 457 247 371 
$x^5 \approx 0.000 016 935 078$  $\frac 15 x^5 =$  0.000 003 387 016 
$x^7 \approx 0.000 000 209 075$  $\frac 17 x^7 =$  0.000 000 029 868 
$x^9 \approx 0.000 000 002 581$  $\frac 19 x^9 =$  0.000 000 000 287 
$x^{11} \approx 0.000 000 000 032$  $\frac 1{11} x^{11} =$  0.000 000 000 003 
These add up to 0.111 571 775 655, so $\ln(0.8) \approx 0.223 143 551 310$ [Boom.]
So, we have (if $t = \ln(2)$ and $T = \ln(10)$):
$10t  3T = 0.023 716 526 617$
$ T  3t = 0.223 143 551 310$
Trebling the second:
$10t  3T = 0.023 716 526 617$
$3T  9t = 0.669 430 653 930$
$t = 0.693 147 180 547$ [That's only good to 10dp. Shocking!]
However, we want $T$:
$T  3t = 0.223 143 551 310$
$3t = 2.079 441 541 641$
$T = 2.302 585 092 951$ [10dp again.]
All we need to do now is work out 48.921 641 726 divided by $\ln(10)$! In fact, we don't even need to do a full division, we just need to take some powers of 10 out and try to end up with a smaller number to put in the exponential.
With that in mind, $20 \ln(10) = 46.051 701 859 2$, meaning we've got $1000\ln(19) = 1280\ln(10)  2.869 939 867$. We can even get rid of another $\ln(10)$, and end up with $1279\ln(10)  0.567 354 774$.
It turns out, though, we can make that loose number even smaller: in the simultaneous equation bit, we chanced on $\ln(2)$, which is handy here: we can rewrite it as $1279\ln(10)  \ln(2) + 0.125 792 406$
Now we're getting somewhere! This means we can write $19^{1000} \approx 5 \times 10^{1278} \times e^{0.125 792 406}$. That last bit is what's going to give us the significant figures.
Let's try $e^{\frac 18}$, as that seems easy enough: $e^x \simeq 1 + x + \frac 12 x^2 + \frac 16 x^3 + ...$
$e^{\frac 18} \approx 1 + \frac 18 + \frac{1}{128} + \frac {1}{3072} + \frac{1}{98304}... =$
, to a completely unjustified 9dp [It's good to 6.]. Let's roll with it, though: the 5 becomes 5.665 741. We can then multiply this by $e^{0.000 792 406}$, which I'm going to call 1.0008, since this is already turning into a book. That's an extra 0.004 526, making 5.670 267.
1.125
+0.007 812 5
+0.000 325 521
+0.000 010 173
=1.133 148 194
My estimate of $19^{1000}$ is $5.670 267 \times 10^{1278}$.
[The correct answer is $5.670 232 \times 10^{1278}$. I'm right to four significant figures (one part in 162,000), which is a win. My logarithm is correct to one part in 476 million, which is pretty lovely.]
* If you can spot anywhere I've messed up, or an easy place to improve the estimate, I'd love to hear about it!
* Edited 20160502 to fix LaTeX and formatting errors. Thanks to @christianp for pointing them out!