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;
}