8

我正在用 C 语言实现一个算法，该算法需要对无符号整数快速进行模加法和减法，并且可以正确处理溢出条件。这是我现在拥有的（确实有效）：

/* a and/or b may be greater than m */
uint32_t modadd_32(uint32_t a, uint32_t b, uint32_t m) {
    uint32_t tmp;
    if (b <= UINT32_MAX - a)
        return (a + b) % m;

    if (m <= (UINT32_MAX>>1))
        return ((a % m) + (b % m)) % m;

    tmp = a + b;
    if (tmp > (uint32_t)(m * 2)) // m*2 must be truncated before compare
        tmp -= m;
    tmp -= m;
    return tmp % m;
}

/* a and/or b may be greater than m */
uint32_t modsub_32(uint32_t a, uint32_t b, uint32_t m) {
    uint32_t tmp;
    if (a >= b)
        return (a - b) % m;

    tmp = (m - ((b - a) % m)); /* results in m when 0 is needed */
    if (tmp == m)
        return 0;
    return tmp;
}

有人知道更好的算法吗？我发现做模运算的库似乎都适用于大的任意精度数字，这太过分了。

编辑：我希望它在 32 位机器上运行良好。此外，我现有的函数被简单地转换为适用于其他大小的无符号整数，这是一个很好保留的属性。

4

3 回答 3

10

模运算通常假设 a 和 b 小于 m。这允许更简单的算法：

umod_t sub_mod(umod_t a, umod_t b, umod_t m)
{
  if ( a>=b )
    return a - b;
  else
    return m - b + a;
}

umod_t add_mod(umod_t a, umod_t b, umod_t m)
{
  if ( 0==b ) return a;

  // return sub_mod(a, m-b, m);
  b = m - b;
  if ( a>=b )
    return a - b;
  else
    return m - b + a;
}

资料来源：Matters Computational，第 39.1 章。

于 2012-06-28T16:36:42.033 回答
1

uint32_t如果它适合，我会做算术，uint64_t否则。

uint32_t modadd_32(uint32_t a, uint32_t b, uint32_t m) {
    if (b <= UINT32_MAX - a)
        return (a + b) % m;
    else
        return ((uint64_t)a + b) % m;
}

在具有 64 位整数类型的架构上，这应该几乎没有开销，您甚至可以考虑只在uint64_t. 在uint64_t综合架构上，让编译器决定他认为最好的，然后查看生成的汇编器并测量以查看这是否令人满意。

于 2012-06-28T15:47:03.130 回答
0

溢出安全的模块化添加

首先确定a<m并b<m与通常的% m.

添加更新a和b.

如果a（或b）超过uintN_t总和，则数学总和是uintN_t溢出和减法m将“mod”数学总和到 的范围内uintN_t。

如果总和超过m，则与上述步骤一样，单次减法m将“修改”总和。

uintN_t modadd_N(uintN_t a, uintN_t b, uintN_t m) {
  // may omit these 2 steps if a < b and a < m are known before the call.
  a %= m;
  b %= m;

  uintN_t sum = a + b;
  if (sum >= m || sum < a) {
    sum -= m;
  }
  return sum;
}

最后很简单。

溢出安全模减法

@Evgeny Kluev的变化很好的答案。

uintN_t modsub_N(uintN_t a, uintN_t b, uintN_t m) {
  // may omit these 2 steps if a < b and a < m are known before the call.
  a %= m;
  b %= m;

  uintN_t diff = a - b;  
  if (a < b) {
    diff += m;
  }
  return diff;
}

请注意，这种方法适用于各种类型N，例如32, 64, 16or unsigned、unsigned long等，而无需求助于更广泛的类型。它也适用于比 更窄的无符号类型int/unsigned。

于 2017-10-04T02:29:31.787 回答