TA貢獻(xiàn)1880條經(jīng)驗(yàn) 獲得超4個(gè)贊
以下計(jì)算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的“素?cái)?shù)：一種計(jì)算視角”中給出的牛頓方法的一種形式。之所以要使用此版本，是因?yàn)橹浪麄冊(cè)谧鍪裁吹娜硕甲C明了它完全收斂于平方根的底面，而且它很簡單，因此實(shí)現(xiàn)錯(cuò)誤的可能性很小。它也很快（盡管可以構(gòu)造甚至更快的算法，但是正確地執(zhí)行則要復(fù)雜得多）。對(duì)于很小的N，正確實(shí)現(xiàn)的二進(jìn)制搜索可能會(huì)更快，但是您也可以在其中使用查找表。
要舍入到最接近的整數(shù)，只需使用上述算法計(jì)算t = floor（sqrt（4N））。如果設(shè)置了t的最低有效位，則選擇x =（t + 1）/ 2; 否則選擇t / 2。請(qǐng)注意，這四舍五入。您還可以通過查看余數(shù)是否為非零（即t ^ 2 == 4N）來舍入（或舍入為偶數(shù)）。
請(qǐng)注意，您不需要使用浮點(diǎn)運(yùn)算。實(shí)際上，您不應(yīng)該這樣。該算法應(yīng)完全使用整數(shù)來實(shí)現(xiàn)（特別是floor（）函數(shù)僅指示應(yīng)使用常規(guī)整數(shù)除法）。
TA貢獻(xiàn)1817條經(jīng)驗(yàn) 獲得超14個(gè)贊
根據(jù)您的需求，可以使用簡單的分而治之策略。它的收斂速度不會(huì)像其他方法那樣快，但是對(duì)于新手來說可能更容易理解。另外，由于它是O（log n）算法（每次迭代將搜索空間減半），所以32位浮點(diǎn)數(shù)的最壞情況是32次迭代。
假設(shè)您想要62.104的平方根。您選擇一個(gè)介于0和那個(gè)之間的值，并將其平方。如果平方比您的數(shù)字高，則需要專注于小于中點(diǎn)的數(shù)字。如果太低，則專注于較高的那些。
使用真實(shí)的數(shù)學(xué)運(yùn)算，您可以將搜索空間永遠(yuǎn)永遠(yuǎn)分成兩部分（如果沒有合理的平方根）。實(shí)際上，計(jì)算機(jī)最終將失去精度，您將獲得近似值。以下C程序說明了這一點(diǎn)：
#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;
}
這是幾次運(yùn)行，因此希望您能了解其工作原理。對(duì)于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
對(duì)于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
對(duì)于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
TA貢獻(xiàn)1982條經(jīng)驗(yàn) 獲得超2個(gè)贊
一種簡單（但不是很快）的方法來計(jì)算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;
示例：squareroot（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
如您所見，它定義了平方根的上下邊界，并縮小了邊界直到其大小可以接受為止。
有許多更有效的方法，但是這一方法說明了該過程并且易于理解。
請(qǐng)注意，如果使用整數(shù)，則將Errormargin設(shè)置為1，否則會(huì)出現(xiàn)無限循環(huán)。
舉報(bào)