x'がx^n <= yとなる最大の整数である場合、x'はyのn乗根です。x、x'、yはすべて整数です。そのようなn乗根を計算する効率的な方法はありますか？これは通常n番目のルートアルゴリズムによって行われることは知っていますが、組み込みシステムを使用しているため、ここでの難しさはすべてが整数であるということです。
ところで、私は1からyまで二分探索して、x ^ n <= yとなる最大のxを特定しようとしましたが、特にnが大きい場合、x ^ nがオーバーフローしやすいため、機能しません。
2952 次
3 に答える
10
x ^ yがオーバーフローしないように、最大xの指定されたyのテーブルを格納します。これらの値を二分探索に使用します。そうすれば、オーバーフローがなくなり、xとnが同じ（整数）型である限り機能するきちんとしたアルゴリズムになります。右？
注：y> 32の場合、xの最大値は32ビット整数の場合は2です...つまり、テーブルは、システムが理解できる整数のビット数とほぼ同じサイズになります。
于 2011-09-13T20:52:09.857 に答える
2
整数の根だけを探していますか？または、34の5乗根が2.024であることを知りたいですか...？それとも「2」で十分ですか？小数点以下の桁数が必要な場合は、ある種の浮動小数点または固定小数点の計算を行う必要があります。
コンピューティングのプリンシパルルートを読み、最初のニュートン近似についてそれが何を言っているかに注意する必要があります。約0.03％の誤差が十分に近い場合は、これを使用することをお勧めします。おそらく、初期近似を行うために使用できるテーブルを作成することをお勧めします。このテーブルは思ったほど大きくはありません。2^32の立方根は約1,626です。平方は簡単に計算でき、x^2とx^3を生成できれば、x^nを簡単に生成できます。したがって、近似を行うのは非常に簡単です。
もう1つの可能性は、自分で根のテーブルを作成し、ある種の補間を使用することです。繰り返しますが、平方根を特殊なケースとして扱う場合、そのテーブルはそれほど大きくする必要はありません。2 ^ 32の5乗根は100未満なので、かなり広い範囲の根を取得するためにかなり小さなテーブルを話していることになります。
于 2011-09-13T21:00:54.427 に答える
1
ウィキペディアの記事にあるニュートンラプソン法を使用するのが最善の方法だと思います。
適切な開始値は、入力のビット長を。で割って計算できますn。各反復では、切り捨てる整数除算を使用します。x次のような値が見つかるまで繰り返しますx^n <= y < (x+1)^n。
オーバーフローを避けるように注意する必要があります。他の答えが言うように、あなたはそれをするために最大ルートのテーブルを使うことができますn < bit size（より大きくなるnために答えは常に1です、を除いてy = 0）。
于 2011-09-14T11:00:27.287 に答える