68

数学：

このような方程式がある場合：

x = 3 mod 7

xは...-4、3、10、17、...、またはより一般的には次のようになります。

x = 3 + k * 7

ここで、kは任意の整数です。数学のためにモジュロ演算が定義されているかどうかはわかりませんが、因数環は確かに定義されています。

Python：

%Pythonでは、正の値を使用すると、常に非負の値が得られますm。

#!/usr/bin/python
# -*- coding: utf-8 -*-

m = 7

for i in xrange(-8, 10 + 1):
    print(i % 7)

結果：

6    0    1    2    3    4    5    6    0    1    2    3    4    5    6    0    1    2    3

C ++：

#include <iostream>

using namespace std;

int main(){
    int m = 7;

    for(int i=-8; i <= 10; i++) {
        cout << (i % m) << endl;
    }

    return 0;
}

出力します：

-1    0    -6    -5    -4    -3    -2    -1    0    1    2    3    4    5    6    0    1    2    3

ISO / IEC 14882：2003（E）-5.6乗法演算子：

二項/演算子は商を生成し、二項％演算子は、最初の式を2番目の式で除算した余りを生成します。/または％の第2オペランドがゼロの場合、動作は未定義です。それ以外の場合、（a / b）* b + a％bはaに等しくなります。両方のオペランドが非負の場合、余りは非負です。そうでない場合、剰余の符号は実装定義です74）。

と

74）ISO Cの改訂に向けて進行中の作業によると、整数除算に推奨されるアルゴリズムは、ISOFortran規格ISO/ IEC 1539：1991で定義されている規則に従います。この規則では、商は常にゼロに向かって丸められます。

出典：ISO / IEC 14882：2003（E）

（無料版が見つかりませんでしたISO/IEC 1539:1991。どこから入手できるか誰か知っていますか？）

操作は次のように定義されているようです。

ここに画像の説明を入力してください

質問：

そのように定義するのは理にかなっていますか？

この仕様の議論は何ですか？そのような基準を作成する人々がそれについて話し合う場所はありますか？彼らがこのようにすることを決めた理由について、どこで私は何かを読むことができますか？

モジュロを使用するほとんどの場合、データ構造の要素にアクセスしたいと思います。この場合、modが負でない値を返すことを確認する必要があります。したがって、この場合、modが常に非負の値を返すのは良いことです。（別の使用法はユークリッドアルゴリズムです。このアルゴリズムを使用する前に両方の数値を正にすることができるため、モジュロの符号が重要になります。）

追加資料：

モジュロがさまざまな言語で行うことの長いリストについては、ウィキペディアを参照してください。

4

3 に答える 3

38

x86（およびその他のプロセッサアーキテクチャ）では、整数の除算とモジュロが1回の演算idiv（符号なしの値の場合）で実行され、商と剰余の両方が生成されます（それぞれ、divワードサイズの引数の場合）。これはCライブラリ関数で使用され、コンパイラによって単一の命令に最適化できます。AXDXdivmod

整数除算は2つの規則を尊重します。

  • 非整数の商はゼロに向かって丸められます。と
  • 方程式dividend = quotient*divisor + remainderは結果によって満たされます。

したがって、負の数を正の数で割ると、商は負（またはゼロ）になります。

したがって、この動作は、一連のローカル決定の結果として見ることができます。

  • プロセッサの命令セットの設計は、あまり一般的でないケース（モジュロ）よりも一般的なケース（除算）に最適化されています。
  • 一貫性（ゼロに向かって丸め、除算式を尊重する）は、数学的な正確さよりも優先されます。
  • Cは効率と単純さを優先します（特にCを「高水準アセンブラ」と見なす傾向がある場合）。と
  • C++はCとの互換性を優先します。
于 2012-07-24T12:43:05.163 に答える
19

当時、x86命令セットを設計している人は、整数の除算を切り捨てるのではなく、ゼロに向かって丸めるのが適切であると判断しました。（千頭のラクダのノミが母親のあごひげに巣を作ることがあります。）数学の正しさをある程度保つために、「剰余」と発音される演算子REMはそれに応じて動作する必要がありました。これを読まないでください：https ：//www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzatk/REM.htm

警告しました。その後、C仕様を実行している誰かが、コンパイラーが正しい方法またはx86の方法でそれを実行することに準拠していると判断しました。次に、C ++仕様を実行する委員会は、Cの方法で実行することを決定しました。その後、この質問が投稿された後、C++委員会は間違った方法で標準化することを決定しました。今、私たちはそれに固執しています。多くのプログラマーは、次の関数などを作成しています。私はおそらく少なくとも十数回それをしました。

 inline int mod(int a, int b) {int ret = a%b; return ret>=0? ret: ret+b; }

あなたの効率があります。

最近、私は基本的に次のものを使用し、type_traitsのものをいくつか投入しています（後日のC ++を使用した改善のアイデアを与えてくれたClearerのコメントに感謝します。以下を参照してください。）

<strike>template<class T>
inline T mod(T a, T b) {
    assert(b > 0);
    T ret = a%b;
    return (ret>=0)?(ret):(ret+b);
}</strike>

template<>
inline unsigned mod(unsigned a, unsigned b) {
    assert(b > 0);
    return a % b;
}

本当の事実：私はPascal標準化委員会に、彼らが容赦するまで正しい方法でmodを実行するように働きかけました。私の恐ろしいことに、彼らは整数除算を間違った方法で行いました。したがって、それらは一致しません。

編集：クリアラーは私にアイデアを与えました。私は新しいものに取り組んでいます。

#include <type_traits>

template<class T1, class T2>
inline T1 mod(T1 a, T2 b) {
    assert(b > 0);
    T1 ret = a % b;
    if constexpr  ( std::is_unsigned_v<T1>)
    {
        return ret;
    } else {
        return (ret >= 0) ? (ret) : (ret + b);
    }
}
于 2018-01-24T09:51:22.950 に答える
10

この仕様の議論は何ですか？

C ++の設計目標の1つは、ハードウェアに効率的にマッピングすることです。基盤となるハードウェアが負の剰余を生成する方法で除算を実装している場合%、C++で使用するとそれが得られます。本当にこれですべてです。

そのような基準を作成する人々がそれについて話し合う場所はありますか？

comp.lang.c ++。moderatedと、程度は少ないがcomp.lang.c++に関する興味深い議論があります。

于 2012-07-24T12:08:30.130 に答える