Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!vrdxhq!verdix!ogcvax!pase
From: pase@ogcvax.UUCP (Douglas M. Pase)
Newsgroups: comp.arch
Subject: Re: chewing up mips with graphics [parallel computing]
Message-ID: <1331@ogcvax.UUCP>
Date: Wed, 1-Jul-87 16:47:56 EDT
Article-I.D.: ogcvax.1331
Posted: Wed Jul  1 16:47:56 1987
Date-Received: Sat, 4-Jul-87 06:33:40 EDT
References: <8270@amdahl.amdahl.com> <359@rocky2.UUCP> <338@astroatc.UUCP> <umn-cs.1683>
Reply-To: pase@ogcvax.UUCP (Douglas M. Pase)
Organization: Oregon Graduate Center, Beaverton, OR
Lines: 34

In article <umn-cs.1683> herndon@umn-cs.UUCP (Robert Herndon) writes:
> [...]
>  If you mean "ALL" problems, then I'd have to agree with you.
>There certainly are problems that seem to require a serial
>solution strategy.
> [...]
>
>-- 
>Robert Herndon				Dept. of Computer Science,
>...!ihnp4!umn-cs!herndon		Univ. of Minnesota,
>herndon@umn-cs.ARPA			136 Lind Hall, 207 Church St. SE
>herndon.umn-cs@csnet-relay.ARPA		Minneapolis, MN  55455

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.
--
Doug Pase   --   ...ucbvax!tektronix!ogcvax!pase  or  pase@Oregon-Grad (CSNet)