問題タブ [sqrt]

（編集：これに「測定がうまくいかないことの教訓」というタイトルを付けましょう。ただし、何が不一致の原因であるかはまだ正確にはわかりません。）

ここで Mark Crowne による非常に高速な整数平方根関数を見つけました。少なくとも私のマシンの GCC では、これは明らかに私がテストした中で最速の整数平方根関数です (Hacker's Delight、このページ、および標準ライブラリの floor(sqrt()) の関数を含む)。

フォーマットを少し整理し、変数の名前を変更し、固定幅型を使用すると、次のようになります。

INNER_ISQRT マクロは、ローカルであり、不要になるとすぐに未定義になるため、それほど悪いものではありません。それにもかかわらず、原則としてインライン関数に変換したいと思います。インライン関数はマクロと同じくらい高速であるという主張をいくつかの場所 (GCC のドキュメントを含む) で読んだことがありますが、速度に影響を与えずに変換するのに苦労しました。

私の現在の反復は次のようになります (always_inline 属性に注意してください。これは、適切な測定のために挿入したものです)。

私が何をしても、インライン関数は常にマクロよりも遅いです。-O2 ビルドを使用した (2^28 - 1) 反復の場合、マクロ バージョンは一般に約 2.92 秒で、インライン バージョンは一般に約 3.25 秒です。編集:前に 2^32 - 1 回の繰り返しと言いましたが、変更したことを忘れていました。全色域にはかなり時間がかかります。

コンパイラが愚かでインライン化を拒否している可能性があります (always_inline 属性に注意してください!)。（アセンブリを確認してみましたが、プログラムの一部としては複雑すぎました。もちろん、関数だけをコンパイルしようとすると、オプティマイザはすべてを省略しました.GCCのnoobishnessのためにライブラリとしてコンパイルするのに問題があります. .)

要するに、これをインラインとして速度を落とさずに書く方法はありますか? (私はプロファイリングしていませんが、sqrt は、現在関心のあるプログラム以外の多くのプログラムで使用している可能性があるため、常に高速化する必要がある基本的な操作の 1 つです。さらに、私はただ興味があります.)

テンプレートを使用して定数値を「焼き込む」ことさえ試みましたが、他の2つのパラメーターがヒットを引き起こしている可能性が高いと感じています（ローカル変数を直接使用するため、マクロはそれを回避できます）。 .まあ、それかコンパイラが頑固にインライン化を拒否しています。

更新: 以下の user1034749 は、それらを別々のファイルに入れてコンパイルすると、両方の関数から同じアセンブリ出力を取得しています。彼の正確なコマンド ラインを試してみましたが、彼と同じ結果が得られました。すべての意図と目的のために、この質問は解決されています。

ただし、測定結果が異なる理由を知りたいです。明らかに、私の測定コードまたは元のビルド プロセスが原因で、状況が異なっていました。以下にコードを掲載します。どんな取引だったか知ってる人いますか？私のコンパイラは実際には私の main() 関数のループで mcrowne_isqrt() 関数全体をインライン化しているのかもしれませんが、他のバージョン全体をインライン化しているわけではありませんか?

更新 2 (コードをテストする前に圧縮): テストの順序を入れ替えてインライン バージョンを最初にすると、インライン バージョンはマクロ バージョンよりも同じ量だけ速くなることに注意してください。これはキャッシングの問題ですか、それともコンパイラが 1 つの呼び出しをインライン化していて、他の呼び出しをインライン化していないのでしょうか?

更新 3: テストの順序に依存するタイミングなしで、さまざまな関数のタイミングを確実に比較する方法がまだわかりません。ヒントをいただければ幸いです。

ただし、これを読んでいる他の誰かが高速な sqrt 実装に興味を持っている場合は、言及する必要があります: Mark Crowne のコード テストは、私が試した他の純粋な C/C++ バージョンよりもかなり高速です (テストの信頼性の問題にもかかわらず)。 SSE コードは、スカラーの 32 ビット整数 sqrt の場合、さらに少し高速になるようです。ただし、精度を失うことなく、本格的な 64 ビット符号なし整数入力に対して一般化することはできません (また、最初の符号付き変換は、値 >= 2^63 を処理するために組み込みのロードに置き換える必要があります)。

Rubyで本当に大きな数の平方根を計算しようとしています。私が抱えている問題は、Math.sqrt関数が次のようになっていることです。

sqrt(numeric) → float

非常に大きな数をフィードすると、FloatDomainError：Infinityが表示されます。

sqrt()BigNumを返すための最良の方法は何ですか？これにはおそらく宝石がありますか、それとも平方根を計算するために独自の関数を作成する必要がありますか？

その場合、これを行うための最も簡単な方法は何ですか？テイラー級数？数値の平方根は常に整数になります。

Dobb博士の記事「固定小数点演算による数学集約型アプリケーションの最適化」で説明されているAnthonyWilliamsの固定小数点ライブラリを使用して、 RhumbLineメソッドを使用して2つの地理的ポイント間の距離を計算しています。

これは、ポイント間の距離が大きい場合（数キロメートルを超える場合）は十分に機能しますが、距離が短い場合は非常に不十分です。最悪の場合、2つのポイントが等しいかほぼ等しい場合、結果は194メートルの距離になりますが、1メートル以上の距離では少なくとも1メートルの精度が必要です。

倍精度浮動小数点の実装と比較して、fixed::sqrt()関数の問題を特定しました。この関数は、小さな値ではパフォーマンスが低下します。

の結果を修正することfixed::sqrt(0)は、それを特殊なケースとして扱うことで簡単ですが、誤差が194メートルから始まり、距離が長くなるにつれてゼロに向かって収束する、ゼロ以外の小さな距離の問題は解決されません。おそらく、ゼロに向けて精度を少なくとも1桁改善する必要があります。

アルゴリズムは上記fixed::sqrt()のリンク先の記事の4ページで簡単に説明されていますが、改善できるかどうかは言うまでもなく、それに従うのに苦労しています。関数のコードを以下に示します。

m_nValは内部固定小数点表現値であり、でint64_tあり、表現はQ36.28形式（fixed_resolution_shift= 28）を使用することに注意してください。表現自体は、少なくとも小数点以下8桁まで十分な精度があり、赤道弧の一部は約0.14メートルの距離に適しているため、制限は固定点表現ではありません。

ラムライン法の使用は、このアプリケーションの標準化団体の推奨事項であるため、変更できません。いずれの場合も、アプリケーションの他の場所または将来のアプリケーションで、より正確な平方根関数が必要になる可能性があります。

質問：fixed::sqrt()有界で決定論的な収束を維持しながら、ゼロ以外の小さな値のアルゴリズムの精度を向上させることは可能ですか？

追加情報 上記の表を生成するために使用されるテストコード：

結論ジャスティン・ピールの解決策と分析、および「固定小数点演算の無視された芸術」の アルゴリズムとの比較に照らして、私は後者を次のように適応させました。

これによりはるかに高い精度が得られますが、必要な改善は達成されません。Q36.28形式だけでも、必要な精度が得られますが、数ビットの精度を失うことなくsqrt（）を実行することはできません。ただし、いくつかの水平思考はより良い解決策を提供します。私のアプリケーションは、計算された距離をある距離制限に対してテストします。後から考えると、かなり明白な解決策は、距離の2乗を限界の2乗に対してテストすることです。

私のプログラムの一部は、sqrt浮動小数点数を計算することです。私が書いsqrt(1.0f);たとき、私はプログラムをコンパイルすることに成功しましたが、私が書いたときsqrt(-1.0f); 、コンパイルは失敗しましたundefined reference to 'sqrt'-この場合、nan値が返されると思います... 私はgccを使用してプログラムをコンパイルします。Visual Studio でコンパイルすると、sqrt に負の引数を指定して正常にコンパイルされます。問題を解決する方法 ありがとう

FPGAに実装される可能性が最も高い効率的な平方根アルゴリズムについて、もう少し情報を見つけようとしています。多くのアルゴリズムがすでに見つかっていますが、たとえば Intel や AMD のアルゴリズムはどれですか? 効率的とは、非常に高速であるか、多くのメモリを必要としないことを意味します。

編集: 質問は一般に浮動小数点数であり、ほとんどのハードウェアは IEEE 754 標準を実装しているため、数値は次のように表されます: 1 符号ビット、8 ビット バイアス指数、23 ビット仮数。

ありがとう！

なぜ出力は-3を期待して、3を与えています。cでそのような前処理を処理する方法は？

私は自分の問題に似た質問を検索しました。同様の問題。しかし、私の問題は、TurboCコンパイラv3.0を使用する場合です。math.hファイルに対して追加の作業を行う必要がありますか？助けてください。

出力は次のようになります。

平方根の＃を入力します。

64

a = 0.000000

a = 0.000000、平方根は0.000000です

私の目標は***、平方根が負の場合に出力することです。nanしかし、デフォルトのテキストを次のように変更する方法が思いつきません***

では、それを可能にするにはif文に何を書けばよいのでしょうか。または、y が nan であるかどうかを確認してから印刷する別の方法があるかもしれません*

コードの for ループでエラーが発生しますfor ( j = 3; j <=sqrt(num); j +=2)。

オーバーロードされた関数「sqrt」の複数のインスタンスが引数リストと一致します。

どうすれば解決できますか?

このコードを実行しての平方根を計算してx[i][j] - y[j]いますが、意味がありません。

最初outFileの値は元の値である0を出力しますが、2番目の値はを出力し-1.#INDます。