Algo for finding energy, i.e. N ^ p

Question

Search Algorithm n ^ p :

unsigned long long power(unsigned n, unsigned p) { unsigned long long x=1, y=n; while(p > 0) { if(p&1) x *= y; y *= y; p >>= 1; } return x; } 

Can someone explain the logic / math behind this algorithm. I know this works, and designed it for several test cases (dry run). I mean how it works and how effective it is from a general naive method.

Answer 1

This squared elevation : >>= 1 is a fantastic way to write /= 2 .

The idea is that if p even, you can take n^(p/2) and put its square; when p is odd, p-1 must be even, so you can take n^((p-1)/2) , compose it, and then multiply the result by n to compensate for the 1 that you subtracted from p before squaring .