Methods of computing square roots
Algorithms for calculating square roots / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Babylonian method?
Summarize this article for a 10 year old
Methods of computing square roots are algorithms for approximating the non-negative square root of a positive real number . Since all square roots of natural numbers, other than of perfect squares, are irrational,[1] square roots can usually only be computed to some finite precision: these methods typically construct a series of increasingly accurate approximations.
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
Most square root computation methods are iterative: after choosing a suitable initial estimate of , an iterative refinement is performed until some termination criterion is met. One refinement scheme is Heron's method, a special case of Newton's method. If division is much more costly than multiplication, it may be preferable to compute the inverse square root instead.
Other methods are available to compute the square root digit by digit, or using Taylor series. Rational approximations of square roots may be calculated using continued fraction expansions.
The method employed depends on the needed accuracy, and the available tools and computational power. The methods may be roughly classified as those suitable for mental calculation, those usually requiring at least paper and pencil, and those which are implemented as programs to be executed on a digital electronic computer or other computing device. Algorithms may take into account convergence (how many iterations are required to achieve a specified precision), computational complexity of individual operations (i.e. division) or iterations, and error propagation (the accuracy of the final result).
A few methods like paper-and-pencil synthetic division and series expansion, do not require a starting value. In some applications, an integer square root is required, which is the square root rounded or truncated to the nearest integer (a modified procedure may be employed in this case).
Procedures for finding square roots (particularly the square root of 2) have been known since at least the period of ancient Babylon in the 17th century BCE. Babylonian mathematicians calculated the square root of 2 to three sexagesimal "digits" after the 1, but it is not known exactly how. They knew how to approximate a hypotenuse using
(giving for example for the diagonal of a gate whose height is rods and whose width is rods) and they may have used a similar approach for finding the approximation of [2]
Heron's method from first century Egypt was the first ascertainable algorithm for computing square root.[3]
Modern analytic methods began to be developed after introduction of the Arabic numeral system to western Europe in the early Renaissance.[citation needed]
Today, nearly all computing devices have a fast and accurate square root function, either as a programming language construct, a compiler intrinsic or library function, or as a hardware operator, based on one of the described procedures.
Many iterative square root algorithms require an initial seed value. The seed must be a non-zero positive number; it should be between 1 and , the number whose square root is desired, because the square root must be in that range. If the seed is far away from the root, the algorithm will require more iterations. If one initializes with (or ), then approximately iterations will be wasted just getting the order of magnitude of the root. It is therefore useful to have a rough estimate, which may have limited accuracy but is easy to calculate. In general, the better the initial estimate, the faster the convergence. For Newton's method (also called Babylonian or Heron's method), a seed somewhat larger than the root will converge slightly faster than a seed somewhat smaller than the root.
In general, an estimate is pursuant to an arbitrary interval known to contain the root (such as ). The estimate is a specific value of a functional approximation to over the interval. Obtaining a better estimate involves either obtaining tighter bounds on the interval, or finding a better functional approximation to . The latter usually means using a higher order polynomial in the approximation, though not all approximations are polynomial. Common methods of estimating include scalar, linear, hyperbolic and logarithmic. A decimal base is usually used for mental or paper-and-pencil estimating. A binary base is more suitable for computer estimates. In estimating, the exponent and mantissa are usually treated separately, as the number would be expressed in scientific notation.
Decimal estimates
Typically the number is expressed in scientific notation as where and n is an integer, and the range of possible square roots is where .
Scalar estimates
Scalar methods divide the range into intervals, and the estimate in each interval is represented by a single scalar number. If the range is considered as a single interval, the arithmetic mean (5.5) or geometric mean () times are plausible estimates. The absolute and relative error for these will differ. In general, a single scalar will be very inaccurate. Better estimates divide the range into two or more intervals, but scalar estimates have inherently low accuracy.
For two intervals, divided geometrically, the square root can be estimated as[Note 1]
This estimate has maximum absolute error of at a = 100, and maximum relative error of 100% at a = 1.
For example, for factored as , the estimate is . , an absolute error of 246 and relative error of almost 70%.
Linear estimates
A better estimate, and the standard method used, is a linear approximation to the function over a small arc. If, as above, powers of the base are factored out of the number and the interval reduced to , a secant line spanning the arc, or a tangent line somewhere along the arc may be used as the approximation, but a least-squares regression line intersecting the arc will be more accurate.
A least-squares regression line minimizes the average difference between the estimate and the value of the function. Its equation is . Reordering, . Rounding the coefficients for ease of computation,
That is the best estimate on average that can be achieved with a single piece linear approximation of the function y=x2 in the interval . It has a maximum absolute error of 1.2 at a=100, and maximum relative error of 30% at S=1 and 10.[Note 2]
To divide by 10, subtract one from the exponent of , or figuratively move the decimal point one digit to the left. For this formulation, any additive constant 1 plus a small increment will make a satisfactory estimate so remembering the exact number isn't a burden. The approximation (rounded or not) using a single line spanning the range is less than one significant digit of precision; the relative error is greater than 1/22, so less than 2 bits of information are provided. The accuracy is severely limited because the range is two orders of magnitude, quite large for this kind of estimation.
A much better estimate can be obtained by a piece-wise linear approximation: multiple line segments, each approximating some subarc of the original. The more line segments used, the better the approximation. The most common way is to use tangent lines; the critical choices are how to divide the arc and where to place the tangent points. An efficacious way to divide the arc from y = 1 to y = 100 is geometrically: for two intervals, the bounds of the intervals are the square root of the bounds of the original interval, 1×100, i.e. [1,2√100] and [2√100,100]. For three intervals, the bounds are the cube roots of 100: [1,3√100], [3√100,(3√100)2], and [(3√100)2,100], etc. For two intervals, 2√100 = 10, a very convenient number. Tangent lines are easy to derive, and are located at x = √1*√10 and x = √10*√10. Their equations are: and . Inverting, the square roots are: and . Thus for :
The maximum absolute errors occur at the high points of the intervals, at a=10 and 100, and are 0.54 and 1.7 respectively. The maximum relative errors are at the endpoints of the intervals, at a=1, 10 and 100, and are 17% in both cases. 17% or 0.17 is larger than 1/10, so the method yields less than a decimal digit of accuracy.
Hyperbolic estimates
In some cases, hyperbolic estimates may be efficacious, because a hyperbola is also a convex curve and may lie along an arc of Y = x2 better than a line. Hyperbolic estimates are more computationally complex, because they necessarily require a floating division. A near-optimal hyperbolic approximation to x2 on the interval is y=190/(10-x)-20. Transposing, the square root is x = -190/(y+20)+10. Thus for :
The floating division need be accurate to only one decimal digit, because the estimate overall is only that accurate, and can be done mentally. A hyperbolic estimate is better on average than scalar or linear estimates. It has maximum absolute error of 1.58 at 100 and maximum relative error of 16.0% at 10. For the worst case at a=10, the estimate is 3.67. If one starts with 10 and applies Newton-Raphson iterations straight away, two iterations will be required, yielding 3.66, before the accuracy of the hyperbolic estimate is exceeded. For a more typical case like 75, the hyperbolic estimate is 8.00, and 5 Newton-Raphson iterations starting at 75 would be required to obtain a more accurate result.
Arithmetic estimates
A method analogous to piece-wise linear approximation but using only arithmetic instead of algebraic equations, uses the multiplication tables in reverse: the square root of a number between 1 and 100 is between 1 and 10, so if we know 25 is a perfect square (5 × 5), and 36 is a perfect square (6 × 6), then the square root of a number greater than or equal to 25 but less than 36, begins with a 5. Similarly for numbers between other squares. This method will yield a correct first digit, but it is not accurate to one digit: the first digit of the square root of 35 for example, is 5, but the square root of 35 is almost 6.
A better way is to the divide the range into intervals half way between the squares. So any number between 25 and half way to 36, which is 30.5, estimate 5; any number greater than 30.5 up to 36, estimate 6.[Note 3] The procedure only requires a little arithmetic to find a boundary number in the middle of two products from the multiplication table. Here is a reference table of those boundaries:
a | nearest square | est. |
---|---|---|
1 to 2.5 | 1 (= 12) | 1 |
2.5 to 6.5 | 4 (= 22) | 2 |
6.5 to 12.5 | 9 (= 32) | 3 |
12.5 to 20.5 | 16 (= 42) | 4 |
20.5 to 30.5 | 25 (= 52) | 5 |
30.5 to 42.5 | 36 (= 62) | 6 |
42.5 to 56.5 | 49 (= 72) | 7 |
56.5 to 72.5 | 64 (= 82) | 8 |
72.5 to 90.5 | 81 (= 92) | 9 |
90.5 to 100 | 100 (= 102) | 10 |
The final operation is to multiply the estimate k by the power of ten divided by 2, so for ,
The method implicitly yields one significant digit of accuracy, since it rounds to the best first digit.
The method can be extended 3 significant digits in most cases, by interpolating between the nearest squares bounding the operand. If , then is approximately k plus a fraction, the difference between a and k2 divided by the difference between the two squares:
where
The final operation, as above, is to multiply the result by the power of ten divided by 2;
k is a decimal digit and R is a fraction that must be converted to decimal. It usually has only a single digit in the numerator, and one or two digits in the denominator, so the conversion to decimal can be done mentally.
Example: find the square root of 75. 75 = 75 × 102 · 0, so a is 75 and n is 0. From the multiplication tables, the square root of the mantissa must be 8 point something because 8 × 8 is 64, but 9 × 9 is 81, too big, so k is 8; something is the decimal representation of R. The fraction R is 75 - k2 = 11, the numerator, and 81 - k2 = 17, the denominator. 11/17 is a little less than 12/18, which is 2/3s or .67, so guess .66 (it's ok to guess here, the error is very small). So the estimate is 8 + .66 = 8.66. √75 to three significant digits is 8.66, so the estimate is good to 3 significant digits. Not all such estimates using this method will be so accurate, but they will be close.
Binary estimates
When working in the binary numeral system (as computers do internally), by expressing as where , the square root can be estimated as
which is the least-squares regression line to 3 significant digit coefficients. has maximum absolute error of 0.0408 at =2, and maximum relative error of 3.0% at =1. A computationally convenient rounded estimate (because the coefficients are powers of 2) is:
which has maximum absolute error of 0.086 at 2 and maximum relative error of 6.1% at a = 0.5 and a = 2.0.
For , the binary approximation gives . , so the estimate has an absolute error of 19 and relative error of 5.3%. The relative error is a little less than 1/24, so the estimate is good to 4+ bits.
An estimate for good to 8 bits can be obtained by table lookup on the high 8 bits of , remembering that the high bit is implicit in most floating point representations, and the bottom bit of the 8 should be rounded. The table is 256 bytes of precomputed 8-bit square root values. For example, for the index 111011012 representing 1.851562510, the entry is 101011102 representing 1.35937510, the square root of 1.851562510 to 8 bit precision (2+ decimal digits).