编写自己的平方根函数
你如何编写自己的函数来find一个整数的最精确的平方根？
Googlesearch后，我发现这个 （从原始链接存档），但首先，我没有完全得到它，其次，这也是近似的。
假定平方根为最近的整数（实际根）或浮点数。
以下计算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给出的牛顿法的一个版本，“素数：计算的angular度”。 你应该使用这个版本的原因是，知道他们在做什么的人已经certificate它正好收敛到平方根的底部，而且很简单，所以发生执行错误的可能性很小。 它也很快（尽pipe可以构build一个更快的algorithm – 但是正确地做这件事情要复杂得多）。 对于非常小的N，正确执行的二进制search可以更快，但是您可以使用查找表。
为了舍入到最接近的整数，只需使用上面的algorithm计算t = floor（sqrt（4N））。 如果t的最低有效位被设置，则selectx =（t + 1）/ 2; 否则selectt / 2。 请注意，这是一个领带。 你也可以通过查看余数是否非零（即是否是t ^ 2 == 4N）来舍入（或舍入）。
请注意，您不需要使用浮点运算。 事实上，你不应该。 这个algorithm应该完全用整数来实现（特别是floor（）函数只是表示应该使用正整数除法）。
根据您的需要，可以使用简单的分治策略。 它不会像其他一些方法一样快速收敛，但是新手可能会更容易理解。 另外，由于它是O（log n）algorithm（每次迭代将search空间减半），对32位浮点数的最坏情况将是32次迭代。
假设你想要62.104的平方根。 你在0和中间select一个值，并将其平方。 如果广场高于你的数字，你需要集中在小于中点的数字。 如果太低，把精力集中在那些较高的。
用真正的math，你可以不断地将search空间分成两半（如果它没有一个有理的平方根）。 事实上，计算机最终会耗尽精度，你会有近似的结果。 下面的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
一个简单的（但不是很快）的方法来计算X的平方根：
squareroot(x) if x<0 then Error a = 1 b = x while (abs(ab)>ErrorMargin) a = (a+b)/2 b = x/a endwhile return a;
示例：squareroot（70000）
ab 1 70000 35001 2 17502 4 8753 8 4381 16 2199 32 1116 63 590 119 355 197 276 254 265 264
正如你所看到的，它为平方根定义了一个上限和一个下限，并缩小了边界，直到它的尺寸被接受为止。
有更有效的方法，但这个过程很容易理解。
只要注意设置Errormargin为1，如果使用整数，否则你有一个无限循环。
让我们指出一个非常有趣的方法来计算倒数平方根1 / sqrt（x），这是游戏devise界的一个传奇，因为它的思维速度很快。 或者等一下，阅读以下文章：
http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/
PS：我知道你只是想要平方根，但是地震的优雅胜过我所有的抵抗:)
顺便说一下，上面提到的文章也谈到了无聊的牛顿 – 拉夫逊逼近的地方。
当然这是近似的; 这就是浮点数的运算方式。
无论如何，标准的方法是用牛顿的方法 。 这和使用泰勒系列的方式大致相同，也就是立即想到的另一种方式。
在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
find一篇关于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; }
这是Facebook等人常见的面试问题。我不认为在面试中使用牛顿的方法是个好主意。 如果面试官在你不明白的时候问你牛顿方法的机制怎么办？
我提供了一个基于二进制search的Java解决scheme，我相信每个人都可以理解。
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; }
你可以在这里testing我的代码： leetcode：sqrt（x）
我想到的第一件事是：这是一个使用二进制search的好地方（受这个伟大教程的启发。）
为了find这个vaule平方根，我们首先search(1..value)中预测值为真的数字。 我们select的预测variables是number * number - value > 0.00001 。
double sqaure_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; }
这是一个使用三angular函数来获得平方根的方法。 这不是最快的algorithm，但它是精确的。 代码在javascript中：
var n = 5; //number to get the square root of var icr = ((n+1)/2); //intersecting circle radius var sqrt = Math.cos(Math.asin((icr-1)/icr))*icr; //square root of n alert(sqrt);
// 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; }
有一个algorithm，我在学校学习，你可以用来计算确切的平方根（或任意大的精度，如果根是一个无理数）。 这肯定比牛顿的algorithm慢，但确实如此。 假设你想计算531.3025的平方根
首先，你是从小数点开始把你的号码分成两组：
{5} {31}。{30} {25}
然后：
1）find第一组的最接近的平方根，小于或等于第一组的实际平方根：sqrt（{5}）> = 2.这个平方根是您最终答案的第一位。 让我们将已经find的最后一个平方根的数字表示为B.那么在B = 2的时刻。
2）接下来计算{5}和B ^ 2之间的差值：5 – 4 = 1。
3）对于所有后续的2位数字组，请执行以下操作：
将余数乘以100，然后将其添加到第二组：100 + 31 = 131。
findX – 根的下一个数字，例如131> =（（B * 20）+ X）* X。 X = 3. 43 * 3 = 129 <131.现在B = 23。另外，因为在小数点左边没有更多的2位数组，所以您已经find了最终根的所有整数数字。
4）对{30}和{25}重复相同的操作。 所以你有：
{30}：131-129 = 2.2 * 100 + 30 = 230> =（23 * 2 * 10 + X）* X→X = 0→B = 23.0
230×100 + 25 = 23025 23025> =（230×2×10 + X）X→X = 5→B = 23.05
最终结果= 23.05。
这个algorithm看起来很复杂，但是如果你在纸上使用你在学校学习过的“长整数”相同的符号，那么这个algorithm就简单多了，除了你不用做除法而是计算平方根。
使用二进制search
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); } } }
一般来说，整数的平方根（例如2） 只能近似（不是因为浮点运算的问题，而是因为它们是无法精确计算的无理数）。
当然，一些近似值比别人好。 当然，我的意思是，1.732的值比3的平方根更接近1.7
在这个链接的代码使用的方法，你通过第一个近似的工作，并使用它来计算一个更好的近似。
这就是所谓的牛顿法，你可以重新计算每一个新的近似值， 直到它对你来说足够准确。
事实上， 必须有一些方法来决定何时停止重复或永久运行。
通常情况下，如果近似值之间的差异小于您决定的值，您将停止。
编辑：我不认为可以有一个比你已经发现的两个更简单的实现。
反过来，正如名字所说，但有时“足够接近”是“足够接近”; 无论如何一个有趣的阅读。
Quake3的快速InvSqrt（）的起源
// A Java program to find floor(sqrt(x) public class Test { public static int floorSqrt(int x) { // Base Cases if (x == 0 || x == 1) return x; // Do Binary Search for floor(sqrt(x)) int start = 1, end = x, ans=0; while (start <= end) { int mid = (start + end) / 2; // If x is a perfect square if (mid*mid == x) return mid; // Since we need floor, we update answer when mid*mid is // smaller than x, and move closer to sqrt(x) if (mid*mid < x) { start = mid + 1; ans = mid; } else // If mid*mid is greater than x end = mid - 1; } return ans; } // Driver Method public static void main(String args[]) { int x = 11; System.out.println(floorSqrt(x)); } }
输出：3（地板）
Let 's' be the answer. We know that 0 <= s <= x. Consider any random number r. If r*r <= x, s >= r If r*r > x, s < r.
algorithm：
-
以'start'= 0开始，end ='x'，在'start'小于或等于'end'的情况下执行下面的操作。
-
a）将“mid”计算为（start + end）/ 2
-
b）比较mid * mid和x。
- c）如果x等于mid * mid，则返回mid。
- d）如果x更大，则在mid + 1和end之间进行二分search。 在这种情况下，我们也更新ans（注意我们需要floor）。
- e）如果x较小，则在开始和中间1之间进行二分search
上述解决scheme的时间复杂度为O（√n）。
一个简单的解决scheme，可以处理浮点平方根和任意精度使用二进制search
用ruby编码
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
假设我们正在试图find2的平方根，而估计值是1.5。 我们会说a = 2，x = 1.5。 为了计算一个更好的估计，我们将除以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; }
Epsilon确定近似值需要的准确度。 函数应返回满足abs（x * x – a）ε的第一个近似值x，其中abs（x）是x的绝对值。
square_root(2, 1e-6) Output: 1.4142141342163086
那么已经有相当多的答案，但是这里是我的这是最简单的一段代码（对我来说），这里是它的algorithm 。
和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)
用内置函数来计算一个数的平方根
# 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); }
