C++ 不使用 sqrt 函数求平方根？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19611198/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding square root without using sqrt function?
提问by Arun Pandey
I was finding out the algorithm for finding out the square root without using sqrt function and then tried to put into programming. I end up with this working code in C++
我在不使用 sqrt 函数的情况下找出求平方根的算法，然后尝试进行编程。我最终在 C++ 中得到了这个工作代码
#include <iostream>
using namespace std;
double SqrtNumber(double num)
{
double lower_bound=0;
double upper_bound=num;
double temp=0; /* ek edited this line */
int nCount = 50;
while(nCount != 0)
{
temp=(lower_bound+upper_bound)/2;
if(temp*temp==num)
{
return temp;
}
else if(temp*temp > num)
{
upper_bound = temp;
}
else
{
lower_bound = temp;
}
nCount--;
}
return temp;
}
int main()
{
double num;
cout<<"Enter the number\n";
cin>>num;
if(num < 0)
{
cout<<"Error: Negative number!";
return 0;
}
cout<<"Square roots are: +"<<sqrtnum(num) and <<" and -"<<sqrtnum(num);
return 0;
}
Now the problem is initializing the number of iterations nCount in the declaratione ( here it is 50). For example to find out square root of 36 it takes 22 iterations, so no problem whereas finding the square root of 15625 takes more than 50 iterations, So it would return the value of temp after 50 iterations. Please give a solution for this.
现在的问题是初始化声明中的迭代次数 nCount（这里是 50）。例如，找出 36 的平方根需要 22 次迭代，所以没问题，而找到 15625 的平方根需要 50 多次迭代，所以它会在 50 次迭代后返回 temp 的值。请给出一个解决方案。
回答by mvp
There is a better algorithm, which needs at most 6 iterations to converge to maximum precision for double numbers:
有一个更好的算法，它最多需要 6 次迭代才能收敛到双数的最大精度：
#include <math.h>
double sqrt(double x) {
if (x <= 0)
return 0; // if negative number throw an exception?
int exp = 0;
x = frexp(x, &exp); // extract binary exponent from x
if (exp & 1) { // we want exponent to be even
exp--;
x *= 2;
}
double y = (1+x)/2; // first approximation
double z = 0;
while (y != z) { // yes, we CAN compare doubles here!
z = y;
y = (y + x/y) / 2;
}
return ldexp(y, exp/2); // multiply answer by 2^(exp/2)
}
Algorithm starts with 1 as first approximation for square root value.
Then, on each step, it improves next approximation by taking average between current value yand x/y. If y= sqrt(x), it will be the same. If y> sqrt(x), then x/y< sqrt(x)by about the same amount. In other words, it will converge very fast.
算法从 1 开始，作为平方根值的第一个近似值。然后，在每一步，它通过取当前值y和之间的平均值来改进下一个近似值x/y。如果y= sqrt(x)，它将是相同的。如果y> sqrt(x)，则x/y<sqrt(x)大致相同。换句话说，它会很快收敛。
UPDATE: To speed up convergence on very large or very small numbers, changed sqrt()function to extract binary exponent and compute square root from number in [1, 4)range. It now needs frexp()from <math.h>to get binary exponent, but it is possible to get this exponent by extracting bits from IEEE-754 number format without using frexp().
更新：为了加速非常大或非常小的数字的收敛，更改了sqrt()函数以提取二进制指数并从[1, 4)范围内的数字计算平方根。现在需要frexp()from<math.h>来获取二进制指数，但可以通过从 IEEE-754 数字格式中提取位而不使用frexp().
回答by Newskooler
Why not try to use the Babylonian methodfor finding a square root.
为什么不尝试使用巴比伦方法来求平方根。
Here is my code for it:
这是我的代码：
double sqrt(double number)
{
double error = 0.00001; //define the precision of your result
double s = number;
while ((s - number / s) > error) //loop until precision satisfied
{
s = (s + number / s) / 2;
}
return s;
}
Good luck!
祝你好运！
回答by Zac Howland
Remove your nCountaltogether (as there are some roots that this algorithm will take many iterations for).
nCount完全删除你的（因为有一些根，这个算法需要多次迭代）。
double SqrtNumber(double num)
{
double lower_bound=0;
double upper_bound=num;
double temp=0;
while(fabs(num - (temp * temp)) > SOME_SMALL_VALUE)
{
temp = (lower_bound+upper_bound)/2;
if (temp*temp >= num)
{
upper_bound = temp;
}
else
{
lower_bound = temp;
}
}
return temp;
}
回答by Mani Kant
if you need to find square root without using sqrt(),use root=pow(x,0.5).
如果您需要在不使用的情况下找到平方根sqrt()，请使用root=pow(x,0.5).
Where x is value whose square root you need to find.
其中 x 是您需要找到其平方根的值。
回答by Himanshu
As I found this question is old and have many answers but I have an answer which is simple and working great..
因为我发现这个问题很旧并且有很多答案，但我有一个简单且有效的答案..
#define EPSILON 0.0000001 // least minimum value for comparison
double SquareRoot(double _val) {
double low = 0;
double high = _val;
double mid = 0;
while (high - low > EPSILON) {
mid = low + (high - low) / 2; // finding mid value
if (mid*mid > _val) {
high = mid;
} else {
low = mid;
}
}
return mid;
}
I hope it will be helpful for future users.
我希望它对未来的用户有所帮助。
回答by PatrickSteiner
Here is a very simple but unsafeapproach to find the square-root of a number. Unsafe because it only works by natural numbers, where you know that the base respectively the exponent are natural numbers. I had to use it for a task where i was neither allowed to use the #include<cmath>-library, nor i was allowed to use pointers.
这是一个非常简单但不安全的方法来找到一个数字的平方根。不安全，因为它仅适用于自然数，您知道底数和指数是自然数。我不得不将它用于一项既不允许我使用#include<cmath>-library 也不允许我使用指针的任务。
potency = base ^ exponent
效力 = 基数 ^ 指数
// FUNCTION: square-root
int sqrt(int x)
{
int quotient = 0;
int i = 0;
bool resultfound = false;
while (resultfound == false) {
if (i*i == x) {
quotient = i;
resultfound = true;
}
i++;
}
return quotient;
}
回答by Cameron Monks
This a very simple recursive approach.
这是一个非常简单的递归方法。
double mySqrt(double v, double test) {
if (abs(test * test - v) < 0.0001) {
return test;
}
double highOrLow = v / test;
return mySqrt(v, (test + highOrLow) / 2.0);
}
double mySqrt(double v) {
return mySqrt(v, v/2.0);
}
回答by Kartik
//long division method.
#include<iostream>
using namespace std;
int main() {
int n, i = 1, divisor, dividend, j = 1, digit;
cin >> n;
while (i * i < n) {
i = i + 1;
}
i = i - 1;
cout << i << '.';
divisor = 2 * i;
dividend = n - (i * i );
while( j <= 5) {
dividend = dividend * 100;
digit = 0;
while ((divisor * 10 + digit) * digit < dividend) {
digit = digit + 1;
}
digit = digit - 1;
cout << digit;
dividend = dividend - ((divisor * 10 + digit) * digit);
divisor = divisor * 10 + 2*digit;
j = j + 1;
}
cout << endl;
return 0;
}
回答by JReyn
After looking at the previous responses, I hope this will help resolve any ambiguities. In case the similarities in the previous solutions and my solution are illusive, or this method of solving for roots is unclear, I've also made a graph which can be found here.
看了之前的回复，我希望这将有助于解决任何歧义。如果前面的解决方案和我的解决方案的相似之处是虚幻的，或者这种求解根的方法不清楚，我还制作了一个图表，可以在这里找到。
This is a working root function capable of solving for any nth-root
这是一个工作根函数，能够解决任何第 n 个根
(default is square root for the sake of this question)
（为了这个问题，默认是平方根）
#include <cmath>
// for "pow" function
double sqrt(double A, double root = 2) {
const double e = 2.71828182846;
return pow(e,(pow(10.0,9.0)/root)*(1.0-(pow(A,-pow(10.0,-9.0)))));
}
Explanation:
说明：
This works via Taylor series, logarithmic properties, and a bit of algebra.
这通过泰勒级数、对数属性和一些代数起作用。
Take, for example:
举个例子：
log A = N
x
*Note: for square-root, N = 2; for any other root you only need to change the one variable, N.
*注：对于平方根，N = 2；对于任何其他根，您只需要更改一个变量 N。
1) Change the base, convert the base 'x' log function to natural log,
1）改变基数，将基数'x'对数函数转换为自然对数，
log A => ln(A)/ln(x) = N
x
2) Rearrange to isolate ln(x), and eventually just 'x',
2）重新排列以隔离ln（x），最终只是'x'，
ln(A)/N = ln(x)
3) Set both sides as exponents of 'e',
3) 将两边设置为 'e' 的指数，
e^(ln(A)/N) = e^(ln(x)) >~{ e^ln(x) == x }~> e^(ln(A)/N) = x
4) Taylor series represents "ln" as an infinite series,
4）泰勒级数将“ln”表示为无穷级数，
ln(x) = (k=1)Sigma: (1/k)(-1^(k+1))(k-1)^n
<~~~ expanded ~~~>
[(x-1)] - [(1/2)(x-1)^2] + [(1/3)(x-1)^3] - [(1/4)(x-1)^4] + . . .
*Note: Continue the series for increased accuracy. For brevity, 10^9 is used in my function which expresses the series convergence for the natural log with about 7 digits, or the 10-millionths place, for precision,
*注意：继续该系列以提高准确性。为简洁起见，我的函数中使用了 10^9，它表示自然对数的级数收敛，大约有 7 位数字，或百万分之一的位置，为了精确，
ln(x) = 10^9(1-x^(-10^(-9)))
5) Now, just plug in this equation for natural log into the simplified equation obtained in step 3.
5) 现在，只需将这个自然对数方程代入步骤 3 中得到的简化方程。
e^[((10^9)/N)(1-A^(-10^-9)] = nth-root of (A)
6) This implementation might seem like overkill; however, its purpose is to demonstrate how you can solve for roots without having to guess and check. Also, it would enable you to replace the pow function from the cmath library with your own pow function:
6）这个实现可能看起来有点矫枉过正；但是，它的目的是演示如何无需猜测和检查即可求解根。此外，它还可以让您用自己的 pow 函数替换 cmath 库中的 pow 函数：
double power(double base, double exponent) {
if (exponent == 0) return 1;
int wholeInt = (int)exponent;
double decimal = exponent - (double)wholeInt;
if (decimal) {
int powerInv = 1/decimal;
if (!wholeInt) return root(base,powerInv);
else return power(root(base,powerInv),wholeInt,true);
}
return power(base, exponent, true);
}
double power(double base, int exponent, bool flag) {
if (exponent < 0) return 1/power(base,-exponent,true);
if (exponent > 0) return base * power(base,exponent-1,true);
else return 1;
}
int root(int A, int root) {
return power(E,(1000000000000/root)*(1-(power(A,-0.000000000001))));
}
回答by galaxyan
Here is a very awesome code to find sqrt and even faster than original sqrt function.
这是一个非常棒的代码，用于查找 sqrt 甚至比原始 sqrt 函数更快。
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f375a86 - (i>>1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
x = x*(1.5f - xhalf*x*x);
x = x*(1.5f - xhalf*x*x);
x=1/x;
return x;
}
