Web server info - 4.6.3 EVALUATION OF POWERS 443 The great calculator
4.6.3 EVALUATION OF POWERS 443 The great calculator al-Kashi stated Algorithm A about 1414 A.D. [Istorike Mat. IssledovaniG 7 (1954), 256-2571. The method is closely related to a proce- dure for multiplication that was actually used by Egyptian mathematicians as early as 1800 B.C.; for if we change step A3 to Y +-Y + 2 and step A5 to 2 +-Z + z , and if we set Y to zero instead of unity in step Al, the algorithm terminates with Y = nz. This is a practical method for multiplication by hand, since it involves only the simple operations of doubling, halving, and adding. It is often called the Russian peasant method of multiplication, since Western visitors to Russia in the nineteenth century found the method in wide use there. The number of multiplications required by Algorithm A is LlgnJ + y(n), where u(n) is the number of ones in the binary representation of n. This is one more multiplication than the left-to-right binary method mentioned at the beginning of this section would require, due to the fact that the first execution of step A3 is simply a multiplication by unity. Because of the bookkeeping time required by this algorithm, the binary method is usually not of importance for small values of n, say n 5 10, unless the time for a multiplication is comparatively large. If the value of n is known in advance, the left-to-right binary method is preferable. In some situations, such as the calculation of C? mod U(X) discussed in Section 4.6.2, it is much easier to multiply by z than to perform a general multiplication or to square a value, so binary methods for exponentiation are primarily suited for quite large n in such cases. If we wish to calculate the exact multiple-precision value of xn, when z is an integer > 1, binary methods are no help unless n is so huge that the high-speed multiplication routines of Section 4.3.3 are involved; and such applications are rare. Similarly, binary methods are usually inappropriate for raising a polynomial to a power; see R. J. Fateman, SIAM J. Computing 3 (1974), 196-213, for a discussion of the extensive literature on polynomial exponentiation. The point of these remarks is that binary methods are nice, but not a panacea. They are most applicable when the time to multiply xj . xk is essentially independent of j and Ic (e.g., for floating point multiplication, or multiplication mod m); in such cases the running time is reduced from order n to order logn. Fewer multiplications. Several authors have published statements (without proof) that the binary method actually gives the minimum possible number of multi- plications. But this is not true. The smallest counterexample is n = 15, when the binary method needs six multiplications, yet we can calculate y = x3 in Tao mul- tiplications and x l5 = y5 in three more, achieving the desired result with only five multiplications. Let us now discuss some other procedures for evaluating xn, for applications when n is known in advance (e.g., within an optimizing compiler). The factor method is based on a factorization of n. If n = pq, where p is the smallest prime factor of n and q > 1, we may calculate xn by first calculating xp and then raising this quantity to the qth power. If n is prime, we may calculate xnP1 and multiply by x. And, of course, if n = 1, we have xn with no calculation at all. Repeated application of these rules gives a procedure for evaluating xn,