Add and subtract integers of arbitrary size

Question

I am tasked to implement from scratch addition and subtraction of signed integers of arbitrary size. Such an integer is stored in an array of 64-bit unsigned integers. The least significant bit of the array's first element is the least significant bit of the whole integer. An array of size d represents a signed integer of at most 64 * d - 1 bits. Format of the integer should not be changed.

I came up with the following:

// Add huge integers: z[] = x[] + y[]
template<typename ing>
inline void addHint(uint64_t *z, uint64_t *x, uint64_t *y, ing d)
{
  uint64_t carry = 0;
  for (ing i = 0; i < d; ++i)
  {
    uint64_t zi = x[i] + y[i];
    // uint64_t carryNew = zi < x[i] or zi < y[i];
    uint64_t carryNew = zi < x[i]; // zi < y[i] unnecessary.
    z[i] = zi + carry;
    carry = carryNew or z[i] < zi;
  }
}


// Subtract huge integers: x[] = z[] - y[]
template<typename ing>
inline void subHint(uint64_t *x, uint64_t *z, uint64_t *y, ing d)
{
  uint64_t carry = 0;
  for (ing i = 0; i < d; ++i)
  {
    uint64_t xi = z[i] - y[i];
    // uint64_t carryNew = z[i] < y[i];
    uint64_t carryNew = z[i] < xi; // Somehow x86-64 g++ 8.3 -O2 dumps fewer assembly lines than the above according to godbolt.org
    x[i] = xi - carry;
    carry = carryNew or xi < x[i];
  }
}

My team is unsatisfied with the speed. Can it be improved?

Thanks!

Answer 1

mp_limb_t mpn_add_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

and

mp_limb_t mpn_sub_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

in GMP are what you were looking for.