C中的溢流安全模块化加法和减法？

Question

我在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位机器上运行良好.此外,我现有的函数可以简单地转换为其他大小的无符号整数,这是一个很好的保留属性.

Answer 1

模块化操作通常假设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章.