Talk:Square root algorithms

Merge "Approximations that depend on the floating point representation" into "Initial estimate"

I believe the section "Approximations that depend on the floating point representation" should be merged into "Initial estimate", since it is a special case of "Binary estimates". Merging would clear up the fact that the floating point trick gives an initial rough approximation, which is then typically iteratively improved.

I also believe the "Initial estimate" section should appear after the section on Heron's method, as the reader is likely more interested in the general idea of iterative refinement than in the details of how to obtain a good initial estimate in all possible ways.

Additionally, in my opinion the entirety of the article could benefit from some trimming/rewriting, as many sections contain redundant information, unnecessary details, and awkward formulations. BlueRavel (talk) 14:54, 4 December 2023 (UTC)

Your proposition makes sense to me, and I dont necessarily disagree. That said though, as a pure mathematician, I am uninclined to blur the lines between programmatical issues and mathematical problems. I think maintaining a distinction is appropriate. An analysis of the pure mathematical problem of initial estimation in these abstract reiterative processes is a decidedly distinct discussion from considerations in this programming language, or that programming language, or this architecture, or that architecture. The former is future-proofed, the latter is not. CogitoErgoCogitoSum (talk) 21:09, 11 February 2024 (UTC)

Useful addition??

Not sure if its useful, but I have found that, in general, ${\sqrt {x+2}}\approx {\frac {x+1}{\sqrt {x}}}$, and if x=n² we get ${\sqrt {n^{2}+2}}\approx n+{\frac {1}{n}}$.

Similarly ${\sqrt {x+4}}\approx {\frac {x+2}{\sqrt {x}}}$.

I sometimes use this for quick pencil and paper calculations, if Im close enough to a convenient value.

Not sure if this is a known or established property, proven, bounded, or if its already in the article in some alternative capacity, or if its even appropriate for this article. I do know the taylor series approximation with two terms connects these expressions. CogitoErgoCogitoSum (talk) 21:05, 11 February 2024 (UTC)

There is nothing special about 2 and 4: ${\sqrt {x+2c}}\approx {\frac {x+c}{\sqrt {x}}}$ provided that c is small compared to x. This is, in fact, just the first two terms of the series given in the article under the section heading "Taylor series". JBW (talk) 01:45, 13 February 2024 (UTC)

I don't think they are useful. In the first, you have replaced a square root and an addition with a square root, an addition, and a division to get an approximate answer. Bubba73 ^{You talkin' to me?} 08:02, 13 February 2024 (UTC)

Python tweak needed

I noticed the interesting Python example and thought I had better look at it before a gnome removes it as OR or whatever. There is a syntax error in the following line: the inner "..." should use apostrophes not quotes because of the quotes on the overall string.

print(f"2) {sqrt_Heron(Decimal("3.1415926535897932384626433832795028841971693993"))}")

Johnuniq (talk) 03:42, 21 October 2025 (UTC)

Fixed. Changed to

print(f"2) {sqrt_Heron(Decimal('3.1415926535897932384626433832795028841971693993'))}")

Marc Schroeder (talk) 13:25, 22 October 2025 (UTC)

Halley's method versus Heron's method

Halley's method should not be mixed into Heron's method, but put into a separate section.

Halley's method $x_{n+1}=x_{n}\cdot {\frac {x_{n}^{2}+3S}{3x_{n}^{2}+S}}$ requires one division and two multiplications per iteration (the squaring in the numerator can be re-used in the denominator). I do not count the factor of 3 in the denominator because that can be done by a shift and an addition which are negligible compared to multiplication. The 3S in the numerator need only be done once at the outset, so it is negligible also. After the initial division, the quotient is known to sufficient precision that we only need to do one step of the division algorithm which amounts to three multiplications. Thus the cost of one iteration of Halley's method amounts to five multiplications. Five iterations would be 25 multiplications for a 243-fold increase in precision.

By contrast, Heron's method only requires one division. (Multiplication by one half is just a shift and the addition is also negligible.) So it costs three multiplications per iteration. Eight iterations of Heron's method would thus cost 24 multiplications for a 256-fold increase in precision. So Heron's method costs less while giving you more precision. (revised once) JRSpriggs (talk) 02:39, 8 November 2025 (UTC)

Pseudo-code for a possible implementation of Heron's method:

Input S as a real number.

If S < 0, then raise an exception (error=out).

If S = 0, then return 0.

Let X = 1. current estimate of the square-root of S

Let R = 1. current estimate of the reciprocal of X

Begin loop.

Let X = ½(X + R·S). one step of Heron's method

Let T = max (½, 2 - R·X). first half of updating R

If (1 - tolerance) < T < (1 + tolerance), then return X. testing whether we are done while avoiding another multiplication

Let R = R·T. second half of updating R to complete one step of division algorithm

End loop.

OK? JRSpriggs (talk) 19:02, 8 November 2025 (UTC)

One might think that the errors introduced by only using one step of the division algorithm per iteration of Heron's method would slow the convergence. However, the steps of the division algorithm under estimate R while Heron's method over estimates X, so the effects tend to cancel out and speed it up. JRSpriggs (talk) 15:18, 10 November 2025 (UTC)

Similar pseudo-code for a possible implementation of Halley's method:

Input S as a real number.

If S < 0, then raise an exception (error=out).

If S = 0, then return 0.

Let 3S = 2S + S. shift and add to multiply by three

Let X = 1. current estimate of the square-root of S

Let XSQ = 1. current estimate of X squared

Let R = ¼. current estimate of the reciprocal of D

Begin loop.

Let X = X·R·(XSQ + 3S). one step of Halley's method

Let XSQ = X·X.

Let D = 2XSQ + XSQ + S. shift and add to get 3XSQ without multiplying and thence the denominator

Let T = max (½, 2 - R·D). first half of updating R

If (1 - tolerance) < T < (1 + tolerance), then return X. testing whether we are done while avoiding another multiplication

Let R = R·T. second half of updating R to complete one step of division algorithm

End loop.

OK? JRSpriggs (talk) 23:59, 20 November 2025 (UTC)

To avoid an explosive change in the value of the estimate of the square-root in Halley's method, we should put a bound on the change. I suggest:

$x_{n+1}=x_{n}\cdot (1+2\operatorname {median} \,(-{\tfrac {1}{4}},{\frac {S-{x_{n}}^{2}}{3x_{n}^{2}+S}},{\tfrac {1}{2}}))$.

OK? JRSpriggs (talk) 16:53, 26 November 2025 (UTC)

Pseudo-code for a possible implementation of Halley's method with bounded change:

Input S as a real number.

If S < 0, then raise an exception (error=out).

If S = 0, then return 0.

Let X = 1. current estimate of the square-root of S

Let XSQ = 1. current estimate of X squared

Let R = ¼. current estimate of the reciprocal of D

Begin loop.

Let X = X·(1 + 2 median (-¼, R·(S - XSQ),½)). one step of Halley's method with bounded change

Let XSQ = X·X.

Let D = 2XSQ + XSQ + S. shift and add to get 3XSQ without multiplying and thence the denominator

Let T = max (½, 2 - R·D). first half of updating R

If (1 - tolerance) < T < (1 + tolerance), then return X. testing whether we are done while avoiding another multiplication

Let R = R·T. second half of updating R to complete one step of division algorithm

End loop.

OK? JRSpriggs (talk) 18:48, 26 November 2025 (UTC)

Edit Request: Add Iyengar Square Root Method

Proposed Addition: Please consider adding the following subsection under the "Rational approximations" or "Iterative methods" section of the article.

Reason: The Iyengar method was published in 2024 in Parabola (a peer-reviewed journal published by the University of New South Wales). It provides an elementary, calculus-free recurrence relation for square root approximations using bounding perfect squares.

Wikitext:

Iyengar Method

Published in 2024 by Nishant Iyengar and Anju Iyengar, the Iyengar Method is an elementary, calculus-free iterative algorithm designed to generate rational approximations for positive square roots. The method relies solely on primary-school arithmetic operations (addition, multiplication, and division) to form a self-correcting fraction ladder, avoiding derivatives or arbitrary initial guesses required by Newton's method.

1. 1. 1. 1. Algorithm

To approximate $\sqrt{a}$ for a positive real number $a$ that is not a perfect square:

1. Determine Bounding Squares: Identify the nearest perfect squares $s^2$ and $S^2$ such that:

  :$s^2 \le a \le S^2$

2. Compute Initial Parameters: Define the relative offset $N$, span $D$, and initial fractional factor $A$:

  :$N = a - s^2$
  :$D = S^2 - s^2$
  :$A = \frac{N}{D}$

3. Iterative Step: Construct the sequence of rational corrections $P_n$ for $n \ge 1$:

  :$P_1 = \frac{N}{D - 1 + A}$
  :$P_n = \frac{N}{D - 1 + P_{n-1}} \quad \text{for } n \ge 2$

The $n$-th rational approximation of the square root is given by:

$R_n = s + P_n \approx \sqrt{a}$

1. 1. 1. 1. Convergence and Properties

The sequence $R_n$ strictly converges to $\sqrt{a}$ as $n \to \infty$. Because the initial state parameters are explicitly calculated from the nearest integer bounds, the iteration does not require manual trial-and-error initial guesses. For multi-digit inputs, the algorithm exhibits accelerated numerical convergence, capable of achieving up to 9 to 12 decimal places of accuracy within 4 to 5 iterations. ~2026-41315-37 (talk) 08:58, 23 July 2026 (UTC)

It is extremely hard to read your suggestion above. Please re-write it in wikipedia's version of LaTeX, so that it will be legible. JRSpriggs (talk) 13:56, 23 July 2026 (UTC)

Sir my submission

Iyengar's square root method is an iterative numerical technique for approximating the square root of a positive real number using elementary arithmetic operations (addition, multiplication, and division). Proposed by Nishant Iyengar and Anju Iyengar in 2024, it is classified as a "bottom-up" algorithm because it achieves rapid convergence and high precision—comparable to "top-down" techniques like Newton's method—while relying only on middle-school mathematical concepts.

== Background ==

Methods for calculating non-negative square roots are broadly categorized into two types:

• Top-down methods: Algorithms like Newton's method or Taylor series expansions, which utilize advanced calculus and undergraduate-level concepts to compute square roots.
• Bottom-up methods: Pedagogical algorithms that rely solely on basic arithmetic operations taught at the elementary or middle-school level.

While traditional bottom-up methods are often slow to converge or computationally tedious, the Iyengar method provides a rational approximation $R_{n}\approx {\sqrt {a}}$ that converges rapidly with minimal computational overhead.

== Previous Method ==

In a prior paper, the authors proposed a single-step interval-weighted denominator approximation:

1. For a given positive real number $a$, find perfect squares $s^{2}$ and $S^{2}$ such that:

$s^{2}\leq a\leq S^{2}$

2. Define the intermediate terms:

$N=a-s^{2}$

$D=S-s$

$A={\frac {N}{D}}$

3. Calculate the single-step rational approximation:

$R=s+{\frac {N}{(D-1)+A}}\approx {\sqrt {a}}$

== The Modified Iterative Method ==

The updated algorithm modifies the third step by introducing an iterative relation for $P_{n}$:

=== Algorithm Steps ===

1. Bound Selection: Find integer or exact values $s$ and $S$ such that $s^{2}\leq a\leq S^{2}$.

2. Compute Intermediate Values:

$N=a-s^{2}$

$D=S-s$

$A={\frac {N}{D}}$

3. Iterative Formula: Define $P_{1}$ as:

$P_{1}={\frac {N}{(D-1)+A}}$

For $n\geq 2$, calculate recursively:

$P_{n}={\frac {N}{(D-1)+P_{n-1}}}$

4. Rational Approximation: The $n$-th approximation of the square root is:

$R_{n}=s+P_{n}$

As $n\to \infty$, the sequence converges to the exact value:

$\lim _{n\to \infty }R_{n}={\sqrt {a}}$

== Example ==

To calculate ${\sqrt {70.28}}$:

1. Choose bounding perfect squares $s^{2}=64$ ($s=8$) and $S^{2}=81$ ($S=9$).

2. Calculate terms:

$N=70.28-64=6.28$

$D=9-8=1$

$A={\frac {6.28}{1}}=6.28$

3. Since $D-1=0$, the recurrence relation simplifies to:

$P_{1}={\frac {6.28}{6.28}}=1\implies R_{1}=8+1=9$

$P_{2}={\frac {6.28}{1}}=6.28\implies R_{2}=8.383642374$

Iterating up to $n=5$ yields:

$R_{5}=8.383316766$

Comparing with the actual value ${\sqrt {70.28}}\approx 8.383316766$, the method achieves 9 decimal places of accuracy in just 5 iterations.

== See also ==

• Methods of computing square roots
• Newton's method
• Continued fraction

== References ==

• Iyengar, Nishant; Iyengar, Anju (2024). "A modified method for calculating square roots". Parabola, UNSW Sydney, Vol. 60, Issue 3.

~2026-41315-37 (talk) 06:46, 27 July 2026 (UTC)

Sir I made a mistake defining D. Kindly consider again.

Iyengar's square root method is an iterative numerical technique for approximating the square root of a positive real number using elementary arithmetic operations (addition, multiplication, and division). Proposed by Nishant Iyengar and Anju Iyengar in 2024, it is classified as a "bottom-up" algorithm because it achieves rapid convergence and high precision—comparable to "top-down" techniques like Newton's method—while relying only on middle-school mathematical concepts.

== Background ==

Methods for calculating non-negative square roots are broadly categorized into two types:

• Top-down methods: Algorithms like Newton's method or Taylor series expansions, which utilize advanced calculus and undergraduate-level concepts to compute square roots.
• Bottom-up methods: Pedagogical algorithms that rely solely on basic arithmetic operations taught at the elementary or middle-school level.

While traditional bottom-up methods are often slow to converge or computationally tedious, the Iyengar method provides a rational approximation $R_{n}\approx {\sqrt {a}}$ that converges rapidly with minimal computational overhead.

== Previous Method ==

In a prior paper, the authors proposed a single-step interval-weighted denominator approximation:

1. For a given positive real number $a$, find perfect squares $s^{2}$ and $S^{2}$ such that:

$s^{2}\leq a\leq S^{2}$

2. Define the intermediate terms:

$N=a-s^{2}$

$D=S^{2}-s^{2}$

$A={\frac {N}{D}}$

3. Calculate the single-step rational approximation:

$R=s+{\frac {N}{(D-1)+A}}\approx {\sqrt {a}}$

== The Modified Iterative Method ==

The updated algorithm modifies the third step by introducing an iterative relation for $P_{n}$:

=== Algorithm Steps ===

1. Bound Selection: Find integer or exact values $s$ and $S$ such that $s^{2}\leq a\leq S^{2}$.

2. Compute Intermediate Values:

$N=a-s^{2}$

$D=S^{2}-s^{2}$

$A={\frac {N}{D}}$

3. Iterative Formula: Define $P_{1}$ as:

$P_{1}={\frac {N}{(D-1)+A}}$

For $n\geq 2$, calculate recursively:

$P_{n}={\frac {N}{(D-1)+P_{n-1}}}$

4. Rational Approximation: The $n$-th approximation of the square root is:

$R_{n}=s+P_{n}$

As $n\to \infty$, the sequence converges to the exact value:

$\lim _{n\to \infty }R_{n}={\sqrt {a}}$

== Example ==

To calculate ${\sqrt {70.28}}$:

1. Choose bounding perfect squares $s^{2}=64$ ($s=8$) and $S^{2}=81$ ($S=9$).

2. Calculate terms:

$N=70.28-64=6.28$

$D=81-64=17$

$A={\frac {6.28}{17}}\approx 0.369411765$

$D-1=16$

3. Apply the recurrence relation:

$P_{1}={\frac {6.28}{16+0.369411765}}\approx 0.383642374\implies R_{1}=8+0.383642374=8.383642374$

$P_{2}={\frac {6.28}{16+P_{1}}}\implies R_{2}=8.383286708$

Iterating up to $n=5$ yields:

$R_{5}=8.383316766$

Comparing with the actual value ${\sqrt {70.28}}\approx 8.383316766$, the method achieves 9 decimal places of accuracy in just 5 iterations.

== See also ==

• Methods of computing square roots
• Newton's method
• Continued fraction

== References ==

~2026-41315-37 (talk) 08:33, 27 July 2026 (UTC)

Your method is wrong. It only works in your example because you chose s and S with S-s=1. What you should do is replace D-1 with 2s. Then when you are at the root you get:

${\frac {a-s^{2}}{2s+({\sqrt {a}}-s)}}={\frac {{\sqrt {a}}^{2}-s^{2}}{2s+({\sqrt {a}}-s)}}={\frac {({\sqrt {a}}-s)({\sqrt {a}}+s)}{{\sqrt {a}}+s}}={\sqrt {a}}-s$.

OK? JRSpriggs (talk) 13:51, 27 July 2026 (UTC)

Notice that the convergence is not quadratic even with this correction. JRSpriggs (talk) 15:10, 27 July 2026 (UTC)