19

「Programming Pearls」本からの言い換え (本は 90 年代後半のものであるため、古いマシンの C 言語について):

整数算術演算 ( +、-、*) には約 10 ナノ秒かかることがありますが、%演算子には最大 100 ナノ秒かかります。

  • なぜそんなに差があるのでしょうか？
  • モジュラス演算子は内部でどのように機能しますか?
  • 時間的には割り算（ ）と同じ/ですか？
4

1 に答える 1

22

モジュラス/モジュロ演算は、通常、剰余演算と同等の整数として理解されます。これは、除算の副作用または対応物です。

一部の退化したケース (除数が基数の累乗、つまりほとんどの数値形式で 2 の累乗) を除いて、これは整数の除算と同じくらいコストがかかります。

問題は、整数除算がなぜそれほど高価なのかということです。

これを数学的に分析する時間も専門知識もないので、小学校​​の数学に訴えます。

次の場合に必要なノートブック (入力を含まない) で作業する行数を考慮してください。

  • 等価性: (ブール演算) 基本的になし - コンピューターの「ビッグ O」用語では、これは O(1) と呼ばれます
  • 追加: 2 つ、左から右へ、出力用に 1 行、キャリー用に 1 行。これは O(N) 操作です
  • 長い乗算: n*(n+1) + 2: 桁積ごとに 2 行 (合計に 1 つ、キャリーに 1 つ) と、最終的な合計とキャリー。したがって、O(N^2) ですが、N は固定 (32 または 64) であり、シリコン内でパイプライン化してそれ未満にすることができます。
  • 長い除算: 不明、引数のサイズによって異なります。これは再帰的な下降であり、一部のインスタンスは他のインスタンスよりも速く下降します (1,000,000 / 500,000 は 1,000 / 7 よりも少ない行数で済みます)。また、各ステップは基本的に、最も近い因子を分離するための一連の乗算です。(複数のアルゴリズムが存在しますが)。変数 N を持つ O(N^3) のように感じます

簡単に言えば、除算とモジュロが遅くなる理由がわかるはずです。コンピューターは、小学校で行ったのと同じように、段階的な方法で長い除算を行う必要があります。

これがあなたにとって意味をなさない場合; あなたは私よりも少し現代的な学校の数学で育てられたかもしれません（30年以上前）.

上記で O(何か) として使用されている Order/Big O 表記は、入力のサイズに関して計算の複雑さを表し、その実行時間に関する事実を表します。 http://en.m.wikipedia.org/wiki/Big_O_notation

O(1) は、一定の (ただし、場合によっては長い) 時間で実行されます。O(N) はそのデータのサイズと同じくらい時間がかかります。したがって、データが 32 ビットの場合、その N ステップの 1 つを計算するには、ステップの O(1) 時間の 32 倍かかり、O(N^2)は、その N ステップの時間の N 倍 (N の 2 乗) かかります (または、定数 M の場合は MN の N 倍になる可能性があります)。等。

上記の作業では、最初の入力の 32 ビットまたは 64 ビットが CPU によって並列に計算されるため、加算に O(N^2) ではなく O(N) を使用しました。仮想の 1 ビット マシンでは、32 ビットの加算演算は O(32^2) になり、変更されます。同じ注文削減が他の操作にも適用されます。

于 2015-01-16T09:08:05.650 に答える