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 に答える