整数の最も正確な平方根を見つける独自の関数をどのように作成しますか?
グーグルで調べた後、これを見つけました（元のリンクからアーカイブされています）が、最初に完全には取得できませんでした.2番目に、それも概算です.
平方根を (実際の根に) 最も近い整数または浮動小数点数として想定します。
質問する
175489 次
19 に答える
85
以下は、N > 0 の floor(sqrt(N)) を計算します。
x = 2^ceil(numbits(N)/2)
loop:
y = floor((x + floor(N/x))/2)
if y >= x
return x
x = y
これは、Crandall & Pomerance の "Prime Numbers: A Computational Perspective" で与えられたニュートンの方法のバージョンです。このバージョンを使用する必要があるのは、自分が何をしているかを知っている人が、それが平方根の下限に正確に収束することを証明しており、単純であるため実装エラーが発生する可能性が小さいためです。また、高速です (ただし、さらに高速なアルゴリズムを構築することは可能ですが、それを正しく行うのははるかに複雑です)。適切に実装された二分探索は、非常に小さい N の場合は高速になる可能性がありますが、ルックアップ テーブルを使用することもできます。
最も近い整数に丸めるには、上記のアルゴリズムを使用して t = floor(sqrt(4N)) を計算します。t の最下位ビットが設定されている場合は、x = (t+1)/2 を選択します。それ以外の場合は t/2 を選択します。これは引き分けで切り上げられることに注意してください。また、剰余が非ゼロかどうか (つまり、t^2 == 4N かどうか) を調べて、切り捨て (または偶数に丸める) こともできます。
浮動小数点演算を使用する必要がないことに注意してください。実際、そうすべきではありません。このアルゴリズムは、完全に整数を使用して実装する必要があります (特に、floor() 関数は、通常の整数除算を使用する必要があることを示しているだけです)。
于 2009-10-26T12:49:38.593 に答える
39
必要に応じて、単純な分割統治戦略を使用できます。他の方法ほど速くは収束しませんが、初心者にとっては理解しやすいかもしれません。さらに、これは O(log n) アルゴリズム (反復ごとに探索空間を半分にする) であるため、32 ビット浮動小数点数の最悪のケースは 32 反復になります。
62.104 の平方根が必要だとしましょう。0 とその中間の値を選び、2 乗します。2 乗が自分の数字よりも大きい場合は、中点より小さい数字に集中する必要があります。低すぎる場合は、より高いものに集中してください。
実際の数学では、検索空間を永遠に 2 つに分割し続けることができます (有理平方根がない場合)。実際には、コンピューターは最終的に精度を使い果たし、近似値が得られます。次の C プログラムは、この点を示しています。
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[]) {
float val, low, high, mid, oldmid, midsqr;
int step = 0;
// Get argument, force to non-negative.
if (argc < 2) {
printf ("Usage: sqrt <number>\n");
return 1;
}
val = fabs (atof (argv[1]));
// Set initial bounds and print heading.
low = 0;
high = mid = val;
oldmid = -1;
printf ("%4s %10s %10s %10s %10s %10s %s\n",
"Step", "Number", "Low", "High", "Mid", "Square", "Result");
// Keep going until accurate enough.
while (fabs(oldmid - mid) >= 0.00001) {
oldmid = mid;
// Get midpoint and see if we need lower or higher.
mid = (high + low) / 2;
midsqr = mid * mid;
printf ("%4d %10.4f %10.4f %10.4f %10.4f %10.4f ",
++step, val, low, high, mid, midsqr);
if (mid * mid > val) {
high = mid;
printf ("- too high\n");
} else {
low = mid;
printf ("- too low\n");
}
}
// Desired accuracy reached, print it.
printf ("sqrt(%.4f) = %.4f\n", val, mid);
return 0;
}
ここにいくつかの実行がありますので、うまくいけばそれがどのように機能するかがわかります。77 の場合:
pax> sqrt 77
Step Number Low High Mid Square Result
1 77.0000 0.0000 77.0000 38.5000 1482.2500 - too high
2 77.0000 0.0000 38.5000 19.2500 370.5625 - too high
3 77.0000 0.0000 19.2500 9.6250 92.6406 - too high
4 77.0000 0.0000 9.6250 4.8125 23.1602 - too low
5 77.0000 4.8125 9.6250 7.2188 52.1104 - too low
6 77.0000 7.2188 9.6250 8.4219 70.9280 - too low
7 77.0000 8.4219 9.6250 9.0234 81.4224 - too high
8 77.0000 8.4219 9.0234 8.7227 76.0847 - too low
9 77.0000 8.7227 9.0234 8.8730 78.7310 - too high
10 77.0000 8.7227 8.8730 8.7979 77.4022 - too high
11 77.0000 8.7227 8.7979 8.7603 76.7421 - too low
12 77.0000 8.7603 8.7979 8.7791 77.0718 - too high
13 77.0000 8.7603 8.7791 8.7697 76.9068 - too low
14 77.0000 8.7697 8.7791 8.7744 76.9893 - too low
15 77.0000 8.7744 8.7791 8.7767 77.0305 - too high
16 77.0000 8.7744 8.7767 8.7755 77.0099 - too high
17 77.0000 8.7744 8.7755 8.7749 76.9996 - too low
18 77.0000 8.7749 8.7755 8.7752 77.0047 - too high
19 77.0000 8.7749 8.7752 8.7751 77.0022 - too high
20 77.0000 8.7749 8.7751 8.7750 77.0009 - too high
21 77.0000 8.7749 8.7750 8.7750 77.0002 - too high
22 77.0000 8.7749 8.7750 8.7750 76.9999 - too low
23 77.0000 8.7750 8.7750 8.7750 77.0000 - too low
sqrt(77.0000) = 8.7750
62.104 の場合:
pax> sqrt 62.104
Step Number Low High Mid Square Result
1 62.1040 0.0000 62.1040 31.0520 964.2267 - too high
2 62.1040 0.0000 31.0520 15.5260 241.0567 - too high
3 62.1040 0.0000 15.5260 7.7630 60.2642 - too low
4 62.1040 7.7630 15.5260 11.6445 135.5944 - too high
5 62.1040 7.7630 11.6445 9.7037 94.1628 - too high
6 62.1040 7.7630 9.7037 8.7334 76.2718 - too high
7 62.1040 7.7630 8.7334 8.2482 68.0326 - too high
8 62.1040 7.7630 8.2482 8.0056 64.0895 - too high
9 62.1040 7.7630 8.0056 7.8843 62.1621 - too high
10 62.1040 7.7630 7.8843 7.8236 61.2095 - too low
11 62.1040 7.8236 7.8843 7.8540 61.6849 - too low
12 62.1040 7.8540 7.8843 7.8691 61.9233 - too low
13 62.1040 7.8691 7.8843 7.8767 62.0426 - too low
14 62.1040 7.8767 7.8843 7.8805 62.1024 - too low
15 62.1040 7.8805 7.8843 7.8824 62.1323 - too high
16 62.1040 7.8805 7.8824 7.8815 62.1173 - too high
17 62.1040 7.8805 7.8815 7.8810 62.1098 - too high
18 62.1040 7.8805 7.8810 7.8807 62.1061 - too high
19 62.1040 7.8805 7.8807 7.8806 62.1042 - too high
20 62.1040 7.8805 7.8806 7.8806 62.1033 - too low
21 62.1040 7.8806 7.8806 7.8806 62.1038 - too low
22 62.1040 7.8806 7.8806 7.8806 62.1040 - too high
23 62.1040 7.8806 7.8806 7.8806 62.1039 - too high
sqrt(62.1040) = 7.8806
49 の場合:
pax> sqrt 49
Step Number Low High Mid Square Result
1 49.0000 0.0000 49.0000 24.5000 600.2500 - too high
2 49.0000 0.0000 24.5000 12.2500 150.0625 - too high
3 49.0000 0.0000 12.2500 6.1250 37.5156 - too low
4 49.0000 6.1250 12.2500 9.1875 84.4102 - too high
5 49.0000 6.1250 9.1875 7.6562 58.6182 - too high
6 49.0000 6.1250 7.6562 6.8906 47.4807 - too low
7 49.0000 6.8906 7.6562 7.2734 52.9029 - too high
8 49.0000 6.8906 7.2734 7.0820 50.1552 - too high
9 49.0000 6.8906 7.0820 6.9863 48.8088 - too low
10 49.0000 6.9863 7.0820 7.0342 49.4797 - too high
11 49.0000 6.9863 7.0342 7.0103 49.1437 - too high
12 49.0000 6.9863 7.0103 6.9983 48.9761 - too low
13 49.0000 6.9983 7.0103 7.0043 49.0598 - too high
14 49.0000 6.9983 7.0043 7.0013 49.0179 - too high
15 49.0000 6.9983 7.0013 6.9998 48.9970 - too low
16 49.0000 6.9998 7.0013 7.0005 49.0075 - too high
17 49.0000 6.9998 7.0005 7.0002 49.0022 - too high
18 49.0000 6.9998 7.0002 7.0000 48.9996 - too low
19 49.0000 7.0000 7.0002 7.0001 49.0009 - too high
20 49.0000 7.0000 7.0001 7.0000 49.0003 - too high
21 49.0000 7.0000 7.0000 7.0000 49.0000 - too low
22 49.0000 7.0000 7.0000 7.0000 49.0001 - too high
23 49.0000 7.0000 7.0000 7.0000 49.0000 - too high
sqrt(49.0000) = 7.0000
于 2009-10-26T07:34:27.323 に答える
17
X の平方根を計算する単純な (しかしそれほど高速ではない) メソッド:
squareroot(x)
if x<0 then Error
a = 1
b = x
while (abs(a-b)>ErrorMargin)
a = (a+b)/2
b = x/a
endwhile
return a;
例: 平方根(70000)
a b
1 70000
35001 2
17502 4
8753 8
4381 16
2199 32
1116 63
590 119
355 197
276 254
265 264
ご覧のとおり、平方根の上限と下限を定義し、そのサイズが許容範囲内になるまで境界を狭めます。
より効率的な方法がありますが、これはプロセスを示しており、理解しやすいものです。
整数を使用すると無限ループが発生する場合は、エラーマージンを 1 に設定するように注意してください。
于 2009-10-26T07:09:15.940 に答える
14
逆平方根 1/sqrt(x) を計算する非常に興味深い方法を指摘させてください。これは、気が遠くなるほど速いため、ゲーム デザインの世界では伝説となっています。または、次の投稿をお読みください。
http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/
PS: 平方根が欲しいだけなのはわかっていますが、地震のエレガンスが私の側のすべての抵抗を克服しました :)
ところで、上記の記事のどこかで退屈なニュートン・ラフソン近似についても語られています。
于 2009-10-26T06:52:46.533 に答える
9
もちろん概算です。これが浮動小数点数の計算方法です。
とにかく、標準的な方法はニュートンの方法です。これは、Taylor の級数を使用するのとほぼ同じですが、すぐに頭に浮かぶ別の方法です。
于 2009-10-26T06:40:50.957 に答える
8
Python で任意の精度で平方根を計算する
#!/usr/bin/env python
import decimal
def sqrt(n):
assert n > 0
with decimal.localcontext() as ctx:
ctx.prec += 2 # increase precision to minimize round off error
x, prior = decimal.Decimal(n), None
while x != prior:
prior = x
x = (x + n/x) / 2 # quadratic convergence
return +x # round in a global context
decimal.getcontext().prec = 80 # desirable precision
r = sqrt(12345)
print r
print r == decimal.Decimal(12345).sqrt()
出力：
111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True
于 2009-10-26T08:35:12.703 に答える
7
Facebookなどからよく聞かれる面接の質問です。面接でニュートン法を使うのは良い考えではないと思います。あなたが本当に理解していないときに、インタビュアーがニュートン法のメカニズムをあなたに尋ねたらどうしますか？
私はJavaでバイナリ検索ベースのソリューションを提供しましたが、これは誰もが理解できると思います。
public int sqrt(int x) {
if(x < 0) return -1;
if(x == 0 || x == 1) return x;
int lowerbound = 1;
int upperbound = x;
int root = lowerbound + (upperbound - lowerbound)/2;
while(root > x/root || root+1 <= x/(root+1)){
if(root > x/root){
upperbound = root;
} else {
lowerbound = root;
}
root = lowerbound + (upperbound - lowerbound)/2;
}
return root;
}
ここで私のコードをテストできます：leetcode：sqrt（x）
于 2013-02-23T23:42:56.090 に答える
6
Integer Square Rootsに関する素晴らしい記事を見つけました。
これは、そこに表示されるわずかに改善されたバージョンです。
unsigned long sqrt(unsigned long a){
int i;
unsigned long rem = 0;
unsigned long root = 0;
for (i = 0; i < 16; i++){
root <<= 1;
rem = (rem << 2) | (a >> 30);
a <<= 2;
if(root < rem){
root++;
rem -= root;
root++;
}
}
return root >> 1;
}
于 2009-10-26T13:00:12.510 に答える
4
私が学校で学んだアルゴリズムがあります。これを使用して、正確な平方根を計算できます (または、根が無理数の場合は任意の精度で計算できます)。ニュートンのアルゴリズムよりも明らかに遅いですが、正確です。531.3025 の平方根を計算したいとします。
最初に、小数点から始まる数値を 2 桁のグループに分割します:
{5}{31}.{30}{25}
次に:
1) 最初のグループの最も近い平方根を見つけます。最初のグループの実際の平方根: sqrt({5}) >= 2. この平方根は、最終的な答えの最初の桁です。最終的な平方根の既に見つかった数字を B とします。したがって、現時点では B = 2.2
) 次に、{5} と B^2 の差を計算します: 5 - 4 = 1.3
) 以降のすべての2 桁のグループは次のことを行います:
剰余に 100 を掛け、それを 2 番目のグループに追加します: 100 + 31 = 131.
131 >=((B*20) + X)*X のように、X - ルートの次の数字を見つけます。X = 3. 43 * 3 = 129 < 131. これで B = 23 です。また、小数点の左側に 2 桁のグループがなくなったため、最終ルートのすべての整数桁が見つかりました。
4) {30} と {25} についても同じことを繰り返します。{30} :
131 - 129 = 2.2 * 100 + 30 = 230 >= (23*2*10 + X) * X -> X = 0 -> B = 23.0
{25} : 230 - 0 = 230. 230 * 100 + 25 = 23025. 23025 >= (230 * 2 * 10 + X) * X -> X = 5 -> B = 23.05
最終結果 = 23.05.
このようにするとアルゴリズムは複雑に見えますが、除算を行わずに平方根を計算することを除けば、学校で習った「長い除算」に使用するのと同じ表記法を使用して紙の上で行うと、はるかに簡単になります。
于 2013-01-10T18:55:27.470 に答える
3
最初に頭に浮かぶのは、これはバイナリ検索を使用するのに適した場所です (この素晴らしいチュートリアルに触発されたものです)。
の平方根を見つけるために、予測変数が真になる場所を初めてvaule検索しnumberます。(1..value)選択している予測子は ですnumber * number - value > 0.00001。
double square_root_of(double value)
{
assert(value >= 1);
double lo = 1.0;
double hi = value;
while( hi - lo > 0.00001)
{
double mid = lo + (hi - lo) / 2 ;
std::cout << lo << "," << hi << "," << mid << std::endl;
if( mid * mid - value > 0.00001) //this is the predictors we are using
{
hi = mid;
} else {
lo = mid;
}
}
return lo;
}
于 2009-10-26T07:43:25.387 に答える
3
二分探索を使う
public class FindSqrt {
public static void main(String[] strings) {
int num = 10000;
System.out.println(sqrt(num, 0, num));
}
private static int sqrt(int num, int min, int max) {
int middle = (min + max) / 2;
int x = middle * middle;
if (x == num) {
return middle;
} else if (x < num) {
return sqrt(num, middle, max);
} else {
return sqrt(num, min, middle);
}
}
}
于 2016-06-14T13:25:18.530 に答える
3
// Fastest way I found, an (extreme) C# unrolled version of:
// http://www.hackersdelight.org/hdcodetxt/isqrt.c.txt (isqrt4)
// It's quite a lot of code, basically a binary search (the "if" statements)
// followed by an unrolled loop (the labels).
// Most important: it's fast, twice as fast as "Math.Sqrt".
// On my pc: Math.Sqrt ~35 ns, sqrt <16 ns (mean <14 ns)
private static uint sqrt(uint x)
{
uint y, z;
if (x < 1u << 16)
{
if (x < 1u << 08)
{
if (x < 1u << 04) return x < 1u << 02 ? x + 3u >> 2 : x + 15u >> 3;
else
{
if (x < 1u << 06)
{ y = 1u << 03; x -= 1u << 04; if (x >= 5u << 02) { x -= 5u << 02; y |= 1u << 02; } goto L0; }
else
{ y = 1u << 05; x -= 1u << 06; if (x >= 5u << 04) { x -= 5u << 04; y |= 1u << 04; } goto L1; }
}
}
else // slower (on my pc): .... y = 3u << 04; } goto L1; }
{
if (x < 1u << 12)
{
if (x < 1u << 10)
{ y = 1u << 07; x -= 1u << 08; if (x >= 5u << 06) { x -= 5u << 06; y |= 1u << 06; } goto L2; }
else
{ y = 1u << 09; x -= 1u << 10; if (x >= 5u << 08) { x -= 5u << 08; y |= 1u << 08; } goto L3; }
}
else
{
if (x < 1u << 14)
{ y = 1u << 11; x -= 1u << 12; if (x >= 5u << 10) { x -= 5u << 10; y |= 1u << 10; } goto L4; }
else
{ y = 1u << 13; x -= 1u << 14; if (x >= 5u << 12) { x -= 5u << 12; y |= 1u << 12; } goto L5; }
}
}
}
else
{
if (x < 1u << 24)
{
if (x < 1u << 20)
{
if (x < 1u << 18)
{ y = 1u << 15; x -= 1u << 16; if (x >= 5u << 14) { x -= 5u << 14; y |= 1u << 14; } goto L6; }
else
{ y = 1u << 17; x -= 1u << 18; if (x >= 5u << 16) { x -= 5u << 16; y |= 1u << 16; } goto L7; }
}
else
{
if (x < 1u << 22)
{ y = 1u << 19; x -= 1u << 20; if (x >= 5u << 18) { x -= 5u << 18; y |= 1u << 18; } goto L8; }
else
{ y = 1u << 21; x -= 1u << 22; if (x >= 5u << 20) { x -= 5u << 20; y |= 1u << 20; } goto L9; }
}
}
else
{
if (x < 1u << 28)
{
if (x < 1u << 26)
{ y = 1u << 23; x -= 1u << 24; if (x >= 5u << 22) { x -= 5u << 22; y |= 1u << 22; } goto La; }
else
{ y = 1u << 25; x -= 1u << 26; if (x >= 5u << 24) { x -= 5u << 24; y |= 1u << 24; } goto Lb; }
}
else
{
if (x < 1u << 30)
{ y = 1u << 27; x -= 1u << 28; if (x >= 5u << 26) { x -= 5u << 26; y |= 1u << 26; } goto Lc; }
else
{ y = 1u << 29; x -= 1u << 30; if (x >= 5u << 28) { x -= 5u << 28; y |= 1u << 28; } }
}
}
}
z = y | 1u << 26; y /= 2; if (x >= z) { x -= z; y |= 1u << 26; }
Lc: z = y | 1u << 24; y /= 2; if (x >= z) { x -= z; y |= 1u << 24; }
Lb: z = y | 1u << 22; y /= 2; if (x >= z) { x -= z; y |= 1u << 22; }
La: z = y | 1u << 20; y /= 2; if (x >= z) { x -= z; y |= 1u << 20; }
L9: z = y | 1u << 18; y /= 2; if (x >= z) { x -= z; y |= 1u << 18; }
L8: z = y | 1u << 16; y /= 2; if (x >= z) { x -= z; y |= 1u << 16; }
L7: z = y | 1u << 14; y /= 2; if (x >= z) { x -= z; y |= 1u << 14; }
L6: z = y | 1u << 12; y /= 2; if (x >= z) { x -= z; y |= 1u << 12; }
L5: z = y | 1u << 10; y /= 2; if (x >= z) { x -= z; y |= 1u << 10; }
L4: z = y | 1u << 08; y /= 2; if (x >= z) { x -= z; y |= 1u << 08; }
L3: z = y | 1u << 06; y /= 2; if (x >= z) { x -= z; y |= 1u << 06; }
L2: z = y | 1u << 04; y /= 2; if (x >= z) { x -= z; y |= 1u << 04; }
L1: z = y | 1u << 02; y /= 2; if (x >= z) { x -= z; y |= 1u << 02; }
L0: return x > y ? y / 2 | 1u : y / 2;
}
于 2013-09-24T13:22:13.570 に答える
1
名前が示すように、その逆ですが、「十分に近い」が「十分に近い」場合もあります。とにかく興味深い読み物。
于 2009-11-01T21:26:19.567 に答える
1
一般に、整数 (たとえば 2 など) の平方根は概算しかできません (浮動小数点演算の問題ではなく、正確に計算できない無理数であるためです)。
もちろん、いくつかの近似は他の近似よりも優れています。もちろん、値 1.732 は 1.7 よりも 3 の平方根の近似値として優れているということです。
あなたが与えたリンクのコードで使用される方法は、最初の近似値を取得し、それを使用してより良い近似値を計算することによって機能します。
これはニュートン法と呼ばれ、十分な精度が得られるまで、新しい近似ごとに計算を繰り返すことができます。
実際、いつ繰り返しを停止するかを決定する方法が必要です。そうしないと、永久に実行されます。
通常、近似値の差が決定した値よりも小さい場合は停止します。
編集：すでに見つけた2つよりも簡単な実装はないと思います。
于 2009-10-26T06:47:34.767 に答える
0
2 の平方根を求めようとしていて、推定値が 1.5 であるとしましょう。a = 2、x = 1.5 とします。より良い見積もりを計算するために、a を x で割ります。これにより、新しい値 y = 1.333333 が得られます。ただし、これを次の見積もりとしてそのまま採用することはできません (なぜですか?)。以前の見積もりと平均する必要があります。したがって、次の推定値 xx は (x + y) / 2、つまり 1.416666 になります。
Double squareRoot(Double a, Double epsilon) {
Double x = 0d;
Double y = a;
Double xx = 0d;
// Make sure both x and y != 0.
while ((x != 0d || y != 0d) && y - x > epsilon) {
xx = (x + y) / 2;
if (xx * xx >= a) {
y = xx;
} else {
x = xx;
}
}
return xx;
}
イプシロンは、近似に必要な精度を決定します。関数は、abs(x*x - a) < epsilon を満たす最初の近似値 x を返す必要があります。ここで、abs(x) は x の絶対値です。
square_root(2, 1e-6)
Output: 1.4142141342163086
于 2015-04-10T00:24:02.560 に答える
0
二分探索を使用して浮動小数点平方根と任意精度を処理できる簡単なソリューション
ルビーでコーディング
include Math
def sqroot_precision num, precision
upper = num
lower = 0
middle = (upper + lower)/2.0
while true do
diff = middle**2 - num
return middle if diff.abs <= precision
if diff > 0
upper = middle
else diff < 0
lower = middle
end
middle = (upper + lower)/2.0
end
end
puts sqroot_precision 232.3, 0.0000000001
于 2014-03-27T06:42:52.507 に答える
0
すでにかなりの数の答えがありますが、ここに私のものがあります。これは最も単純なコードです（私にとって）。これがそのアルゴリズムです。
そしてpython 2.7でコード：
from __future__ import division
val = 81
x = 10
def sqr(data,x):
temp = x - ( (x**2 - data)/(2*x))
if temp == x:
print temp
return
else:
x = temp
return sqr(data,x)
#x =temp
#sqr(data,x)
sqr(val,x)
于 2016-08-11T15:34:17.967 に答える
-5
組み込み関数を使用して数値の平方根を計算するには
# include"iostream.h"
# include"conio.h"
# include"math.h"
void main()
{
clrscr();
float x;
cout<<"Enter the Number";
cin>>x;
float squreroot(float);
float z=squareroot(x);
cout<<z;
float squareroot(int x)
{
float s;
s = pow(x,.5)
return(s);
}
于 2013-10-25T03:51:03.103 に答える