8

私は最近、Vector 3 クラスを作成し、レビュー用に normalize() 関数を友人に提出しました。彼は、それは良いことだと言いましたが、可能な場合は逆数を掛けるべきだと言いました。なぜなら、「掛け算は割り算よりも CPU 時間のほうが安い」からです。

私の質問は、なぜですか？

4

3 に答える 3

10

ハードウェアがより簡単に実装できる基本演算 (加算、減算、シフト、比較) の観点から考えてみてください。些細なセットアップでも乗算には、そのような基本的なステップが少なくて済みます-さらに、さらに高速な高度なアルゴリズムが提供されます-たとえば、ここを参照してください...しかし、ハードウェアは一般にそれらを利用しません(おそらく非常に特殊なハードウェアを除く)。たとえば、ウィキペディアの URL にあるように、「Toom–Cook はサイズ N の乗算 5 回のコストでサイズ N の 3 乗乗算を行うことができます」 - これは非常に大きな数に対して非常に高速です (Fürer のアルゴリズム、かなり最近の開発、できますΘ(n ln(n) 2Θ(ln*(n)))-- 繰り返しますが、ウィキペディアのページとそこからのリンクを参照してください)。

ウィキペディアによると、部門は本質的に遅いです。最高のアルゴリズムでさえ (HW に実装されているものもありますが、掛け算の最高のアルゴリズムほど洗練されていないため、複雑ではありません;-) 掛け算のアルゴリズムには太刀打ちできません。

それほど大きくない数値で問題を定量化するために、GMPの使いやすい Python ラッパーであるgmpyを使用した結果をいくつか示します。 . 遅い (第 1 世代;-) Macbook Pro の場合:

$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a*ib'
1000000 loops, best of 3: 0.186 usec per loop
$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a/b'
1000000 loops, best of 3: 0.276 usec per loop

ご覧のように、この小さなサイズ (数値のビット数) でさえ、まったく同じ速度に夢中になっている人々によってライブラリが最適化されている場合、逆数による乗算は、除算にかかる時間の 1/3 を節約できます。

これらの数ナノ秒が生死にかかわる問題になるのはまれな状況だけかもしれませんが、そうである場合、もちろん、同じ値で繰り返し除算している場合 (1.0/b操作を償却するために!)、この知識は命の恩人になることができます。

(多くの場合、[ Python や Fortran のような「累乗」演算子を持つ言語]x*xと比較して時間を節約できます。また、Horner の多項式計算のスキームは、累乗を繰り返すよりもはるかに優れています。オペレーション！-）。x**2**

于 2009-07-13T04:26:49.873 に答える
6

小学校時代を思い出すと、掛け算は足し算より難しく、割り算は掛け算より難しかったことを思い出すでしょう。CPUの場合は何も変わりません。

また、逆数の計算には除算が含まれることを思い出してください。したがって、逆数を 1 回計算して 3 回使用しない限り、速度は向上しません。

于 2009-07-13T04:30:03.907 に答える
0

(float) 除算の CPU 演算は、乗算よりもはるかに複雑です。CPU はさらに多くのことを行う必要があります。私はハードウェアについて詳しくはありませんが、一般的な除算の実装 (たとえば、ニュートン ラフソンアルゴリズムに基づく) に関する多くの情報を見つけることができます。

また、CPU パフォーマンスを向上させるために、除算ではなく逆数の乗算を常に使用するように注意します。まったく同じ結果が得られない場合があります。これは、アプリケーションによっては問題になる場合と問題にならない場合があります。

于 2009-07-13T04:22:11.487 に答える