webdevqa.jp.net

乗算または除算を使用する必要がありますか?

馬鹿げた楽しい質問です:

変数の半分の値が必要な簡単な操作を実行しなければならないとしましょう。 通常、これを行うには2つの方法があります:

y = x / 2.0;
// or...
y = x * 0.5;

言語で提供される標準演算子を使用していると仮定すると、どれがより良いパフォーマンスを持っていますか?

私は乗算が一般的に優れていると推測しているので、コーディングするときにそれを維持しようとしますが、これを確認したいと思います。

個人的にはPython 2.4-2.5の回答に興味がありますが、他の言語の回答も自由に投稿してください!必要に応じて、他のより洗練された方法(ビット単位のシフト演算子の使用など)も自由に投稿してください。

113
Edmundito

Python:

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 / 2.0'
real    0m26.676s
user    0m25.154s
sys     0m0.076s

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 * 0.5'
real    0m17.932s
user    0m16.481s
sys     0m0.048s

乗算は33%高速です

ルア:

time lua -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m7.956s
user    0m7.332s
sys     0m0.032s

time lua -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m7.997s
user    0m7.516s
sys     0m0.036s

=>実質的な違いはありません

LuaJIT:

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m1.921s
user    0m1.668s
sys     0m0.004s

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m1.843s
user    0m1.676s
sys     0m0.000s

=>わずか5%高速です

結論:in Python分割するよりも乗算する方が高速ですが、より高度なVMまたはJITを使用してCPUに近づくと、利点はなくなります。将来Python VMは無関係になります

74
Javier

常に最も明確なものを使用してください。あなたがする他のことは、コンパイラを裏切ることです。コンパイラがまったくインテリジェントな場合、結果を最適化するために最善を尽くしますが、次の人があなたの安っぽいビットシフトソリューションのためにあなたを嫌わないようにすることはできません(私はちなみにビット操作が大好きです、しかし楽しいです! )

早すぎる最適化は、すべての悪の根源です。最適化の3つのルールを常に覚えておいてください!

  1. 最適化しないでください。
  2. 専門家の方は、ルール1をご覧ください
  3. あなたが専門家であり、必要性を正当化できる場合は、次の手順を使用します。

    • 最適化せずにコーディングする
    • 「十分に速い」速さを判断します。どのユーザー要件/ストーリーがそのメトリックを必要とするかに注意してください。
    • 速度テストを書く
    • 既存のコードをテストします。十分に高速であれば、完了です。
    • 最適化して再コーディング
    • 最適化されたコードをテストします。メトリックを満たしていない場合は、捨てて元のものを保持します。
    • テストを満たしている場合は、元のコードをコメントとして保存します

また、内部ループが不要な場合に内部ループを削除したり、挿入ソートのために配列のリンクリストを選択したりすることは、最適化ではなく、プログラミングだけです。

64
Bill K

これは非常にきちんとなっているので、コードを読みやすくするために何でもする方が良いと思います。数百万回ではないにしても、数千回も操作を実行しない限り、誰もがその違いに気付くことはないでしょう。

本当に選択する必要がある場合は、ベンチマークが唯一の方法です。どの関数が問題を引き起こしているかを見つけ、関数のどこで問題が発生しているかを見つけ、それらのセクションを修正します。ただし、1つの数学演算(1回でも何度も何度も繰り返される)がボトルネックの原因になるのではないかと思います。

47
Thomas Owens

乗算はより高速で、除算はより正確です。数値が2の累乗でない場合、精度がいくらか失われます。

y = x / 3.0;
y = x * 0.333333;  // how many 3's should there be, and how will the compiler round?

コンパイラーに逆定数を完全な精度で計算させたとしても、答えは異なる場合があります。

x = 100.0;
x / 3.0 == x * (1.0/3.0)  // is false in the test I just performed

速度の問題は、C/C++またはJIT言語でのみ問題になる可能性が高く、その場合でも、操作がボトルネックのループ内にある場合のみです。

37
Mark Ransom

コードを最適化したいが、それでも明確にしたい場合は、これを試してください:

y = x * (1.0 / 2.0);

コンパイラーは、コンパイル時に除算を実行できる必要があるため、実行時に乗算が行われます。精度はy = x / 2.0の場合と同じであると期待しています。

これが問題になる可能性のある場所は、浮動小数点演算を計算するために浮動小数点エミュレーションが必要な組み込みプロセッサです。

25
Jason S

「他の言語」オプションに何かを追加するだけです。
C:これは実際にに違いはない単なる学術的な演習なので、私は何か違うことに貢献すると思いました。

最適化なしでアセンブリにコンパイルし、結果を確認しました。
コード:

_int main() {

    volatile int a;
    volatile int b;

    asm("## 5/2\n");
    a = 5;
    a = a / 2;

    asm("## 5*0.5");
    b = 5;
    b = b * 0.5;

    asm("## done");

    return a + b;

}
_

_gcc tdiv.c -O1 -o tdiv.s -S_でコンパイルされた

2による除算

_movl    $5, -4(%ebp)
movl    -4(%ebp), %eax
movl    %eax, %edx
shrl    $31, %edx
addl    %edx, %eax
sarl    %eax
movl    %eax, -4(%ebp)
_

0.5の乗算:

_movl    $5, -8(%ebp)
movl    -8(%ebp), %eax
pushl   %eax
fildl   (%esp)
leal    4(%esp), %esp
fmuls   LC0
fnstcw  -10(%ebp)
movzwl  -10(%ebp), %eax
orw $3072, %ax
movw    %ax, -12(%ebp)
fldcw   -12(%ebp)
fistpl  -16(%ebp)
fldcw   -10(%ebp)
movl    -16(%ebp), %eax
movl    %eax, -8(%ebp)
_

ただし、これらのintsをdoublesに変更したとき(これはpythonがおそらく行うことです)、私はこれを得ました:

分割:

_flds    LC0
fstl    -8(%ebp)
fldl    -8(%ebp)
flds    LC1
fmul    %st, %st(1)
fxch    %st(1)
fstpl   -8(%ebp)
fxch    %st(1)
_

乗算:

_fstpl   -16(%ebp)
fldl    -16(%ebp)
fmulp   %st, %st(1)
fstpl   -16(%ebp)
_

このコードのベンチマークは行っていませんが、コードを調べるだけで、整数を使用すると、2による除算が2による乗算よりも短いことがわかります。おそらく、同じ操作にそれらを使用しないよりも高速に実行されます(実際にはわかりません)。したがって、最終的に、この答えは、0.5による乗算と2による除算のパフォーマンスが、言語の実装とそれが実行されるプラットフォームに依存することを示しています。最終的に、違いは無視でき、読みやすさの点を除いて、実質的に決して心配する必要はありません。

補足として、私のプログラムではmain()が_a + b_を返すことがわかります。 volatileキーワードを削除すると、アセンブリがどのように見えるかを推測することはできません(プログラムのセットアップを除く)。

_## 5/2

## 5*0.5
## done

movl    $5, %eax
leave
ret
_

1つの命令で除算、乗算、および加算の両方を行いました!オプティマイザーが立派なものであれば、明らかにこれについて心配する必要はありません。

回答が長すぎて申し訳ありません。

21
Carson Myers

まず、Cまたはアセンブリで作業しているのでない限り、おそらくメモリストールと一般的な呼び出しのオーバーヘッドにより、乗算と除算の違いがまったく関係のない点で完全に小さくなってしまう、高レベルの言語を使用しているでしょう。ですから、その場合は読みやすいものを選んでください。

あなたが非常に高いレベルから話している場合、あなたがそれを使用する可能性があるものについては、それが測定可能なほど遅くなることはありません。他の答えでわかるように、2つのサブミリ秒の差を測定するためだけに、100万回の乗算/除算を行う必要があります。

まだ興味があれば、低レベルの最適化の観点から:

除算は、乗算よりもかなり長いパイプラインを持つ傾向があります。これは、結果を取得するのに時間がかかることを意味しますが、プロセッサを非依存タスクでビジー状態に保つことができる場合、乗算以上のコストがかかることはありません。

パイプラインの違いの長さは、ハードウェアに完全に依存しています。私が最後に使用したハードウェアは、FPU乗算で9サイクル、FPU除算で50サイクルのようなものでした。たくさん聞こえますが、その後、メモリミスのために1000サイクルを失うことになります。

アナロジーは、テレビ番組を見ながらパイを電子レンジに入れることです。テレビ番組からあなたを連れ去った合計時間は、それを電子レンジに入れて電子レンジから取り出すのにかかった時間です。残りの時間は、まだテレビ番組を見ていました。したがって、パイが調理するのに1分ではなく10分かかったとしても、実際にはテレビの視聴時間をこれ以上使い切ることはありませんでした。

実際には、乗算と除算の違いを気にするレベルに到達する場合、パイプライン、キャッシュ、ブランチストール、異常な予測、およびパイプラインの依存関係を理解する必要があります。これがこの質問に進むつもりのように聞こえない場合、正しい答えは2つの違いを無視することです。

多くの(数年前)分割を避け、常に乗算を使用することが絶対に重要でしたが、当時のメモリヒットはそれほど重要ではなく、分割ははるかに悪化していました。最近では読みやすさを高く評価していますが、読みやすさの違いがなければ、乗算を選択するのが良い習慣だと思います。

10
James Podesta

どちらがあなたの意図を明確に述べているかを書いてください。

プログラムが動作したら、遅いものを見つけて、それを速くします。

逆にしないでください。

7
Jay Bazuzi

必要なことは何でもします。最初に読者のことを考えてください。パフォーマンスの問題があることが確実になるまで、パフォーマンスについて心配しないでください。

コンパイラーにパフォーマンスを任せてください。

6
buti-oxa

整数または非浮動小数点型を使用している場合、ビットシフト演算子を忘れないでください:<< >>

    int y = 10;
    y = y >> 1;
    Console.WriteLine("value halved: " + y);
    y = y << 1;
    Console.WriteLine("now value doubled: " + y);
4
sbeskur

実際には、一般的な経験則として、乗算よりも除算の方が速いという正当な理由があります。ハードウェアでの浮動小数点除算は、シフトおよび条件付き減算アルゴリズム(2進数による「長い除算」)で行われます。または、最近の可能性が高いのは、 Goldschmidt's アルゴリズムのような繰り返しです。シフトと減算には、精度のビットごとに少なくとも1サイクルが必要です(反復の乗算とシフトの加算と同様に、並列化はほぼ不可能です)。反復アルゴリズムは、少なくとも1回の乗算繰り返し。いずれの場合も、部門のサイクルが長くなる可能性が高くなります。もちろん、これはコンパイラーの癖、データの移動、または精度を考慮していません。概して、プログラムの時間依存部分で内部ループをコーディングしている場合、0.5 * xまたは1.0/2.0 * x のではなく x / 2.0は妥当なことです。 「最も明確なものをコード化する」という考え方は絶対に正しいのですが、これら3つはすべて読みやすさの点で非常に近いため、この場合の考え方は単なる教訓的です。

4
Gene

乗算は通常、高速です-決して遅くなることはありません。ただし、速度が重要でない場合は、最も明確な方を記述してください。

3
Dan Hewett

これは、AssemblyまたはおそらくCでプログラミングしている場合、より多くの質問になります。ほとんどの現代言語では、このような最適化が行われていると思います。

2
Seamus

私は、乗算がより効率的であることを常に学びました。

2
Toon Krijthe

浮動小数点除算は(一般に)特に遅いため、浮動小数点乗算も比較的低速ですが、おそらく浮動小数点除算よりも高速です。

しかし、プロファイリングで除算が少しボトルネック対乗算であることを示していない限り、「それは本当に問題ではない」と答えたいと思います。ただし、乗算と除算の選択がアプリケーションのパフォーマンスに大きな影響を与えることはないと思います。

2
mipadi

「推測乗算は一般的には優れているので、コーディングするときはそれに固執しようとする」ことに注意してください。

この特定の質問の文脈では、ここで良いということは「速い」ということです。これはあまり役に立ちません。

速度について考えることは重大な間違いです。計算の特定の代数形式には重大なエラーの影響があります。

エラー分析を伴う浮動小数点演算 を参照してください。 浮動小数点演算およびエラー分析の基本的な問題 を参照してください。

一部の浮動小数点値は正確ですが、ほとんどの浮動小数点値は近似値です。それらは、いくつかの理想的な値といくつかのエラーです。すべての操作は、理想値とエラー値に適用されます。

最大の問題は、ほぼ等しい2つの数値を操作しようとすることです。右端のビット(エラービット)が結果を左右します。

>>> for i in range(7):
...     a=1/(10.0**i)
...     b=(1/10.0)**i
...     print i, a, b, a-b
... 
0 1.0 1.0 0.0
1 0.1 0.1 0.0
2 0.01 0.01 -1.73472347598e-18
3 0.001 0.001 -2.16840434497e-19
4 0.0001 0.0001 -1.35525271561e-20
5 1e-05 1e-05 -1.69406589451e-21
6 1e-06 1e-06 -4.23516473627e-22

この例では、値が小さくなるにつれて、ほぼ等しい数の差が正解がゼロであるゼロ以外の結果を作成することがわかります。

2
S.Lott

違いはありますが、コンパイラに依存します。最初はvs2003(c ++)で、double型(64ビット浮動小数点)に大きな違いはありませんでした。しかし、vs2010で再度テストを実行すると、乗算で最大4倍速くなる大きな差が検出されました。これを追跡すると、vs2003とvs2010は異なるfpuコードを生成しているようです。

Pentium 4、2.8 GHz、vs2003の場合:

  • 乗算:8.09
  • 部門:7.97

Xeon W3530、vs2003の場合:

  • 乗算:4.68
  • 部門:4.64

Xeon W3530、vs2010の場合:

  • 乗算:5.33
  • 部門:21.05

Vs2003では、ループ内の除算(除数が複数回使用された)が逆の乗算に変換されたようです。 vs2010では、この最適化はもう適用されません(2つの方法の結果が少し異なるためだと思います)。また、分子が0.0になるとすぐにCPUが除算を実行することに注意してください。チップに組み込まれている正確なアルゴリズムはわかりませんが、数に依存している可能性があります。

編集18-03-2013:vs2010の観察

1
gast128

Java Android、Samsung GT-S5830でプロファイル

public void Mutiplication()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a *= 0.5f;
    }
}
public void Division()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a /= 2.0f;
    }
}

結果?

Multiplications():   time/call: 1524.375 ms
Division():          time/call: 1220.003 ms

除算は乗算よりも約20%高速です(!)

1
PiotrK

投稿#24(乗算が高速)と#30の場合と同様に-しかし、両方とも同じくらい簡単に理解できる場合があります。

1*1e-6F;

1/1e6F;

〜どちらも同じように読みやすく、何十億回も繰り返さなければなりません。したがって、乗算は通常より高速であることを知っておくと便利です。

1
Chris

これはばかげた楽しい答えです:

x/2.0notx * 0.5と同等

このメソッドを2008年10月22日に書いたとしましょう。

double half(double x) => x / 2.0;

10年後、このコードを最適化できることがわかりました。メソッドは、アプリケーション全体で数百の式で参照されます。それを変更すると、パフォーマンスが5%向上します。

double half(double x) => x * 0.5;

コードを変更するのは正しい決定でしたか?数学では、2つの式は実際に同等です。コンピュータサイエンスでは、それが常に当てはまるわけではありません。詳細については、 精度の問題の影響の最小化 を参照してください。計算された値が-ある時点で-他の値と比較される場合、Edgeケースの結果を変更します。例えば。:

double quantize(double x)
{
    if (half(x) > threshold))
        return 1;
    else
        return -1;
}

一番下の行は;どちらか一方に落ち着いたら、それに固執してください!

1
l33t

私はどこかで、C/C++では乗算がより効率的であることを読みました。インタプリタ言語に関するアイデアはありません-他のすべてのオーバーヘッドのために、おそらく違いは無視できます。

それがより保守的で読みやすいものに固執する問題にならない限り-私は人々がこれを言うときそれを嫌いますが、それは本当です。

除数が0でないことを保証するサイクルを費やす必要がないため、一般に乗算をお勧めします。除数が定数の場合、これはもちろん当てはまりません。

1
Steve

このように長く興味深い議論の後に、これについての私の見解があります。この質問に対する最終的な答えはありません。一部の人々が指摘したように、ハードウェア(cf piotrk および gast128 )とコンパイラ(cf @ Javier のテスト)の両方に依存します。速度が重要でない場合、アプリケーションが大量のデータをリアルタイムで処理する必要がない場合は、除算を使用して明確にすることを選択できますが、処理速度またはプロセッサ負荷が問題になる場合は、乗算が最も安全です。最後に、アプリケーションがデプロイされるプラットフォームを正確に知らない限り、ベンチマークは無意味です。また、コードを明確にするために、1つのコメントで十分です!

0
Jean-François

さて、加算/減算の運用コストを1と仮定すると、コスト5を乗算し、コストを約20に分割します。

0
matma