Square root algorithms - Revision history

GuccizBud: /* Continued fraction expansion */ Copy edit ▸ Presentation ▸ Impossible to see the whole pink box on mobile! Presentation was optimized pre-smartphone ( 𝑖.𝑒. for desktop/laptop).

2025-05-30T02:09:20Z

Continued fraction expansion: Copy edit ▸ Presentation ▸ Impossible to see the whole pink box on mobile! Presentation was optimized pre-smartphone ( 𝑖.𝑒. for desktop/laptop).

← Previous revision		Revision as of 02:09, 30 May 2025
Line 536:		Line 536:
	<math display="block"> \sqrt{S} = a + \frac{r}{a + \sqrt{S}}. </math>		<math display="block"> \sqrt{S} = a + \frac{r}{a + \sqrt{S}}. </math>

	By applying this expression for <math>\sqrt{S}</math> to the denominator term of the fraction, we have		By applying this expression for <math>\sqrt{S}</math> to the denominator term of the fraction, we have:
	<math display="block"> \sqrt{S} = a + \frac{r}{a + (a + \frac{r}{a + \sqrt{S}})} = a + \frac{r}{2a + \frac{r}{a + \sqrt{S}}}. </math>		<math display="block"> \sqrt{S} = a + \frac{r}{a + (a + \frac{r}{a + \sqrt{S}})} = a + \frac{r}{2a + \frac{r}{a + \sqrt{S}}}. </math>
	<div style="~~float:right;~~ padding:1em; margin:0 0 0 1em~~; width:450px~~; border:1px solid; background:#faf3ee;">		<div style="padding:1em; margin:0 0 0 1em; border:1px solid; background:#faf3ee;">
			{{np}}
	{{center\|'''<big>Compact notation</big>'''}}		{{center\|'''<big>Compact notation</big>'''}}
	The numerator/denominator expansion for continued fractions (~~see left~~) is cumbersome to write as well as to embed in text formatting systems. So mathematicians have devised several alternative notations, ~~like<ref>~~see: [[Generalized continued fraction#Notation~~]]</ref>~~		The numerator/denominator expansion for continued fractions (above) is cumbersome to write as well as to embed in text formatting systems. So mathematicians have devised several alternative notations {{xref\|(see: {{slink\|Generalized continued fraction\|Notation}})}} such as:
	<math display="block">		<math display="block">
	\sqrt{S} = a+		\sqrt{S} = a+

GuccizBud: /* Exponential identity */ Copy edit ▸ Presentation (was line-wrapping right after open parentheses symbol) and MTCE tags (citation request tag replaced with unreferenced section tag).

2025-05-30T01:17:44Z

Exponential identity: Copy edit ▸ Presentation (was line-wrapping right after open parentheses symbol) and MTCE tags (citation request tag replaced with unreferenced section tag).

← Previous revision		Revision as of 01:17, 30 May 2025
Line 453:		Line 453:

	==Exponential identity==		==Exponential identity==
			{{unreferenced section\|date=May 2020}}
	[[calculator\|Pocket calculator]]s typically implement good routines to compute the [[exponential function]] and the [[natural logarithm]], and then compute the square root of ''S'' using the identity found using the properties of logarithms (<math>\ln x^n = n \ln x</math>) and exponentials (<math>e^{\ln x} = x</math>)~~:{{cn\|date=May 2020~~}}		[[calculator\|Pocket calculator]]s typically implement good routines to compute the [[exponential function]] and the [[natural logarithm]], and then compute the square root of ''S'' using the identity found using the properties of logarithms (<math>\ln x^n = n \ln x</math>) and exponentials {{nowrap\|(<math>e^{\ln x} = x</math>)}}:
	<math display="block">\sqrt{S} = e^{\frac{1}{2}\ln S}.</math>		<math display="block">\sqrt{S} = e^{\frac{1}{2}\ln S}.</math>
	The denominator in the fraction corresponds to the ''n''th root. In the case above the denominator is 2, hence the equation specifies that the square root is to be found. The same identity is used when computing square roots with [[logarithm table]]s or [[slide rule]]s.		The denominator in the fraction corresponds to the ''n''th root. In the case above the denominator is 2, hence the equation specifies that the square root is to be found. The same identity is used when computing square roots with [[logarithm table]]s or [[slide rule]]s.

GuccizBud: /* Initial estimate */ Copy edit ▸ Links ▸ "Mantissa" redirected to section within the same article (rather than the article top) that more directly addresses the word.

2025-05-29T23:47:37Z

Initial estimate: Copy edit ▸ Links ▸ "Mantissa" redirected to section within the same article (rather than the article top) that more directly addresses the word.

← Previous revision		Revision as of 23:47, 29 May 2025
Line 35:		Line 35:
	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 <math>S</math>, 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 <math>x_0=1</math> (or <math>S</math>), then approximately <math> \tfrac12 \vert \log_2 S \vert </math> 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, a seed somewhat larger than the root will converge slightly faster than a seed somewhat smaller than the root.		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 <math>S</math>, 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 <math>x_0=1</math> (or <math>S</math>), then approximately <math> \tfrac12 \vert \log_2 S \vert </math> 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, 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 <math>[x_0,S/x_0]</math>). The estimate is a specific value of a functional approximation to <math>f(x)=\sqrt{x}</math> over the interval. Obtaining a better estimate involves either obtaining tighter bounds on the interval, or finding a better functional approximation to <math>f(x)</math>. 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~~ (logarithm)\|mantissa]] are usually treated separately, as the number would be expressed in scientific notation.		In general, an estimate is pursuant to an arbitrary interval known to contain the root (such as <math>[x_0,S/x_0]</math>). The estimate is a specific value of a functional approximation to <math>f(x)=\sqrt{x}</math> over the interval. Obtaining a better estimate involves either obtaining tighter bounds on the interval, or finding a better functional approximation to <math>f(x)</math>. 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 (logarithm)#Mantissa and characteristic\|mantissa]] are usually treated separately, as the number would be expressed in scientific notation.

	===Decimal estimates===		===Decimal estimates===

Fgnievinski at 19:12, 18 May 2025

2025-05-18T19:12:58Z

← Previous revision		Revision as of 19:12, 18 May 2025
Line 5:		Line 5:
	}}		}}

	'''~~Methods~~ of ~~computing square roots~~''' ~~are [[algorithm]]s for approximating~~ the non-negative [[square root]] <math>\sqrt{S}</math> of a positive [[real number]] <math>S</math>.		'''Square root algorithms''' compute the non-negative [[square root]] <math>\sqrt{S}</math> of a positive [[real number]] <math>S</math>.
	Since all square roots of [[natural number]]s, other than of [[square number\|perfect square]]s, are [[Irrational number\|irrational]],{{sfn\|Jackson\|2011}}		Since all square roots of [[natural number]]s, other than of [[square number\|perfect square]]s, are [[Irrational number\|irrational]],{{sfn\|Jackson\|2011}}
	square roots can usually only be computed to some finite precision: these ~~methods~~ typically construct a series of increasingly accurate [[Numerical approximation\|approximations]].		square roots can usually only be computed to some finite precision: these [[algorithm]]s typically construct a series of increasingly accurate [[Numerical approximation\|approximations]].

	Most square root computation methods are iterative: after choosing a suitable [[#Initial estimate\|initial estimate]] of <math>\sqrt{S}</math>, an iterative refinement is performed until some termination criterion is met.		Most square root computation methods are iterative: after choosing a suitable [[#Initial estimate\|initial estimate]] of <math>\sqrt{S}</math>, an iterative refinement is performed until some termination criterion is met.

Fgnievinski: Fgnievinski moved page Methods of computing square roots to Square root algorithms

2025-05-18T19:08:57Z

Fgnievinski moved page Methods of computing square roots to Square root algorithms

← Previous revision	Revision as of 19:08, 18 May 2025
(No difference)

Dominic3203: /* top */

2025-04-27T04:28:03Z

top

← Previous revision		Revision as of 04:28, 27 April 2025
Line 635:		Line 635:

	-->		-->
			{{see also\|binary logarithm}}
	A number is represented in a [[floating point]] format as <math>m\times b^p</math> which is also called [[scientific notation]]. Its square root is <math>\sqrt{m}\times b^{p/2}</math> and similar formulae would apply for cube roots and logarithms. On the face of it, this is no improvement in simplicity, but suppose that only an approximation is required: then just <math>b^{p/2}</math> is good to an order of magnitude. Next, recognise that some powers, {{mvar\|p}}, will be odd, thus for 3141.59 = 3.14159{{x10^\|3}} rather than deal with fractional powers of the base, multiply the mantissa by the base and subtract one from the power to make it even. The adjusted representation will become the equivalent of 31.4159{{x10^\|2}} so that the square root will be {{radic\|31.4159}}{{x10^\|1}}.		A number is represented in a [[floating point]] format as <math>m\times b^p</math> which is also called [[scientific notation]]. Its square root is <math>\sqrt{m}\times b^{p/2}</math> and similar formulae would apply for cube roots and logarithms. On the face of it, this is no improvement in simplicity, but suppose that only an approximation is required: then just <math>b^{p/2}</math> is good to an order of magnitude. Next, recognise that some powers, {{mvar\|p}}, will be odd, thus for 3141.59 = 3.14159{{x10^\|3}} rather than deal with fractional powers of the base, multiply the mantissa by the base and subtract one from the power to make it even. The adjusted representation will become the equivalent of 31.4159{{x10^\|2}} so that the square root will be {{radic\|31.4159}}{{x10^\|1}}.

195.195.176.156: /* History */

2025-04-03T12:51:46Z

History

← Previous revision		Revision as of 12:51, 3 April 2025
Line 22:		Line 22:
	==History==		==History==
	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.		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 mathematics\|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		[[Babylonian mathematics\|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
	<math display="block">\sqrt{a^2+b^2}\approx a+\frac{b^2}{2a}</math>		<math display="block">\sqrt{a^2+b^2}\approx a+\frac{b^2}{2a}</math>
	(giving for example <math>\frac{41}{60}+\frac{15}{3600}</math> for the diagonal of a gate whose height is <math>\frac{40}{60}</math> rods and whose width is <math>\frac{10}{60}</math> rods) and they may have used a similar approach for finding the approximation of <math>\sqrt 2.</math>{{sfn\|Fowler\|Robson\|1998}}		(giving for example <math>\frac{41}{60}+\frac{15}{3600}</math> for the diagonal of a gate whose height is <math>\frac{40}{60}</math> rods and whose width is <math>\frac{10}{60}</math> rods) and they may have used a similar approach for finding the approximation of <math>\sqrt 2.</math>{{sfn\|Fowler\|Robson\|1998}}

Jdmartin86: /* Basic principle */ added "the"

2025-03-31T16:39:28Z

Basic principle: added "the"

← Previous revision		Revision as of 16:39, 31 March 2025
Line 342:		Line 342:
	</math>		</math>

	This expression allows us to find the square root by sequentially guessing the values of <math>a_i</math>s. Suppose that the numbers <math>a_1, \ldots, a_{m-1}</math> have already been guessed, then the ''m''-th term of the right-hand-side of above summation is given by <math>Y_{m} = \left[2 P_{m-1} + a_{m}\right] a_{m},</math> where <math display="inline">P_{m-1} = \sum_{i=1}^{m-1} a_i</math> is the approximate square root found so far. Now each new guess <math>a_m</math> should satisfy the recursion		This expression allows us to find the square root by sequentially guessing the values of <math>a_i</math>s. Suppose that the numbers <math>a_1, \ldots, a_{m-1}</math> have already been guessed, then the ''m''-th term of the right-hand-side of the above summation is given by <math>Y_{m} = \left[2 P_{m-1} + a_{m}\right] a_{m},</math> where <math display="inline">P_{m-1} = \sum_{i=1}^{m-1} a_i</math> is the approximate square root found so far. Now each new guess <math>a_m</math> should satisfy the recursion
	<math display="block">X_{m} = X_{m-1} - Y_{m},</math>		<math display="block">X_{m} = X_{m-1} - Y_{m},</math>
	where <math>X_{m}</math> is the sum of all the terms after <math>Y_{m}</math>, i.e. the remainder, such that <math>X_m \geq 0</math> for all <math>1\leq m\leq n,</math> with initialization <math>X_0 = S.</math> When <math>X_n = 0,</math> the exact square root has been found; if not, then the sum of the <math>a_i</math>s gives a suitable approximation of the square root, with <math>X_n</math> being the approximation error.		where <math>X_{m}</math> is the sum of all the terms after <math>Y_{m}</math>, i.e. the remainder, such that <math>X_m \geq 0</math> for all <math>1\leq m\leq n,</math> with initialization <math>X_0 = S.</math> When <math>X_n = 0,</math> the exact square root has been found; if not, then the sum of the <math>a_i</math>s gives a suitable approximation of the square root, with <math>X_n</math> being the approximation error.

172.56.153.22: Corrected link to "The Preparation of Programs for an Electronic Digital Computer" by Wilkes et al. (original link pointed to "A history of Greek mathematics" by Heath). Book does not detail a square root algorithm on page 146 but a closely related division algorithm.

2025-03-18T03:08:20Z

Corrected link to "The Preparation of Programs for an Electronic Digital Computer" by Wilkes et al. (original link pointed to "A history of Greek mathematics" by Heath). Book does not detail a square root algorithm on page 146 but a closely related division algorithm.

← Previous revision		Revision as of 03:08, 18 March 2025
Line 918:		Line 918:
	\| year = 1951		\| year = 1951
	\| oclc = 475783493		\| oclc = 475783493
	\| pages = [https://archive.org/details/~~ahistorygreekma00heatgoog~~/page/~~n340~~ ~~323~~]~~–324~~		\| pages = [https://archive.org/details/programsforelect00wilk/page/146 146]–262
	\| url = https://archive.org/details/~~ahistorygreekma00heatgoog~~		\| url = https://archive.org/details/programsforelect00wilk
	}}		}}
	{{Refend}}		{{Refend}}

ScrabbleTiles: Restored revision 1280281421 by ScrabbleTiles (talk): Promotion

2025-03-13T19:41:08Z

Restored revision 1280281421 by ScrabbleTiles (talk): Promotion

← Previous revision		Revision as of 19:41, 13 March 2025
Line 205:		Line 205:

	Therefore <math>\sqrt{\,125348\,} \approx 354.0452</math> to seven significant figures. (The true value is 354.0451948551....) Notice that early iterations only needed to be computed to 1, 2 or 4 places to produce an accurate final answer.		Therefore <math>\sqrt{\,125348\,} \approx 354.0452</math> to seven significant figures. (The true value is 354.0451948551....) Notice that early iterations only needed to be computed to 1, 2 or 4 places to produce an accurate final answer.
	===Animation===
	[https://longhai.shinyapps.io/newtonsqrt/ This shiny app] provides an animated illustration of this algorithm.

	[[File:Square Root Animation.png\|thumb]]

	===Convergence===		===Convergence===