编写自己的平方根函数

Question

您如何编写自己的函数来查找整数的最精确平方根？

对其进行谷歌搜索之后，我发现了它（从其原始链接存档），但是首先，我没有完全了解它，其次，它也是近似的。

假设平方根是最接近的整数（实际根数）或浮点数。

Answer 1

以下计算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的“素数：一种计算视角”中给出的牛顿方法的一种形式。之所以要使用此版本，是因为知道他们在做什么的人都证明了它完全收敛于平方根的底面，而且它很简单，因此实现错误的可能性很小。它也很快（尽管可以构造甚至更快的算法，但是正确地执行则要复杂得多）。对于很小的N，正确实现的二进制搜索可能会更快，但是您也可以在其中使用查找表。要舍入到最接近的整数，只需使用上述算法计算t = floor（sqrt（4N））。如果设置了t的最低有效位，则选择x =（t + 1）/ 2; 否则选择t / 2。请注意，这四舍五入。您还可以通过查看余数是否为非零（即t ^ 2 == 4N）来舍入（或舍入为偶数）。请注意，您不需要使用浮点运算。实际上，您不应该这样。该算法应完全使用整数来实现（特别是floor（）函数仅指示应使用常规整数除法）。

Answer 2

根据您的需求，可以使用简单的分而治之策略。它的收敛速度不会像其他方法那样快，但是对于新手来说可能更容易理解。另外，由于它是O（log n）算法（每次迭代将搜索空间减半），所以32位浮点数的最坏情况是32次迭代。假设您想要62.104的平方根。您选择一个介于0和那个之间的值，并将其平方。如果平方比您的数字高，则需要专注于小于中点的数字。如果太低，则专注于较高的那些。使用真实的数学运算，您可以将搜索空间永远永远分成两部分（如果没有合理的平方根）。实际上，计算机最终将失去精度，您将获得近似值。以下C程序说明了这一点：#include <stdio.h>#include <stdlib.h>int main (int argc, char *argv[]) {&nbsp; &nbsp; float val, low, high, mid, oldmid, midsqr;&nbsp; &nbsp; int step = 0;&nbsp; &nbsp; // Get argument, force to non-negative.&nbsp; &nbsp; if (argc < 2) {&nbsp; &nbsp; &nbsp; &nbsp; printf ("Usage: sqrt <number>\n");&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; }&nbsp; &nbsp; val = fabs (atof (argv[1]));&nbsp; &nbsp; // Set initial bounds and print heading.&nbsp; &nbsp; low = 0;&nbsp; &nbsp; high = mid = val;&nbsp; &nbsp; oldmid = -1;&nbsp; &nbsp; printf ("%4s&nbsp; %10s&nbsp; %10s&nbsp; %10s&nbsp; %10s&nbsp; %10s&nbsp; &nbsp; %s\n",&nbsp; &nbsp; &nbsp; &nbsp; "Step", "Number", "Low", "High", "Mid", "Square", "Result");&nbsp; &nbsp; // Keep going until accurate enough.&nbsp; &nbsp; while (fabs(oldmid - mid) >= 0.00001) {&nbsp; &nbsp; &nbsp; &nbsp; oldmid = mid;&nbsp; &nbsp; &nbsp; &nbsp; // Get midpoint and see if we need lower or higher.&nbsp; &nbsp; &nbsp; &nbsp; mid = (high + low) / 2;&nbsp; &nbsp; &nbsp; &nbsp; midsqr = mid * mid;&nbsp; &nbsp; &nbsp; &nbsp; printf ("%4d&nbsp; %10.4f&nbsp; %10.4f&nbsp; %10.4f&nbsp; %10.4f&nbsp; %10.4f&nbsp; ",&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++step, val, low, high, mid, midsqr);&nbsp; &nbsp; &nbsp; &nbsp; if (mid * mid > val) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; high = mid;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printf ("- too high\n");&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; low = mid;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printf ("- too low\n");&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // Desired accuracy reached, print it.&nbsp; &nbsp; printf ("sqrt(%.4f) = %.4f\n", val, mid);&nbsp; &nbsp; return 0;}这是几次运行，因此希望您能了解其工作原理。对于77：pax> sqrt 77Step&nbsp; &nbsp; &nbsp; Number&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Low&nbsp; &nbsp; &nbsp; &nbsp; High&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Mid&nbsp; &nbsp; &nbsp; Square&nbsp; &nbsp; Result&nbsp; &nbsp;1&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp;38.5000&nbsp; &nbsp;1482.2500&nbsp; - too high&nbsp; &nbsp;2&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;38.5000&nbsp; &nbsp; &nbsp;19.2500&nbsp; &nbsp; 370.5625&nbsp; - too high&nbsp; &nbsp;3&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;19.2500&nbsp; &nbsp; &nbsp; 9.6250&nbsp; &nbsp; &nbsp;92.6406&nbsp; - too high&nbsp; &nbsp;4&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp; 9.6250&nbsp; &nbsp; &nbsp; 4.8125&nbsp; &nbsp; &nbsp;23.1602&nbsp; - too low&nbsp; &nbsp;5&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 4.8125&nbsp; &nbsp; &nbsp; 9.6250&nbsp; &nbsp; &nbsp; 7.2188&nbsp; &nbsp; &nbsp;52.1104&nbsp; - too low&nbsp; &nbsp;6&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 7.2188&nbsp; &nbsp; &nbsp; 9.6250&nbsp; &nbsp; &nbsp; 8.4219&nbsp; &nbsp; &nbsp;70.9280&nbsp; - too low&nbsp; &nbsp;7&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.4219&nbsp; &nbsp; &nbsp; 9.6250&nbsp; &nbsp; &nbsp; 9.0234&nbsp; &nbsp; &nbsp;81.4224&nbsp; - too high&nbsp; &nbsp;8&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.4219&nbsp; &nbsp; &nbsp; 9.0234&nbsp; &nbsp; &nbsp; 8.7227&nbsp; &nbsp; &nbsp;76.0847&nbsp; - too low&nbsp; &nbsp;9&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7227&nbsp; &nbsp; &nbsp; 9.0234&nbsp; &nbsp; &nbsp; 8.8730&nbsp; &nbsp; &nbsp;78.7310&nbsp; - too high&nbsp; 10&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7227&nbsp; &nbsp; &nbsp; 8.8730&nbsp; &nbsp; &nbsp; 8.7979&nbsp; &nbsp; &nbsp;77.4022&nbsp; - too high&nbsp; 11&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7227&nbsp; &nbsp; &nbsp; 8.7979&nbsp; &nbsp; &nbsp; 8.7603&nbsp; &nbsp; &nbsp;76.7421&nbsp; - too low&nbsp; 12&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7603&nbsp; &nbsp; &nbsp; 8.7979&nbsp; &nbsp; &nbsp; 8.7791&nbsp; &nbsp; &nbsp;77.0718&nbsp; - too high&nbsp; 13&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7603&nbsp; &nbsp; &nbsp; 8.7791&nbsp; &nbsp; &nbsp; 8.7697&nbsp; &nbsp; &nbsp;76.9068&nbsp; - too low&nbsp; 14&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7697&nbsp; &nbsp; &nbsp; 8.7791&nbsp; &nbsp; &nbsp; 8.7744&nbsp; &nbsp; &nbsp;76.9893&nbsp; - too low&nbsp; 15&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7744&nbsp; &nbsp; &nbsp; 8.7791&nbsp; &nbsp; &nbsp; 8.7767&nbsp; &nbsp; &nbsp;77.0305&nbsp; - too high&nbsp; 16&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7744&nbsp; &nbsp; &nbsp; 8.7767&nbsp; &nbsp; &nbsp; 8.7755&nbsp; &nbsp; &nbsp;77.0099&nbsp; - too high&nbsp; 17&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7744&nbsp; &nbsp; &nbsp; 8.7755&nbsp; &nbsp; &nbsp; 8.7749&nbsp; &nbsp; &nbsp;76.9996&nbsp; - too low&nbsp; 18&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7749&nbsp; &nbsp; &nbsp; 8.7755&nbsp; &nbsp; &nbsp; 8.7752&nbsp; &nbsp; &nbsp;77.0047&nbsp; - too high&nbsp; 19&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7749&nbsp; &nbsp; &nbsp; 8.7752&nbsp; &nbsp; &nbsp; 8.7751&nbsp; &nbsp; &nbsp;77.0022&nbsp; - too high&nbsp; 20&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7749&nbsp; &nbsp; &nbsp; 8.7751&nbsp; &nbsp; &nbsp; 8.7750&nbsp; &nbsp; &nbsp;77.0009&nbsp; - too high&nbsp; 21&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7749&nbsp; &nbsp; &nbsp; 8.7750&nbsp; &nbsp; &nbsp; 8.7750&nbsp; &nbsp; &nbsp;77.0002&nbsp; - too high&nbsp; 22&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7749&nbsp; &nbsp; &nbsp; 8.7750&nbsp; &nbsp; &nbsp; 8.7750&nbsp; &nbsp; &nbsp;76.9999&nbsp; - too low&nbsp; 23&nbsp; &nbsp; &nbsp;77.0000&nbsp; &nbsp; &nbsp; 8.7750&nbsp; &nbsp; &nbsp; 8.7750&nbsp; &nbsp; &nbsp; 8.7750&nbsp; &nbsp; &nbsp;77.0000&nbsp; - too lowsqrt(77.0000) = 8.7750对于62.104：pax> sqrt 62.104Step&nbsp; &nbsp; &nbsp; Number&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Low&nbsp; &nbsp; &nbsp; &nbsp; High&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Mid&nbsp; &nbsp; &nbsp; Square&nbsp; &nbsp; Result&nbsp; &nbsp;1&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp;31.0520&nbsp; &nbsp; 964.2267&nbsp; - too high&nbsp; &nbsp;2&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;31.0520&nbsp; &nbsp; &nbsp;15.5260&nbsp; &nbsp; 241.0567&nbsp; - too high&nbsp; &nbsp;3&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;15.5260&nbsp; &nbsp; &nbsp; 7.7630&nbsp; &nbsp; &nbsp;60.2642&nbsp; - too low&nbsp; &nbsp;4&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.7630&nbsp; &nbsp; &nbsp;15.5260&nbsp; &nbsp; &nbsp;11.6445&nbsp; &nbsp; 135.5944&nbsp; - too high&nbsp; &nbsp;5&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.7630&nbsp; &nbsp; &nbsp;11.6445&nbsp; &nbsp; &nbsp; 9.7037&nbsp; &nbsp; &nbsp;94.1628&nbsp; - too high&nbsp; &nbsp;6&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.7630&nbsp; &nbsp; &nbsp; 9.7037&nbsp; &nbsp; &nbsp; 8.7334&nbsp; &nbsp; &nbsp;76.2718&nbsp; - too high&nbsp; &nbsp;7&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.7630&nbsp; &nbsp; &nbsp; 8.7334&nbsp; &nbsp; &nbsp; 8.2482&nbsp; &nbsp; &nbsp;68.0326&nbsp; - too high&nbsp; &nbsp;8&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.7630&nbsp; &nbsp; &nbsp; 8.2482&nbsp; &nbsp; &nbsp; 8.0056&nbsp; &nbsp; &nbsp;64.0895&nbsp; - too high&nbsp; &nbsp;9&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.7630&nbsp; &nbsp; &nbsp; 8.0056&nbsp; &nbsp; &nbsp; 7.8843&nbsp; &nbsp; &nbsp;62.1621&nbsp; - too high&nbsp; 10&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.7630&nbsp; &nbsp; &nbsp; 7.8843&nbsp; &nbsp; &nbsp; 7.8236&nbsp; &nbsp; &nbsp;61.2095&nbsp; - too low&nbsp; 11&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8236&nbsp; &nbsp; &nbsp; 7.8843&nbsp; &nbsp; &nbsp; 7.8540&nbsp; &nbsp; &nbsp;61.6849&nbsp; - too low&nbsp; 12&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8540&nbsp; &nbsp; &nbsp; 7.8843&nbsp; &nbsp; &nbsp; 7.8691&nbsp; &nbsp; &nbsp;61.9233&nbsp; - too low&nbsp; 13&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8691&nbsp; &nbsp; &nbsp; 7.8843&nbsp; &nbsp; &nbsp; 7.8767&nbsp; &nbsp; &nbsp;62.0426&nbsp; - too low&nbsp; 14&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8767&nbsp; &nbsp; &nbsp; 7.8843&nbsp; &nbsp; &nbsp; 7.8805&nbsp; &nbsp; &nbsp;62.1024&nbsp; - too low&nbsp; 15&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8805&nbsp; &nbsp; &nbsp; 7.8843&nbsp; &nbsp; &nbsp; 7.8824&nbsp; &nbsp; &nbsp;62.1323&nbsp; - too high&nbsp; 16&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8805&nbsp; &nbsp; &nbsp; 7.8824&nbsp; &nbsp; &nbsp; 7.8815&nbsp; &nbsp; &nbsp;62.1173&nbsp; - too high&nbsp; 17&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8805&nbsp; &nbsp; &nbsp; 7.8815&nbsp; &nbsp; &nbsp; 7.8810&nbsp; &nbsp; &nbsp;62.1098&nbsp; - too high&nbsp; 18&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8805&nbsp; &nbsp; &nbsp; 7.8810&nbsp; &nbsp; &nbsp; 7.8807&nbsp; &nbsp; &nbsp;62.1061&nbsp; - too high&nbsp; 19&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8805&nbsp; &nbsp; &nbsp; 7.8807&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp;62.1042&nbsp; - too high&nbsp; 20&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8805&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp;62.1033&nbsp; - too low&nbsp; 21&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp;62.1038&nbsp; - too low&nbsp; 22&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp;62.1040&nbsp; - too high&nbsp; 23&nbsp; &nbsp; &nbsp;62.1040&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp; 7.8806&nbsp; &nbsp; &nbsp;62.1039&nbsp; - too highsqrt(62.1040) = 7.8806对于49：pax> sqrt 49Step&nbsp; &nbsp; &nbsp; Number&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Low&nbsp; &nbsp; &nbsp; &nbsp; High&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Mid&nbsp; &nbsp; &nbsp; Square&nbsp; &nbsp; Result&nbsp; &nbsp;1&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp;24.5000&nbsp; &nbsp; 600.2500&nbsp; - too high&nbsp; &nbsp;2&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;24.5000&nbsp; &nbsp; &nbsp;12.2500&nbsp; &nbsp; 150.0625&nbsp; - too high&nbsp; &nbsp;3&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 0.0000&nbsp; &nbsp; &nbsp;12.2500&nbsp; &nbsp; &nbsp; 6.1250&nbsp; &nbsp; &nbsp;37.5156&nbsp; - too low&nbsp; &nbsp;4&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.1250&nbsp; &nbsp; &nbsp;12.2500&nbsp; &nbsp; &nbsp; 9.1875&nbsp; &nbsp; &nbsp;84.4102&nbsp; - too high&nbsp; &nbsp;5&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.1250&nbsp; &nbsp; &nbsp; 9.1875&nbsp; &nbsp; &nbsp; 7.6562&nbsp; &nbsp; &nbsp;58.6182&nbsp; - too high&nbsp; &nbsp;6&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.1250&nbsp; &nbsp; &nbsp; 7.6562&nbsp; &nbsp; &nbsp; 6.8906&nbsp; &nbsp; &nbsp;47.4807&nbsp; - too low&nbsp; &nbsp;7&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.8906&nbsp; &nbsp; &nbsp; 7.6562&nbsp; &nbsp; &nbsp; 7.2734&nbsp; &nbsp; &nbsp;52.9029&nbsp; - too high&nbsp; &nbsp;8&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.8906&nbsp; &nbsp; &nbsp; 7.2734&nbsp; &nbsp; &nbsp; 7.0820&nbsp; &nbsp; &nbsp;50.1552&nbsp; - too high&nbsp; &nbsp;9&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.8906&nbsp; &nbsp; &nbsp; 7.0820&nbsp; &nbsp; &nbsp; 6.9863&nbsp; &nbsp; &nbsp;48.8088&nbsp; - too low&nbsp; 10&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9863&nbsp; &nbsp; &nbsp; 7.0820&nbsp; &nbsp; &nbsp; 7.0342&nbsp; &nbsp; &nbsp;49.4797&nbsp; - too high&nbsp; 11&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9863&nbsp; &nbsp; &nbsp; 7.0342&nbsp; &nbsp; &nbsp; 7.0103&nbsp; &nbsp; &nbsp;49.1437&nbsp; - too high&nbsp; 12&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9863&nbsp; &nbsp; &nbsp; 7.0103&nbsp; &nbsp; &nbsp; 6.9983&nbsp; &nbsp; &nbsp;48.9761&nbsp; - too low&nbsp; 13&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9983&nbsp; &nbsp; &nbsp; 7.0103&nbsp; &nbsp; &nbsp; 7.0043&nbsp; &nbsp; &nbsp;49.0598&nbsp; - too high&nbsp; 14&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9983&nbsp; &nbsp; &nbsp; 7.0043&nbsp; &nbsp; &nbsp; 7.0013&nbsp; &nbsp; &nbsp;49.0179&nbsp; - too high&nbsp; 15&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9983&nbsp; &nbsp; &nbsp; 7.0013&nbsp; &nbsp; &nbsp; 6.9998&nbsp; &nbsp; &nbsp;48.9970&nbsp; - too low&nbsp; 16&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9998&nbsp; &nbsp; &nbsp; 7.0013&nbsp; &nbsp; &nbsp; 7.0005&nbsp; &nbsp; &nbsp;49.0075&nbsp; - too high&nbsp; 17&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9998&nbsp; &nbsp; &nbsp; 7.0005&nbsp; &nbsp; &nbsp; 7.0002&nbsp; &nbsp; &nbsp;49.0022&nbsp; - too high&nbsp; 18&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 6.9998&nbsp; &nbsp; &nbsp; 7.0002&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp;48.9996&nbsp; - too low&nbsp; 19&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp; 7.0002&nbsp; &nbsp; &nbsp; 7.0001&nbsp; &nbsp; &nbsp;49.0009&nbsp; - too high&nbsp; 20&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp; 7.0001&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp;49.0003&nbsp; - too high&nbsp; 21&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp;49.0000&nbsp; - too low&nbsp; 22&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp;49.0001&nbsp; - too high&nbsp; 23&nbsp; &nbsp; &nbsp;49.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp; 7.0000&nbsp; &nbsp; &nbsp;49.0000&nbsp; - too highsqrt(49.0000) = 7.0000

Answer 3

一种简单（但不是很快）的方法来计算X的平方根：squareroot(x)&nbsp; &nbsp; if x<0 then Error&nbsp; &nbsp; a = 1&nbsp; &nbsp; b = x&nbsp; &nbsp; while (abs(a-b)>ErrorMargin)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; a = (a+b)/2&nbsp; &nbsp; &nbsp; &nbsp; b = x/a&nbsp; &nbsp; endwhile&nbsp; &nbsp; return a;示例：squareroot（70000）&nbsp; &nbsp; a&nbsp; &nbsp; &nbsp; &nbsp;b&nbsp; &nbsp; 1&nbsp; &nbsp;7000035001&nbsp; &nbsp; &nbsp; &nbsp;217502&nbsp; &nbsp; &nbsp; &nbsp;4&nbsp;8753&nbsp; &nbsp; &nbsp; &nbsp;8&nbsp;4381&nbsp; &nbsp; &nbsp; 16&nbsp;2199&nbsp; &nbsp; &nbsp; 32&nbsp;1116&nbsp; &nbsp; &nbsp; 63&nbsp; 590&nbsp; &nbsp; &nbsp;119&nbsp; 355&nbsp; &nbsp; &nbsp;197&nbsp; 276&nbsp; &nbsp; &nbsp;254&nbsp; 265&nbsp; &nbsp; &nbsp;264如您所见，它定义了平方根的上下边界，并缩小了边界直到其大小可以接受为止。有许多更有效的方法，但是这一方法说明了该过程并且易于理解。请注意，如果使用整数，则将Errormargin设置为1，否则会出现无限循环。