[1] More precisely, the number of multiplications required is equal to 1 less than the log base 2 of $n$, plus the number of ones in the binary representation of $n$. This total is always less than twice the log base 2 of $n$. The arbitrary constants $k_1$ and $k_2$ in the definition of order notation imply that, for a logarithmic process, the base to which logarithms are taken does not matter, so all such processes are described as $\Theta(\log n)$.
[2] You may wonder why anyone would care about raising numbers to the 1000th power. See section 1.2.6.
[3] This iterative algorithm is ancient. It appears in the Chandah-sutra by Áchárya, written before 200 b.c. See Knuth 1981, section 4.6.3, for a full discussion and analysis of this and other methods of exponentiation.
[4] This algorithm, which is sometimes known as the Russian peasant method of multiplication, is ancient. Examples of its use are found in the Rhind Papyrus, one of the two oldest mathematical documents in existence, written about 1700 b.c. (and copied from an even older document) by an Egyptian scribe named A'h-mose.
[5] This exercise was suggested to us by Joe Stoy, based on an example in Kaldewaij 1990.
1.2.4 Exponentiation