問題タブ [square-root]

整数演算のみを使用して整数の平方根を求める方法はいくつかあります。たとえば、これ。これは興味深い読み物であり、非常に興味深い理論でもあります。特に、そのような手法があまり役に立たなくなった私の世代にとってはそうです。

主なことは、浮動小数点演算を使用できないため、newtons メソッドとその派生を除外することです。根を見つけるために私が知っている他の唯一の方法は二項展開ですが、それには浮動小数点演算も必要です。

整数演算のみを使用して整数 n 乗根を計算するための手法/アルゴリズムは何ですか?

編集：これまでのすべての回答に感謝します。それらはすべて、もう少し知的な試行錯誤のようです。もっと良い方法はありませんか？

Edit2:わかりましたので、試行/改善と、ニュートン法またはバイナリ検索なしでこれを行うスマートな方法はないようです。理論的に2つの比較を提供できる人はいますか? この 2 つのベンチマークを何度も実行したところ、非常によく似ていることがわかりました。

私は今、平方根の整数部分と残りを返す平方根を計算するための特定のアルゴリズムを見ています。

たとえば、次のようになります。mysqrt(140) = 11*11 + 19 = integer 11, remainder 19

問題は、平方根を float として計算できるかどうかです。たとえば、140 の平方根は ~ 11.8321 です....?

コメントから編集

左/右シフト、加算、減算などのバイナリ演算のみを使用する固定小数点平方根の VHDL 実装を検討しています。

...アルゴリズムで十分です。

EDIT 2私は実際にこのアルゴリズムをここで読んでいます: http://pioneer.netserv.chula.ac.th/~achatcha/Publications/0012.pdf

ラジカンドを 2n だけ左にシフトすることで、より良い精度が得られるようです。なぜそれが機能しているのかよくわかりませんか？誰か説明してくれませんか

この男：http ：//andrew-hoyer.com/experiments/cloth/は、布をシミュレートするためのjavascriptアルゴリズムを作成しました。彼は、コードが遅すぎるため、テイラー級数を使用して平方根を最適化する必要があると指摘しました。

1. 代わりに、可能なすべての値を事前に計算し、ルックアップテーブルを使用してそれを取得することで、これを最適化できませんでしたか？

2. これはよく使われますか？たとえば、3Dゲームでは、実際に計算を実行しますか、それともすべてのsin、cos、tg、sqrtおよび同様の関数のルックアップテーブルをすでに持っていますか？

3. なぜこれはプロセッサに事前にプログラムされていないのですか？

関数から最初の完全な正方形を見つける方法: f(n)=An²+Bn+C? BとCが与えられます。A、B、C、n は常に整数で、A は常に 1 です。問題は n を見つけることです。

Example: A=1, B=2182, C=3248

最初の完全な正方形の答えは n=16 ですsqrt(f(16))=196。

私のアルゴリズムは n をインクリメントし、平方根が整数かどうかをテストします。

このアルゴリズムは、B または C が大きい場合、答えを見つけるのに n 回の計算が必要になるため、非常に遅くなります。

この計算をより速く行う方法はありますか? 答えを導き出す簡単な公式はありますか？

メソッドを呼び出そうとしていますが、値を返さなければならないdist()というエラーが表示され続けます。dist()

最近、ホットスポットが間違いなくこれであるプログラムをプロファイリングしていました

値 c のみが必要なため、値 d2 は後で使用されません。少し前に、高速逆平方根のカーマック法について読んだことがありますが、これは明らかにそうではありませんが、同様のアルゴリズムが 1/x^2 の計算に役立つかどうか疑問に思っています。

非常に正確な精度が必要です。私のプログラムが gcc -ffast-math オプションで正しい結果を出さないことを確認しました。(g++-4.5)

Math.sqrt();310文字未満の任意の数で正常に機能するようです。

ただし、310文字以上の数値は無限大を返します...

自分でテストしたい場合は、jsfiddlehttp : //jsfiddle.net/gqhk9/2にあります。

とにかく、310文字以上のものを含む数値の平方根を取得する必要があります。

どうすればjsでそれを行うことができますか？

整数の平方根を数値的に計算するのではなく、代数的に単純化したい、つまり√800は28.2842712474619ではなく20√2にする必要があります。

プログラミングでこれを解決する方法が見つかりません:(

この形式で積分を解こうとしています (ここで、a、b、c、d、e、f、および g は定数です)。

Cubic Bezier 曲線の長さを見つけようとしたときに (再帰的な細分を使用せずに)、これに遭遇しました。私の目標は、t の任意の範囲 (つまり、上記の式の f と g) の間でベジエの長さを見つけることができる記号式を作成することです。

私の最初の推測では、平方を完成させることでしたが、ウィキペディアはそれが二次方程式でのみ機能することを明確にしていました。
部品ごとの統合...これではうまくいかないようです。

次の質問 (ただし、このトピックの主題ではありません) は、ベジエを再帰的に分割するよりも実際に高速に使用できますか?

数値（整数）の平方根（整数）を計算する最速の方法を探していました。私はウィキペディアでこの解決策に出くわしました。これは、数値の平方根（完全な平方の場合）または最も近い下の完全な平方の平方根（指定された数値が完全な平方でない場合）を見つけます。

アルゴリズムをトレースするために多くのテストを実行しようとしましたが、内部の部分が理解できないようですwhile(bit!=0)。誰かが私にこの部分を説明できますか？