# Efficient Integer Exponentiation in C

It's surprisingly difficult to find a good code snippet for this on Google, so here's an efficient computation of integer powers in C, using binary exponentiation:

```// Computes b**e (mod UINT32_MAX) uint32_t ipow(uint32_t b, uint32_t e) { uint32_t ret; for (ret = 1; e; e >>= 1) { if (e & 1) { ret *= b; } b *= b; } return ret; }```

GCC 4.9.1 (and likely other versions) is smart enough to replace the `if (e & 1)` branch with a conditional move, generating very fast code.

Of course, this computes the result modulo `UINT32_MAX`. To use a different modulus, just reduce after each multiplication:

```// Computes b**e (mod m) uint32_t ipowm(uint32_t b, uint32_t e, uint32_t m) { uint32_t ret; b %= m; for (ret = m > 1; e; e >>= 1) { if (e & 1) { ret = (uint64_t)ret * b % m; } b = (uint64_t)b * b % m; } return ret; }```

(Note the `ret = m > 1` instead of `ret = 1`, to handle the case `e == 0 && m == 1`.)

Unfortunately, GCC isn't smart enough to realise the limited range of the operands and generates a full 64-bit multiply and divide for each `... * b % m` operation. For extra performance, this bit of inline assembly for x86 and x86-64 gives about a 15% boost:

```// Computes a * b (mod m), as long as a / b is representable in 32 bits static uint32_t reduced_multiply(uint32_t a, uint32_t b, uint32_t m) { uint32_t q, r;   __asm__ ("mull %3\n\t" "divl %4" : "=a" (q), "=&d" (r) : "0" (a), "rm" (b), "rm" (m));   return r; }   // Computes b**e (mod m) uint32_t ipowm(uint32_t b, uint32_t e, uint32_t m) { uint32_t ret; b %= m; for (ret = m > 1; e; e >>= 1) { if (e & 1) { ret = reduced_multiply(ret, b, m); } b = reduced_multiply(b, b, m); }   return ret; }```