Welcome~~~


Another blog:
http://fun-st.blogspot.com/

It is easier to write an incorrect program than understand a correct one.

Wednesday, February 9, 2011

# Compute square roots

Rough estimation

Many of the methods for calculating square roots of a positive real number S require an initial seed value. If the initial value is too far from the actual square root, the calculation will be slowed down. It is therefore useful to have a rough estimate, which may be very inaccurate but easy to calculate. If S ≥ 1, let D be the number of digits to the left of the decimal point. If S < 1, let D be the negative of the number of zeros to the immediate right of the decimal point. Then the rough estimation is this:

If D is odd, D = 2n + 1, then use  \sqrt{S} \approx 2 \cdot 10^n.
If D is even, D = 2n + 2, then use  \sqrt{S} \approx 6 \cdot 10^n.

Two and six are used because they approximate the geometric means of the lowest and highest possible values with the given number of digits: \sqrt{\sqrt{1 \cdot  10}} = \sqrt[4]{10} \approx 2 \, and \sqrt{\sqrt{10 \cdot 100}} = \sqrt[4]{1000}  \approx 6 \,.

When working in the binary numeral system (as computers do internally), an alternative method is to use 2^{\left\lfloor  D/2\right\rfloor} (here D is the number of binary digits).

Babylonian method

Graph charting the use of the Babylonian method for approximating the square root of 100 (10) using starting values x0 = 50, x0 = 1, and x0 = −5. Note that using a negative starting value yields the negative root.

Perhaps the first algorithm used for approximating \sqrt S is known as the "Babylonian method", named after the Babylonians,[1] or "Heron's method", named after the first-century Greek mathematician Hero of Alexandria who gave the first explicit description of the method.[2] It can be derived from (but predates) Newton's method. This is a quadratically convergent algorithm, which means that the number of correct digits of the approximation roughly doubles with each iteration. It proceeds as follows:

  1. Begin with an arbitrary positive starting value x0 (the closer to the root, the better).
  2. Let xn+1 be the average of xn and S / xn (using the arithmetic mean to approximate the geometric mean).
  3. Repeat step 2 until the desired accuracy is achieved.

Take the number you want to know the square root of. Call this number x.
Guess a number that is smaller than x. Call your guess G.
Now square G, to find "G squared".
If "G squared" is equal to x, G is the square root of x. Stop.
If "G squared" is not equal to x, get a "new G" like so: New guess = (G + x/G) / 2
Take your new guess, go back three steps, carry on from there.



#include <iostream>
#include <cmath>
using namespace std;

int main()
{
cout << "Please enter a number: ";
double a;
cin >> a;
const double EPSILON = 1E-14;
double xnew = a/2;
double xold;
do
{
xold = xnew;
xnew = (xold + a / xold) / 2;
}
while (fabs(xnew - xold) > EPSILON);

cout << "The square root is " << xnew << "\n";
system("pause");
return 0;
}

and another one


#include <iostream>
#include <cmath>
using namespace std;

int main()
{
cout << "Please enter a number: ";
double a;
cin >> a;
double answer = sqrt(a);
cout << answer << "\n";
system ("pause");
return 0;
}
but i'm confused about finding square root by mental arithmetic


If the required number is interger:
Alternative is to use brute search:
for (int count = 1; count^2<=num; count ++);


pow(x,.5)
(sqrt())

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
http://www.cplusplus.com/forum/beginner/34202/
http://www.dreamincode.net/code/snippet244.htm

No comments:

Post a Comment