モジュラスの数学的概念がどのように機能するのか、または20 % 3 == 2これをうまく理解しているのかを尋ねているわけではありません。コンパイラ/インタプリタがこれをどのように決定するのか、もっと興味があります。次のように、非常に素朴な方法を考えることができます。

int modulus(int a, int b) { while (a > b) { a -= b; } return a; }

（aはbよりも小さい可能性があるため、明らかにこれにはさらにいくつかのケースが必要ですが、アイデアは得られます。）しかし、これにはいくつかの深刻なパフォーマンスの問題があります。両方の係数の効率をテストするために、いくつかのC ++をまとめました。演算子と私の素朴な関数。

#include <iostream> #include <chrono> #include <limits> #include "chrono_io" using namespace std; typedef chrono::high_resolution_clock Clock; int mod(int a, int b) { while (a > b) { a -= b; } return a; } int main() { auto start = Clock::now(); cout << 20 % 3 << endl; auto end = Clock::now(); cout << "Modulus on a small number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << numeric_limits<int>::max() % 3 << endl; end = Clock::now(); cout << "Modulus on a large number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << mod(20, 3) << endl; end = Clock::now(); cout << "My modulus function on a small number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << mod(numeric_limits<int>::max(), 3) << endl; end = Clock::now(); cout << "My modulus function on a large number took " << end - start << " seconds to calculate.\n"; }

出力は次のとおりです。

2 Modulus on a small number took 43629 nanoseconds seconds to calculate. 1 Modulus on a large number took 5644 nanoseconds seconds to calculate. 2 My modulus function on a small number took 3682 nanoseconds seconds to calculate. 1 My modulus function on a large number took 2153824554 nanoseconds seconds to calculate.

モジュラス演算子は4,000〜70,000ナノ秒の範囲で変化しました。私の関数は常に小さい数値で勝ちましたが、大きい数値では約2秒かかりました。モジュラス演算子の方がはるかに一貫しているため、ビット単位のレベルで数値を比較すると思います。

では、モジュラス演算子はどのように機能しますか？ 決定が非常に簡単な場合がいくつか考えられます。たとえば、mod 2を使用すると、最後のバイトまたはmod4を使用すると、最後から2番目のbを確認できます。 yte。ただし、すべての数値がそのような単純なパターンを持っているわけではありません。

コメント

  • PCでは、これは通常、ハードウェア（x86 DIVおよびIDIV命令は、整数除算を実行し、余りもレジスタに格納します）。 ハードウェアがどのように機能するかを尋ねていますか？
  • 関連資料： アセンブリ言語-モジュロの実行方法？
  • 筆算は、10進数の場合と同じように2進数でも機能します。それを試してから、どのようにコーディングするかを考えてください（ヒント：'多くのシフトを使用します）。
  • @DJMcMayhem：はい。コンパイラは、符号付き算術の言語仕様に準拠するために、結果に対していくつかの調整を実行する必要がある場合があります。一般に、ハードウェア分割の速度は十分に優れているため、コンパイル時に入力値がわからない場合は、ソフトウェアエミュレーションではなくハードウェアに分割させる方がよいでしょう。ただし、コンパイル時に除数がわかっている場合は、より高速に実行できるトリックがあります。参照： this および this 。
  • あなたのやり方に注意してくださいcout <<のほとんどの操作にかかる時間を実際に測定しているタイミングです。コンパイラがコンパイル時に'を実行しなかったとしても、プロセッサが20 % 3を実行するのにかかる時間を実際に測定できるとは思えません。 。

回答

ほぼすべてのCPUには、値のモジュラスを返す単一の命令があります。たとえば、次のプログラムについて考えてみます。

int main() { int i = 10; return i % 3; }

g ++-Sを使用してIntelOS Xマシンでこれをコンパイルすると、結果は定型文になります。 

movl $3, %eax movl $0, -4(%rbp) movl $10, -8(%rbp) movl -8(%rbp), %ecx movl %eax, -12(%rbp) ## 4-byte Spill movl %ecx, %eax cltd movl -12(%rbp), %ecx ## 4-byte Reload idivl %ecx movl %edx, %eax

実際の係数は次の命令で発生します：idivl %ecx。この命令が実行されると、商は%eaxに配置され、余りは%edxに配置されます。

実際には、これは%操作に数クロックサイクルしかかからないことを意味し、その大部分は実際にデータを正しいレジスタに移動します。また、少なくともIntelでは、同じ操作で商と剰余の両方が検出されるため、コメントを参照すると、/と%まったく同じ時間かかります。同じ操作です。変更されるのは、コンパイラが結果を取得するレジスタだけです。

過去数十年に作成されたCPUを使用すると、基本的な数学演算（sqrtまたはcos）は、実際には単一のマシン命令であり、通常、最大で数クロックサイクルしかかかりません。

[UPDATE]

コメントで指摘されているように、何かが正しいタイミングに近づいていることを確認するには、次のように、タイミングセクションから出力を削除する必要があります。

int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl;

ただし、タイミングの実際の粒度が実際の粒度を超える可能性があるため、それでも正確ではない可能性があります。時間を計ろうとしています。代わりに、次のようにすることをお勧めします。

int i=0; int x; auto start = Clock::now(); for(i=0;i<1000000;i++) x = i % 3; auto end = Clock::now(); cout << i << endl;

次に、タイミングを1,000,000で割ります。 （割り当て、比較、増分にかかる時間が含まれるため、これは少し長くなります。）私のマシンでは、これにより5ナノ秒の時間が与えられます。

コメント

Agner Fog 'テーブル。少なくとも毎年更新されます、HaswellSSE2命令SQRTSS / SQRTPS（32ビット浮動小数点数、重要度が23ビットの）のレイテンシーは11サイクル、SQRTSD / SQRTPD（64ビット浮動小数点数）のレイテンシーは16サイクルです。これらの指示は正確なものです。つまり、高速近似の変形ではありません。実際、古いアーキテクチャではかなり遅くなります。また、std::sqrt()を呼び出すと、ほとんどのC ++コンパイラでライブラリ呼び出しが発生することに注意してください。

  • コンパイラは、特別な場合に強度低減の最適化を追加で適用できます。たとえば、特定のアーキテクチャで'が高速である場合、x％2はビットマスクに最適化される可能性があります。
  • @rwong std:sqrtは通常インライン化されます（そしてインラインアセンブリを使用します）が、私は'チェックしたことがありません。

    • コメントを残す

    メールアドレスが公開されることはありません。 * が付いている欄は必須項目です