インテル アーキテクチャのリファレンス マニュアルhttp://www.cs.princeton.edu/courses/archive/spr12/cos217/reading/ia32opt.pdfを何気なく読んでいて、命令のレイテンシとスループットの付録を読んでいたときに、 sqrt 命令のレイテンシ (実行コアが命令を形成するすべての μop の実行を完了するために必要なクロック サイクル数) が、除算のレイテンシ (ページ上) とまったく同じであることを発見しました。 C-28) 命令 -- 少なくとも一部のマイクロアーキテクチャでは。数値は、単精度、倍精度、および拡張精度に対して、それぞれ 30、40、および 44 クロック サイクルでした。
私の質問は、sqrt 命令を div 命令と同じくらい大きなプロセッサ シンクにする方法を教えてください。私は常に、sqrt 命令はどの言語でもコストがかかるという印象を受けてきました。
あまり知られていませんが、シフト操作に関して除算を行うのと同じくらい高速に平方根を計算するアルゴリズムがあります。これらはニュートン近似ではありません。
(Sqrt in) 2 進法 (基数 2)を参照してください。私はこれを最初に Knuth の Seminumerical Algorithms の本で見、1970 年代初頭に 16 ビットのミニコンピューターで除算と同じ速度で sqrt をコーディングするために使用しました。ループのコアは、2 ビットをシフトアウトし、平方根ビットを計算して、繰り返します。したがって、合計シフト == ビット数であり、従来の除算と同じです。
チップ上でシフトと比較の方法で除算を行う場合、平方根を非常に簡単に実装できます。
理論的には、除算は、 http://en.wikipedia.org/wiki/Newton%27s_methodで計算できる平方根を含む多くの関数と漸近的に同じ次数です。ニュートン法の反復回数は、毎回正しい桁数が 2 倍になるため、少ないです。初期の反復は、完全な精度で実行する必要がないため安価です。反復に期待する精度のみが必要です。漸近的に、結果は、すべてが単一の完全精度除算とほぼ同じくらい高価です。httpを参照してください。 //en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
チップ上では、両方に高度に調整された特別な目的の方法を使用する可能性がありますが、完全な精度の結果を得るために最後にチップの乗算パイプラインを通過する回数がコストの最大の要因である場合、それらは同じコストになる可能性があります。高速テーブルルックアップまたはその他の近似解の後。