What is the correct way to raise an integer to a positive integer power in C++?

Question

We know that for various reasons, there is no standard integer power function in C++. I'm performing exact arithmetic with rather small integers, what is the correct way to compute powers?

Answer 1

The standard, fast exponentiation uses repeated squaring:

uint_t power(uint_t base, uint_t exponent) {     uint_t result = 1;      for (uint_t term = base; exponent != 0; term = term * term)     {         if (exponent % 2 != 0) { result *= term; }         exponent /= 2;     }      return result; } 

The number of steps is logarithmic in the value of exponent. This algorithm can trivially be extended to modular exponentiation.

---

Update: Here is a modified version of the algorithm that performs one less multiplication and handles a few trivial cases more efficiently. Moreover, if you know that the exponent is never zero and the base never zero or one, you could even remove the initial checks:

uint_t power_modified(uint_t base, uint_t exponent) {     if (exponent == 0) { return 1;    }     if (base < 2)      { return base; }      uint_t result = 1;      for (uint_t term = base; ; term = term * term)     {          if (exponent % 2 != 0) { result *= term; }         exponent /= 2;         if (exponent == 0)     { break; }     }      return result; }