[net.lang.c] non-built-in exponentiation

gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/16/86)

/*
	LPow -- long exponentiation (no overflow detection)

	last edit:	86/06/16	D A Gwyn

	SCCS ID:	@(#)lpow.c	1.1
*/

long
LPow( base, exponent )			/* returns base^exponent */
	register long	base;
	register long	exponent;
	{
	register long	result;		/* result accumulator */

	/* handle simple special cases separately: */

	if ( base == 0 )
		return 0;		/* exp. < 0 should be EDOM */
	else if ( base == 1 )
		return 1;
	else if ( base == -1 )
		return exponent % 2 == 0 ? 1 : -1;
	else if ( exponent < 0 )
		return 0;

	/* general case with exponent >= 0: */

	result = 1;

	for ( ; ; )	/* LOOP INVARIANT: result*base^exponent */
		{
		if ( exponent % 2 != 0 )
			result *= base;

		if ( (exponent /= 2) == 0 )
			break;		/* result now stable */

		base *= base;
		}

	return result;
	}

levy@ttrdc.UUCP (Daniel R. Levy) (06/22/86)

In article <1371@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes:
>/*
>	LPow -- long exponentiation (no overflow detection)
>	last edit:	86/06/16	D A Gwyn
>	SCCS ID:	@(#)lpow.c	1.1
>*/
>long
>LPow( base, exponent )			/* returns base^exponent */
>	register long	base;
>	register long	exponent;
>	{
>	register long	result;		/* result accumulator */
>	/* handle simple special cases separately: */
>	if ( base == 0 )
>		return 0;		/* exp. < 0 should be EDOM */
>	else if ( base == 1 )
>		return 1;
>	else if ( base == -1 )
>		return exponent % 2 == 0 ? 1 : -1;
>	else if ( exponent < 0 )
>		return 0;
>	/* general case with exponent >= 0: */
>	result = 1;
>	for ( ; ; )	/* LOOP INVARIANT: result*base^exponent */
>		{
>		if ( exponent % 2 != 0 )
>			result *= base;
>		if ( (exponent /= 2) == 0 )
>			break;		/* result now stable */
>		base *= base;
>		}
>	return result;
>	}

Question.  Why not use

	exponent & 01

rather than

	exponent % 2

(other than consideration of portability to machines with one's complement
integers, which could be #ifdef'd easily enough)?  The latter is at least
three times slower when I spot checked it on a 3B20 (which has one-instruction
opcodes for both tests) and I doubt the VAX or other machines are much better
with a general-purpose "modulo".
-- 
 -------------------------------    Disclaimer:  The views contained herein are
|       dan levy | yvel nad      |  my own and are not at all those of my em-
|         an engihacker @        |  ployer or the administrator of any computer
| at&t computer systems division |  upon which I may hack.
|        skokie, illinois        |
 --------------------------------   Path: ..!{akgua,homxb,ihnp4,ltuxa,mvuxa,
						vax135}!ttrdc!levy

gwyn@brl.arpa (VLD/VMB) (06/23/86)

I wrote
	exponent % 2
because that was what I meant.  If your compiler cannot optimize
	expr % 2 == 0
to use a low-order bit test (two's complement only!), then perhaps
you should get somebody to improve your compiler.  (The SVR2 VAX
PCC generates remarkably ugly code for this, by the way.)

I'm a software engineer, not a speed phreak; I prefer code to be
correct regardless of any particular machine architecture.

The algorithm I posted is so much more efficient than the "obvious"
method that concerns for microefficiency are relatively unimportant.