This article presents and explains several methods which can be used to calculate 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:
Two and six are used because
and
When working in the binary numeral system (as computers do internally), an alternative method is to use
(here D is the number of binary digits).
Babylonian method
Perhaps the first algorithm used for approximating
is known as the "Babylonian method", named after the Babylonians, or "Heron's method", named after the first-century Greek mathematician Heron of Alexandria who gave the first explicit description of the method. 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:
- Start with an arbitrary positive start value x 0 (the closer to the root, the better).
- Let x n +1 be the average of x n and S / x n (using the arithmetic mean to approximate the geometric mean).
- Repeat steps 2 and 3, until the desired accuracy is achieved.
It can also be represented as:
This algorithm works equally well in the p-adic numbers, but cannot be used to identify real square roots with p-adic square roots; it is easy, for example, to construct a sequence of rational numbers by this method which converges to + 3 in the reals, but to − 3 in the 2-adics.
Example
To calculate
, where S = 125348, to 6 significant figures, we will use the rough estimation method above to get x 0 . The number of digits in S is D =6=2·2+2. So, n =2 and the rough estimate is
Therefore,
Convergence
We let the relative error in x n be defined by
and thus
Then one can show that
and thus that
and consequently that convergence is assured provided that x 0 and S are both positive.
Worst case for convergence
If one is using the rough estimate above with the Babylonian method, then the worst cases are:
Thus in any case,
Remember that rounding errors will slow the convergence. One should keep at least one extra digit beyond the desired accuracy of the x n which you are calculating to minimize round off error.
Exponential identity
Pocket calculators typically implement good routines to compute the exponential function and the natural logarithm, and then compute the square root of S using the identity
The same identity is used when computing square roots with logarithm tables or slide rules.
Method of bisecting intervals
Another simple way to find a square root is the high/low method, similar to the bisection method. This method involves guessing a number based on known squares, then checking if its square is too high or too low and adjusting accordingly.
Suppose you want to find the square root of 20. You know that the square of 5 is 25, and that the square of 4 is 16, so it must be between 4 and 5. Now you guess 4.5. The square of 4.5 equals 20.25 and is too high, so you guess 4.4. This equals 19.36 and is too low. So the root is between 4.4 and 4.5. Continue this pattern until you get as many decimal places as needed. We are going to stop at three.
Now that we know that it is between 4.472 and 4.473, we now know that the square root of 20 to the first three decimal places is 4.472 .
Bakhshali approximation
This is a method for finding an approximation to a square root which was described in an ancient manuscript known as the Bakhshali manuscript. It is equivalent to two iterations of the Babylonian method beginning with N . The original presentation goes as follows: To calculate
This can be also written as:
Example
We'll find
Digit by digit calculation
This is a method to find each digit of the square root in a sequence. It is slower than the Babylonian method (if you have a calculator which can divide in one operation), but it has several advantages:
- It can be easier for manual calculations.
- Every digit of the root found is known to be correct, i.e. it will not have to be changed later.
- If the square root has an expansion which terminates, the algorithm will terminate after the last digit is found. Thus, it can be used to check whether a given integer is a square number.
Napier's bones include an aid for the execution of this algorithm. The Shifting nth-root algorithm is a generalization of this method.
The algorithm works for any base, and naturally, the way it proceeds depends on the base chosen.
Decimal (base 10)
Write the original number in decimal form. The numbers are written similar to the long division algorithm, and, as in long division, the root will be written on the line above. Now separate the digits into pairs, starting from the decimal point and going both left and right. The decimal point of the root will be above the decimal point of the square. One digit of the root will appear above each pair of digits of the square.
Beginning with the left-most pair of digits, do the following procedure for each pair:
- Starting on the left, bring down the most significant (leftmost) pair of digits not yet used (if all the digits have been used, write "00") and write them to the right of the remainder from the previous step (on the first step, there will be no remainder). In other words, multiply the remainder by 100 and add the two digits. This will be the current value c .
- Find p , y and x , as follows:
- Let p be the part of the root found so far , ignoring any decimal point. (For the first step, p = 0).
- Determine the greatest digit x such that
does not exceed c .
- Note: 20 p + x is simply twice p , with the digit x appended to the right).
- Note: You can find x by guessing what c /(20· p ) is and doing a trial calculation of y , then adjusting x upward or downward as necessary.
- Place the digit x as the next digit of the root, i.e above the two digits of the square which you just brought down. Thus the next p will be the old p times 10 plus x .
- Subtract y from c to form a new remainder.
- If the remainder is zero and there are no more digits to bring down, then the algorithm has terminated. Otherwise go back to step 1 for another iteration.
Examples
Find the square root of 152.2756.
1 2. 3 4 / \/ 01 52.27 56 01 1*1 <= 1 < 2*2 x = 1 01 y = x*x = 1*1 = 1 00 52 22*2 <= 52 < 23*3 x = 2 00 44 y = (20+x)*x = 22*2 = 44 08 27 243*3 <= 827 < 244*4 x = 3 07 29 y = (240+x)*x = 243*3 = 729 98 56 2464*4 <= 9856 < 2465*5 x = 4 98 56 y = (2460+x)*x = 2464*4 = 9856 00 00 Algorithm terminates: Answer is 12.34Find the square root of 2.
1. 4 1 4 2 / \/ 02.00 00 00 00 02 1*1 <= 2 < 2*2 x = 1 01 y = x*x = 1*1 = 1 01 00 24*4 <= 100 < 25*5 x = 4 00 96 y = (20+x)*x = 24*4 = 96 04 00 281*1 <= 400 < 282*2 x = 1 <
Fast inverse square root - Wikipedia, the free encyclopedia
Fast inverse square root (sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5f3759df) is a method of calculating the reciprocal of a square root for a 32-bit ...
Fast square root in C (Application Note 18180)
This application note describes a solution for a fast square root routine in C. Both the parameter and the result are 16-bit unsigned ints. Even though it is not 100% precise, the ...
Fast square root in C
IAR Application Note AN-G002 1 IAR Application Note G-002 Fast square root in C SUMMARY This application note describes a solution for a fast square root routine in C.
Understanding Quake’s Fast Inverse Square Root | BetterExplained
An article:http://www.beyond3d.com/articles/fastinvsqrt/ and research paper:http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf describe a fast, seemingly
Fast Inverse Square Root
THE MATHEMATICS BEHIND THE FAST INVERSE SQUARE ROOT FUNCTION CODE Fast Inverse Square Root
FAST INVERSE SQUARE ROOT
2 CHRISLOMONT but close) explanation by D. Eberly[4]. However his explanation is illuminating. Further digging found no correct explanation oft his code.
Fast Square Root - ILabWiki
C++ Source Code for Computing Fast Square Root Approximations with Floating and Double Precision Floating Points. Here are listed a few different methods for computing a square ...
Nicolas Cannasse Blog
love this trick. Magic. here's the magic explaination: http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/..better do n = d + d than n = d * 2, wow ...
Fast Integer Square Root
2000 Microchip Technology Inc. Preliminary DS91040A-page 1 TB040 INTRODUCTION One very common and relatively quick method for finding the square root of a number is the Newton ...
Wikipedia:Peer review/Fast inverse square root/archive1 - Wikipedia ...
Article (edit | history) • Article talk (edit | history) • Watch • Watch peer review ... A script has been used to generate a semi-automated review of the article for issues ...