speedy mod inverses for 2**48

modInverses.cpp

#include <iostream>

const uint64_t MASK = 0xffffffffffffL;


//Credits : Matthew Bolan for the following Function
static inline uint64_t modInverse(uint64_t a,uint64_t k){
        uint64_t x = (((a << 2) ^ (a << 1)) & 8) ^ a;

        x += x - a * x * x;
        x += x - a * x * x;
        x += x - a * x * x;
        x += x - a * x * x;

        return x & MASK;
    }


//My implementation
static inline uint64_t mod_inverse_1(uint64_t a)
{
  uint64_t x,t;
  x = (((a << 2) ^ (a << 1)) & 8) ^ a;
  x *= 2-a*x;
  x *= 2-a*x;
  x *= 2-a*x;
  x *= 2-a*x;
  return x & MASK;
}

int main(int argc, char const *argv[])
{
  uint64_t hold = modInverse(555666999, 48);
  uint64_t hold2 = mod_inverse_1(555666999);
  std::cout << "modIverse of 555666999 with mod 2^48 : " << hold << std::endl;
  std::cout << "modInverse of 555666999 with mod 2^48 : " << hold2 << std::endl;
  return 0;
}

Two functions for checking validity.

First function credits : Matthew Bolan (mjtb49 on github)