[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

29.0. "Efficient Raising to Powers" by HARE::STAN () Sun Feb 05 1984 13:51

In the November 1983 issue of The Fibonacci Quarterly, Philip Mana
asked, in problem B-484, for the least number of multiplications
needed to calculate x^98.  A solution was printed by Walther Janous,
wherein he states that the minimum number of multiplications needed
is 8 (this is correct).  However, he then goes on to state (without
proof) that if the binary representation of n is

		a  a     ... a  a  a
		 k  k-1       2  1  0

then the minimum number of multiplications needed to compute x^n
is k-1 plus the number of 1 bits in the binary representation of n.
(98=2^6+2^5+2^1, so answer is 6-1+3=8).  THIS IS INCORRECT.

Find the smallest counterexample.

T.R	Title	User	Date	Lines
29.1		AURORA::HALLYB	`Sun Feb 05 1984 14:20`	1
	Is a "shift" operation considered a multiplication?
29.2		HARE::STAN	`Sun Feb 05 1984 16:52`	28
	x is considered arbitrary and only multiplications are permitted. For example, x^98 is computed by the following 8 multiplies: operation comment --------- ------- y1=xx x^2 y2=y1y1 x^4 y3=y2y2 x^8 y4=y3y3 x^16 y5=y4y4 x^32 y6=y5y5 x^64 y7=y6y5 x^96 y8=y7y1 x^98 y8 is the desired result. I don't believe shifts are relevant to the question posed. This algorithm is important to compilers that wish to generate in-line code for computing small integer powers of integer variables. The algorithm used above (for exponent 98) is the binary multiplicative algorithm. This is not always the most efficient algorithm (as is mistakenly believed by some). I am asking for an example that shows that this algorithm is not always best. It would be interesting to see if our compilers do this right. I took a look at the VAX-11 FORTRAN compiler, but found that it called OTS$POWJJ to do the exponentiation.
29.3		AURORA::HALLYB	`Sun Feb 05 1984 20:34`	13
	Operation Comment --------- ------- y1=xx x^2 y2=xy1 x^3 y3=y2y2 x^6 y4=y2y3 x^9 y5=y4y4 x^18 y6=y4y5 x^27 Now 27 = 11011, so the "theorem" says we we need 4-1+4=7 multiplies. 2 Clearly 6 suffices, but I don't know the general algorithm.
29.4		NEWTON::LARY	`Mon Feb 06 1984 22:02`	19
	Using the notation of the previous examples: Operation Comment --------- ------- y1=xx x^2 y2=y1y1 x^4 y3=xy2 x^5 y4=y3y3 x^10 y5=y3*y4 x^15 But 15 = 1111 which would yield 6 multiplies. 2 One way of stating a more general algorithm is that whenever the exponent is factorable we may "nest" the applications of the algorithm; i.e. by computing x^(ab) as ((x^a)^b) or ((x^b)^a), whichever is better. It is pretty obvious that if one of the factors is a power of two this reduction accomplishes nothing, but 3 yields good results....
29.5		TURTLE::GILBERT	`Tue Feb 14 1984 18:27`	19
	The smallest power for which the binary method fails is 15. "The factor method is based on a factorization of n. If n = p*q, wgere p is the smallest prime factor of n, and q > 1, we may calculate x^n by first calculating x^p and then raising this quantity to the qth power. If n is prime, we may calculate x^(n-1) and multiply by x. And, of course, if n = 1, we have x^n with no calculation at all. Repeated applications of these rules gives a procedure for evaluating x^n, for any given n." "The factor method is better than the binary method on the average, but there are cases (n = 33 is the smallest example) where the binary method excels." from "The Art of Computer Programming", Donald E. Knuth, Vol.2, p.401 The text continues (for about 18 pages) with more powerful methods of reducing the number of multiplications required to evaluate powers. - Gilbert P.S. Eight multiplications are required for x^98.