加减任意大小的整数

Question

我的任务是从头开始实现任意大小的有符号整数的加减法。这样的整数存储在一个 64 位无符号整数数组中。数组第一个元素的最低有效位是整个整数的最低有效位。大小为 d 的数组表示最多 64 * d - 1 位的有符号整数。整数的格式不应更改。

我想到了以下内容：

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

我的团队对速度不满意。可以改进吗？

谢谢！

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)

和

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

GMP 中就是您要查找的内容。

加减任意大小的整数

Add and subtract integers of arbitrary size

c++

integer

bit-manipulation

biginteger