Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!mcnc!unc!rentsch
From: rentsch@unc.cs.unc.edu (Tim Rentsch)
Newsgroups: comp.arch
Subject: Re: chewing up mips with graphics [parallel computing]
Message-ID: <734@unc.cs.unc.edu>
Date: Thu, 2-Jul-87 18:21:28 EDT
Article-I.D.: unc.734
Posted: Thu Jul  2 18:21:28 1987
Date-Received: Sat, 4-Jul-87 08:07:29 EDT
References: <8270@amdahl.amdahl.com> <359@rocky2.UUCP> <338@astroatc.UUCP> <umn-cs.1683> <1331@ogcvax.UUCP>
Reply-To: rentsch@unc.UUCP (Tim Rentsch)
Organization: University of North Carolina, Chapel Hill
Lines: 66

In article <1331@ogcvax.UUCP> pase@ogcvax.UUCP (Douglas M. Pase) writes:
> One such problem (one which is serial) is the calculation of positive 
> integer powers.  The fastest method is as follows:
> 
> 	pow(b,i)	/* raise b to the ith power */
> 	{
> 		int j;
> 
> 		for (j=1; i; i>>=1) {
> 			if (i&1)	/* least significant bit is set */
> 				j *= b;
> 			b *= b;		/* square b */
> 		}
> 		return(j);
> 	}
> 
> If someone wants to quibble, the last multiplication (squaring 'b') could be
> removed by restructuring the code.  However, I have heard that this method
> has been proven to be faster than any parallel algorithm which computes the
> same function.

I don't know about faster than any parallel algorithm, but the given
algorithm is not the fastest possible, at least in terms of number
of multiplies.  Example:

	using the given algorithm takes 6 multiplies to compute
	x ** 15 (unquibbling the original multiply, and the last
	multiply), as in

			b		j
			-------		-------
			x		x
	(1)		x ** 2		
	(2)				x ** 3
	(3)		x ** 4
	(4)				x ** 7
	(5)		x ** 8
	(6)				x ** 15


	However, x ** 15 need take only 5 multiplies, as shown by:

			y		z
			-------		-------
			x		x
	(1)		x ** 2
	(2)		x ** 4
	(3)		x ** 5
	(4)				y ** 2  ( = x ** 10 )
	(5)				y ** 3  ( = x ** 15 )


Larger powers can be done in arbitrarily fewer multiplies than the
number used by the binary decomposition (given) method.  x ** 191 can
be computed with only 11 multiplies, but no fewer;  x ** 382 can also
be computed with 11 multiplies.  

I would love to say I thought up all this, but I didn't -- it's
from Knuth volume 2.

(And, I know this discussion should not continue on comp.arch --
followups please continue elsewhere.)

cheers,

Tim