CODEWITHSUNDEEP
algorithmbit-shiftdiscrete-mathematicsexponentiation
Anton Samsonov
Anton Samsonov

Reputation: 1432

Exponentiation by cyclic shifting

Some other topic here on SO mentioned the paper “Fast Exponentiation with Precomputation” by Brickell et al., which, along with simple concept of precomputation of powers corresponding to binary digits, had a statement about “exponentiation by cyclic shifting” (as far as I understood it). Unfortunately, that part of the paper was expressed in a very general form, so I simply can't figure out whether they were talking something obvious that becomes sophisticated with bases other than 2**n, or there really exist some method of exponentiation other than multiplication (squaring)?

For example, let's say we have x = 5 (that's 00101 in binary). How is it possible to end up with y = 5 * 5 (that's 11001 in binary), using only bit-shifting and perhaps some addition(s)? Of course, the algorithm should be more effective than multiplication, — the answer “you may emulate each multiplication by a bunch of bit-shifting and additions, as y = (5 << 2) + (5 << 0)” doesn't count. Well, it could count if sparse numbers were usual, but it's not a common scenario, and determining the exact bit-population count is also time-consuming, so, unless a number is very sparse, it's not worth trying, the more so that after each squaring a new assessment is needed.

Upvotes: 1

Views: 507

Answers (1)

Tyler Durden
Tyler Durden

Reputation: 11562

The method is called "exponentiation by binary decomposition" and you can find a discussion in Knuth 4.6.3. For example, xcubed, thus in the first case you need 7 multiplications, but in the second 3 (note that 8 = 100 in binary). The code to do this is as follows:

long power( int x, int n ){
   long result = 1;
   long base = x;
   while( true ){
      if( n & 1 ) result = base * result;
      n = n >> 1;
      if( n == 0 ) return result;
      base = base * base;
   }
}

Upvotes: 1

Related Questions