robison@uiucdcsb.cs.uiuc.edu (07/04/87)
> 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); > } > Look in The Art of Computer Programming, vol. 2, section 4.6.3. The above binary scheme is not the fastest possible. For example: 5 15 3 X = X requires 5 multiplications while 2 2 2 15 2 2 2 X = X * X * X * X requires 6 multiplications Arch D. Robison University of Illinois at Urbana-Champaign CSNET: robison@UIUC.CSNET UUCP: {ihnp4,pur-ee,convex}!uiucdcs!robison ARPA: robison@B.CS.UIUC.EDU (robison@UIUC.ARPA)