Editing Square root (section)

==Computation==
{{Main article|Methods of computing square roots}}
Square roots of positive numbers are not in general [[rational number]]s, and so cannot be written as a terminating or recurring decimal expression. Therefore in general any attempt to compute a square root expressed in decimal form can only yield an approximation, though a sequence of increasingly accurate approximations can be obtained.

Most [[pocket calculator]]s have a square root key. Computer [[spreadsheet]]s and other [[software]] are also frequently used to calculate square roots. Pocket calculators typically implement efficient routines, such as the [[Newton's method]] (frequently with an initial guess of 1), to compute the square root of a positive real number.<ref>{{cite book| last=Parkhurst|first=David F.|title=Introduction to Applied Mathematics for Environmental Science| url=https://archive.org/details/introductiontoap00park_663|url-access=limited| year=2006| publisher=Springer| isbn=9780387342283| pages=[https://archive.org/details/introductiontoap00park_663/page/n249 241]}}</ref><ref>{{cite book|last=Solow|first=Anita E.| title=Learning by Discovery: A Lab Manual for Calculus|year=1993|publisher=Cambridge University Press| isbn=9780883850831| pages=[https://archive.org/details/learningbydiscov0001unse/page/48 48]|url=https://archive.org/details/learningbydiscov0001unse/page/48}}</ref> When computing square roots with [[Common logarithm|logarithm table]]s or [[slide rule]]s, one can exploit the identities<math display="block">\sqrt{a} = e^{(\ln a)/2} = 10^{(\log_{10} a)/2},</math>
where {{math|ln}} and {{math|log<sub>10</sub>}} are the [[Natural logarithm|natural]] and [[base-10 logarithm]]s.

By trial-and-error,<ref>{{cite book |title=Mathematics for Biological Scientists |first1=Mike |last1=Aitken |first2=Bill |last2=Broadhurst |first3=Stephen |last3=Hladky |publisher=Garland Science |year=2009 |isbn=978-1-136-84393-8 |page=41 |url=https://books.google.com/books?id=KywWBAAAQBAJ |url-status=live |archive-url=https://web.archive.org/web/20170301101038/https://books.google.com/books?id=KywWBAAAQBAJ |archive-date=2017-03-01 }} [https://books.google.com/books?id=KywWBAAAQBAJ&pg=PA41 Extract of page 41] {{webarchive|url=https://web.archive.org/web/20170301100516/https://books.google.com/books?id=KywWBAAAQBAJ&pg=PA41 |date=2017-03-01 }}</ref> one can square an estimate for <math>\sqrt{a}</math> and raise or lower the estimate until it agrees to sufficient accuracy. For this technique it is prudent to use the identity<math display="block">(x + c)^2 = x^2 + 2xc + c^2,</math>
as it allows one to adjust the estimate {{mvar|x}} by some amount {{mvar|c}} and measure the square of the adjustment in terms of the original estimate and its square.

The most common [[iterative method]] of square root calculation by hand is known as the "[[Babylonian method]]" or "Heron's method" after the first-century Greek philosopher [[Hero of Alexandria|Heron of Alexandria]], who first described it.<ref>{{cite book
  | last = Heath
  | first = Sir Thomas L.
  | title = A History of Greek Mathematics, Vol. 2
  | publisher = Clarendon Press
  | year = 1921
  | location = Oxford
  | pages = [https://archive.org/details/ahistorygreekma00heatgoog/page/n340 323]–324
  | url = https://archive.org/details/ahistorygreekma00heatgoog
  }}</ref> The method uses the same iterative scheme as the [[Newton–Raphson method]] yields when applied to the function {{math|1=''y'' = ''f''(''x'') = ''x''<sup>2</sup> − ''a''}}, using the fact that its slope at any point is {{math|1=''dy''/''dx'' = ''{{prime|f}}''(''x'') = 2''x''}}, but predates it by many centuries.<ref>{{Cite book
 |title      = Elementary functions: algorithms and implementation
 |first1     = Jean-Mic
 |last1      = Muller
 |publisher  = Springer
 |year       = 2006
 |isbn       = 0-8176-4372-9
 |pages      = 92–93
 |url        = https://books.google.com/books?id=g3AlWip4R38C
 }}, [https://books.google.com/books?id=g3AlWip4R38C&pg=PA92 Chapter 5, p 92] {{webarchive|url=https://web.archive.org/web/20160901091516/https://books.google.com/books?id=g3AlWip4R38C&pg=PA92 |date=2016-09-01 }}
</ref> The algorithm is to repeat a simple calculation that results in a number closer to the actual square root each time it is repeated with its result as the new input. The motivation is that if {{mvar|x}} is an overestimate to the square root of a nonnegative real number {{mvar|a}} then {{math|''a''/''x''}}<!-- please avoid intermixing <math> with a bare text in one paragraph: it is the ugliest pair among 3 existing styles --> will be an underestimate and so the average of these two numbers is a better approximation than either of them. However, the [[inequality of arithmetic and geometric means]] shows this average is always an overestimate of the square root (as noted [[Square root#Geometric construction of the square root|below]]), and so it can serve as a new overestimate with which to repeat the process, which [[Limit of a sequence|converges]] as a consequence of the successive overestimates and underestimates being closer to each other after each iteration. To find {{mvar|x}}:

# Start with an arbitrary positive start value {{mvar|x}}. The closer to the square root of {{mvar|a}}, the fewer the iterations that will be needed to achieve the desired precision.
# Replace {{mvar|x}} by the average {{math|(''x'' + ''a''/''x'') / 2}} between {{math|''x''}} and {{math|''a''/''x''}}.
# Repeat from step 2, using this average as the new value of {{mvar|x}}.

That is, if an arbitrary guess for <math>\sqrt{a}</math> is {{math|''x''<sub>0</sub>}}, and {{math|1 = ''x''<sub>''n'' + 1</sub> = (''x<sub>n</sub>'' + ''a''/''x<sub>n</sub>'') / 2}}, then each {{math|''x''<sub>''n''</sub>}} is an approximation of <math>\sqrt{a}</math> which is better for large {{mvar|n}} than for small {{mvar|n}}. If {{mvar|a}} is positive, the convergence is [[Rate of convergence|quadratic]], which means that in approaching the limit, the number of correct digits roughly doubles in each next iteration. If {{math|1=''a'' = 0}}, the convergence is only linear; however, <math>\sqrt{0} = 0</math> so in this case no iteration is needed.

Using the identity<math display="block">\sqrt{a} = 2^{-n}\sqrt{4^n a},</math>
the computation of the square root of a positive number can be reduced to that of a number in the range {{closed-open|1, 4}}. This simplifies finding a start value for the iterative method that is close to the square root, for which a [[Polynomial function|polynomial]] or [[Piecewise linear function|piecewise-linear]] [[Approximation theory|approximation]] can be used.

The [[Computational complexity theory|time complexity]] for computing a square root with {{mvar|n}} digits of precision is equivalent to that of multiplying two {{mvar|n}}-digit numbers.

Another useful method for calculating the square root is the shifting nth root algorithm, applied for {{math|1= ''n'' = 2}}.

The name of the square root [[Function (programming)|function]] varies from [[programming language]] to programming language, with <code>sqrt</code><ref>{{cite web |title=Function sqrt |work=CPlusPlus.com |date=2016 |publisher=The C++ Resources Network |url=http://www.cplusplus.com/reference/clibrary/cmath/sqrt/ |access-date=June 24, 2016 |url-status=live |archive-url=https://web.archive.org/web/20121122050619/http://www.cplusplus.com/reference/clibrary/cmath/sqrt/ |archive-date=November 22, 2012 }}</ref> (often pronounced "squirt"<ref>{{cite book |title=C++ for the Impatient |first=Brian |last=Overland |page=338 |publisher=Addison-Wesley |date=2013 |isbn=9780133257120 |oclc=850705706 |url=https://books.google.com/books?id=eJFpV-_t4WkC&q=%22squirt%22+sqrt+C%2B%2B&pg=PA338 |access-date=June 24, 2016 |url-status=live |archive-url=https://web.archive.org/web/20160901082021/https://books.google.com/books?id=eJFpV-_t4WkC&pg=PA338&dq=%22squirt%22+sqrt+C%2B%2B&hl=en&sa=X&ved=0ahUKEwjEwfj04sHNAhUY0GMKHatGDnsQ6AEIKDAC#v=onepage&q=%22squirt%22%20sqrt%20C%2B%2B&f=false |archive-date=September 1, 2016 }}</ref>) being common, used in [[C (programming language)|C]] and derived languages such as [[C++]], [[JavaScript]], [[PHP]], and [[Python (programming language)|Python]].