22

浮動小数点除算を行うアルゴリズムの手順は何ですか?

結果が掛け算よりも遅いのはなぜですか?

手で除算するのと同じ方法ですか？除数で除算し、結果を減算して剰余を取得し、数値を再度調整して、剰余が特定の値未満になるまで繰り返しますか?

また、実行する代わりにパフォーマンスが向上するのはなぜですか

a = b / c

私たちはします

d = 1 / c
a = b * d

?

編集：基本的に、誰かが重みの割り当てに基づいて競合者間で値を分配するように頼んだので、私は尋ねていました. これをすべて整数で行った後、float に変換するように求められたため、パフォーマンスが低下しました。CまたはC++がこれらの操作をどのように実行して速度を低下させるかを知りたいだけでした。

4

6 に答える 6

23

FPU の除算では、多くの場合、基本的にニュートン ラフソン (または他のアルゴリズム) を使用して逆数を取得し、その逆数を掛けます。そのため、逆数演算は一般的な除算演算よりもわずかに高速です。

この HP の論文(これは、私が出会った Newton-Raphson について話しているほとんどの論文よりも実際には理解しやすいものです) は、浮動小数点除算について次のように述べています。

浮動小数点除算と平方根は、加算と乗算よりも計算にかなり時間がかかります。後者の 2 つは直接計算されますが、前者は通常反復アルゴリズムで計算されます。最も一般的な方法は、除算のないニュートン ラフソン反復法を使用して、分母の逆数 (除算) または逆数平方根の近似値を取得し、分子 (除算) または入力引数 (平方根) で乗算することです。 .

于 2009-02-03T08:26:07.593 に答える
18

ハードウェアの観点から見ると、除算は反復アルゴリズムであり、かかる時間はビット数に比例します。現在使用されている最速の除算では、反復ごとに 4 ビットの結果を生成する radix4 アルゴリズムが使用されます。32 ビット除算の場合、少なくとも 8 ステップが必要です。

乗算は、ある程度並列に実行できます。詳細に立ち入ることなく、大きな乗算をいくつかの小さな独立した乗算に分割できます。これらの乗算は、ビットレベルになるまで分解するか、以前に停止してハードウェアで小さなルックアップテーブルを使用することができます。これにより、乗算ハードウェアはシリコンの不動産の観点からは重くなりますが、非常に高速でもあります。これは、従来のサイズと速度のトレードオフです。

並列計算結果を組み合わせるには log2 ステップが必要なため、32 ビットの乗算には 5 つの論理ステップが必要です (最小値まで下げると)。幸いなことに、これらの 5 つのステップは、除算のステップよりもかなり単純です (追加だけです)。つまり、実際の乗算はさらに高速です。

于 2009-02-03T11:07:03.103 に答える
6

ウィキペディアの記事除算アルゴリズムで説明されているように、コンピューターの除算には2つの主要なアプローチがあります。

遅い部門

次の漸化式を使用して、反復ごとに1桁を検索します。 partialRemainder[j+1] = radix * partialRemainder[j] - quotientDigit[n-(j+1)]*denominator

高速除算

見積もりから始まり、商に収束します。正確さは、反復回数によって異なります。

ニュートン-ラプソン分割（ごく簡単に）：

  1. 逆数の推定値を計算します。
  2. 逆数のより正確な推定値を計算します。
  3. 被除数に逆数を掛けて商を計算します。
于 2009-02-03T07:35:01.190 に答える
1

実行してもパフォーマンスは向上しません

d = 1 / c
a = b * d

あなたはおそらく意味します：

d = 1 / c
a1 = b1 * d
a2 = b2 * d

このようにして、分割は1回だけ行われます。

除算自体は乗算より遅いですが、詳細はわかりません。基本的な理由は、sinやsqrtなどの関数と同様に、数学的に複雑であるためです。IIRC、乗算は平均的なCPUで約10サイクルかかりますが、除算は約50以上かかります。

それが実際にどのように行われるかは、ジョン・マルダーによってうまく説明されました。

于 2009-02-03T07:19:58.630 に答える
0

関連するハードウェアについて考えてみてください。乗算よりも除算に時間がかかる理由がよくわかります。どちらの演算も浮動小数点ユニット（FPU）レベルで実行され、積分ALUの世界でも、除算回路は乗算回路よりもはるかに忙しい場所です。データは最下位桁まで順序付けられているだけでなく、IEEE 754標準によって順序付けられているため、これは浮動小数点の世界でのみより苦痛だと思います。

四捨五入に関しては、ゲート間を移動する信号がアースにはんだ付けされる場所が重要です。それが起こるところで、あなたは数字を失います。丸めではなく、切り捨てと同じくらいです。

それとも、整数だけを使用して浮動小数点演算をシミュレートすることについて質問していましたか？

于 2009-02-03T07:33:07.920 に答える
0

浮動小数点除算は整数除算よりも遅くはありませんが、コンパイラは同じ最適化を実行できない場合があります。

たとえば、コンパイラは 3 の間の整数除算を乗算とバイナリ シフトに置き換えることができます。また、2.0 の浮動小数点数の除算を 0.5 の乗算に置き換えることはできますが、3.0 の除算を 1/3.0 の乗算に置き換えることはできません。1/3.0 は 2 進数を使用して正確に表すことができないため、丸め誤差によって除算の結果が変わる可能性があります。
コンパイラは、アプリケーションが丸め誤差にどの程度影響を受けやすいかを認識していないため (たとえば、気象シミュレーションを行っていたとします。「バタフライ効果」を参照してください)、最適化を行うことができません。

于 2009-02-03T12:38:00.080 に答える