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.