Iterative Methods for Computing the Square Roots

Computing the Square Root using the Bisection Method

Explanation, Python Implementation and Numerical Analysis

The simplest iterative methods to approximate the square root of a positive number S ∈ ℝ⁺ is the Bisection Method. This is an exhaustive enumeration a.k.a. brute-force search technique which bisects the interval presumed to contain the true value α = √S, refining the guess at every iteration, unil the predefined stopping criterion is met.

[…] we are using exhaustive enumeration. Notice that this method for finding the square root has nothing in common with the way of finding square roots using a pencil that you might have learned in middle school. It is often the case that the best way to solve a problem with a computer is quite different from how one would approach the problem by hand. (Guttag 2016, p. 31)

Also in this series:

• Computing the Square Root using the Babylonian / Heron’s Method
• Computing the Square Root using Halley’s Method

Table of Contents

• How does it work?
• Does it converge?
• Python implementation
• Analysis
• Conclusion
• Download
• Appendix: Multiprecision

How does it work?

The bisection search algorithm starts by choosing the lower and upper boundaries of the interval where the true value α = √S must lie in. We will call these variables low and high. The choice of these boundaries is very different from how we would choose the nearest square numbers by hand. In computational methods, we select the simplest boundaries as follows:

• low = 0
• high = max(1, S)

Setting the high variable in this way caters for fractional values 0 < S < 1, avoiding the algorithm going down the rabbit hole.

The inital guess will be the midpoint of this interval i.e.,

• x[0] = (low + high) / 2, dividing the initial interval in half.

Visual demonstration of how the bisection search works.

Exhaustive enumreation is a search technique that works only if the set of values being searched includes the answer. (Guttag 2016, p. 31)

The refinement of our guess at each step consists of the following decision:

• Is our guess squared less than the input number i.e., x[n]² < S?
• If yes, then the guess is too low. Thus, we set low to the current guess: low = x[n].
• If no, then the guess is too high. So, we set high to the current guess high = x[n].
• We update the next guess with the new low and high values i.e., x[n+1] = (low + high) / 2, again dividing the search interval in half.

The first five iterations of the Bisection Method for approximating √2.

When do we reach a ‘good-enough’ approximation?

That depends on the threshold value tau for the approximation errors abs(x[n] - x[n-1]) and abs(x[n]² - S). Therefore, we loop until either condition is met:

• abs(x[n]² - S) < tau
• or abs(x[n] - x[n-1]) < tau.

Since most modern computers work with 64-bit double precision, we should not set the threshold lower than 1e-15 i.e, 15 decimal places (d.p.). For consistency, I have chosen 12 d.p. i.e., tau = 10^(-12) in all tests.

How long is a piece of string? (Anonymous)

Back to the top.

Does it converge?

Yes, the bisection search is linearly convergent. The convergence error term eₙ = |xₙ — α| that is, the distance of our approximation xₙ from the true value α = √S, depends on the previous error term in a linear fashion:

• eₙ₊₁ ≤ ½ eₙ
• Intuitively, the next error term must be less than or equal to half of the previous error term since we bisect the search interval at each step.
• Notice that the order of the previous error is 1 i.e., eₙ = (eₙ)¹, called the order of convergence, usually notated with a ‘q’. The order q = 1 is what makes the Bisection method converge linearly.
• The coefficient of ⅟₂ is called the rate of convergence, usually notated with a ‘μ’. For linearly convergent sequence, the rate μ ∈ (0, 1).

A sequence of real numbers (xₙ) is said to converge to x ∈ ℝ (and we write lim_{n → ∞} xₙ = x) if, for any ε > 0, there exists an integer N ∈ ℕ such that, for all n > N, |xₙ — x| < ε. (Chongchitnan 2026, p. 10)

Proof of Linear Convergence

We use one of the fundamental theorems of calculus, the Intermediate Value Theorem (IVT) which basically states that for a continuous function on a closed interval [a, b], we do not skip any values between its endpoints.

Need for Speed

What does linear convergence mean in terms of the ‘speed’ of approaching the limit that is, the true value α? Computationally, we say the Bisection method is ‘very slow’ compared to other methods depicted below.

Approximation of √3 with different iterative methods.

That is, it takes a lot more iterations for the error term to get below the threshold value compared to the Babylonian or Halley’s methods.

Zoomed in the approximation of √3.

To quantify the number of iterations n in terms of the desired precision d i.e., the number of decimal places, the estimated number of iterations to achieve that precision is:

• n ≥ -(d + log₁₀(e₀)) / log₁₀(μ)
• where μ is the rate of convergence and e₀ is the initial error |x₀ - α|.

Derivation of the estimated number of iterations:

Nota Bene: this estimation applies when the guess is very close to the true value of the square root of S.

Get Aurel Nicolae’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Example for S = 2 with 12 dp and rate μ = ½:

In [1]: import math

In [2]: S = 2

In [3]: d = 12

In [4]: x0 = (0 + max(1, S)) / 2

In [5]: e0 = abs(x0 - math.sqrt(S))

In [6]: mu = 1 / 2

In [7]: n = -1 * (d + math.log10(e0)) / math.log10(mu)

In [8]: print(n)
38.591583835484734

In [9]: print(math.ceil(n))
39

This means that it takes roughly 39 iterations for the approximation error of √2 to get below τ = 1e-12.

Decimal Precision

How does the decimal precision improve with each iteration? The number of precision improves by log₁₀(2) ≈ 0.30103 < ⅓ d.p. when our guess xₙ is very close to the true value α. We have to wait at least 3 iterations to get 1 d.p. accuracy.

This is exactly what the derived formula dₙ₊₁ ≈ dₙ + log₁₀(2) tells us. We only gain roughly a third of a decimal place precision for each iteration.

Another way to think of decimal represent in 64-bit double precision is that the denary number 0.1 ≈ 2⁻³·³²² i.e., to gain 1 decimal place of precision, it takes 3.322 binary digits aka bits.

We can see that to get to a precision of 12 d.p. we need 39.863 binary digits or approximately 40 bits. Coincidentally, the 40 bits is not too far from the 39 estimated iterations that we calculated above.

These two numbers are so close for √2 because the initial guess is fairly near to the true value. As the number increases, so does the error interval and the number of guess increase.

Back to the top.

Python implementation

My code is based on the root finding algrithm written by Guttag 2016, p. 33, with my own tweaks and enhancements.

Disclaimer: My implementation might not be the best and most efficient. I encourage you to rewrite it in your own way.

Back to the top.

Analysis

I ran tests using the bisection method for various numbers with the same threshold 1e-12 or 12 d.p. and the following is a summary of my tests:

╭─────────────────────────────────┬───────────────────────────────────┬──────────────────┬─────────────────────╮
│                          Number │                     Approximation │   Actual Guesses │   Estimated Guesses │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                               1 │                0.9999999999990905 │               39 │                  39 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                               2 │                1.4142135623733338 │               38 │                  39 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                               3 │                1.7320508075686121 │               40 │                  38 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                               4 │                2.0000000000000000 │                0 │                   0 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                               5 │                2.2360679774999426 │               41 │                  38 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                               7 │                2.6457513110646005 │               42 │                  40 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                               8 │                2.8284271247457582 │               42 │                  41 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                               9 │                2.9999999999998295 │               43 │                  41 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                              10 │                3.1622776601682290 │               42 │                  41 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                              25 │                5.0000000000004263 │               44 │                  43 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                              37 │                6.0827625302978419 │               45 │                  44 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                              49 │                7.0000000000004974 │               45 │                  44 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                              73 │                8.5440037453171911 │               46 │                  45 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                              81 │                8.9999999999996803 │               46 │                  45 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                             100 │               10.0000000000001421 │               46 │                  46 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                             121 │               10.9999999999994529 │               46 │                  46 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                            1000 │               31.6227766016838885 │               49 │                  49 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                           10000 │               99.9999999999995310 │               53 │                  53 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                          100000 │              316.2277660168375633 │               56 │                  56 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                          987654 │              993.8078285060951202 │               59 │                  59 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│                       987543201 │            31425.2000948283530306 │               69 │                  69 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│  673003460632639326586069439443 │  820367881278051.5000000000000000 │              103 │                 138 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│ 1000000000000000000000000000000 │ 1000000000000000.0000000000000000 │              101 │                 139 │
├─────────────────────────────────┼───────────────────────────────────┼──────────────────┼─────────────────────┤
│ 1367999732000000000000000000071 │ 1169615206809487.5000000000000000 │              103 │                 139 │
╰─────────────────────────────────┴───────────────────────────────────┴──────────────────┴─────────────────────╯

As we can see from the summary table above, most of the estimated number of guesses in the far right column are quite close to the actual number of iterations.

The exception for the bisection method is the 4 which happens to be a perfect square i.e., 2² = 4 and the midpoint of the inital interval of [0, 4] is the square root 2.

When we take the square root of really large numbers in the region of 10³⁰, then we overestimate the number of iterations. This is because the initial error term e₀ = |x₀ — α| is quite huge.

Let’s run an example to see how the search intervals are bisected:

(.venv) C:\Users\...\Math_Square_Root>python c1bisection\bisect_sqrt.py
Enter positive number: 2
Enter precision between 0 and 15 (Default 15 d.p.): 12
iteration: 0    low: 0  high: 2.0       guess: 1.0      guess²: 1.0
iteration: 1    low: 1.0        high: 2.0       guess: 1.5      guess²: 2.25
iteration: 2    low: 1.0        high: 1.5       guess: 1.25     guess²: 1.5625
iteration: 3    low: 1.25       high: 1.5       guess: 1.375    guess²: 1.890625
iteration: 4    low: 1.375      high: 1.5       guess: 1.4375   guess²: 2.06640625
iteration: 5    low: 1.375      high: 1.4375    guess: 1.40625  guess²: 1.9775390625
iteration: 6    low: 1.40625    high: 1.4375    guess: 1.421875 guess²: 2.021728515625
iteration: 7    low: 1.40625    high: 1.421875  guess: 1.4140625        guess²: 1.99957275390625
iteration: 8    low: 1.4140625  high: 1.421875  guess: 1.41796875       guess²: 2.0106353759765625
iteration: 9    low: 1.4140625  high: 1.41796875        guess: 1.416015625      guess²: 2.0051002502441406
iteration: 10   low: 1.4140625  high: 1.416015625       guess: 1.4150390625     guess²: 2.002335548400879
iteration: 11   low: 1.4140625  high: 1.4150390625      guess: 1.41455078125    guess²: 2.0009539127349854
iteration: 12   low: 1.4140625  high: 1.41455078125     guess: 1.414306640625   guess²: 2.000263273715973
iteration: 13   low: 1.4140625  high: 1.414306640625    guess: 1.4141845703125  guess²: 1.9999179989099503
iteration: 14   low: 1.4141845703125    high: 1.414306640625    guess: 1.41424560546875 guess²: 2.0000906325876713
iteration: 15   low: 1.4141845703125    high: 1.41424560546875  guess: 1.414215087890625        guess²: 2.000004314817488
iteration: 16   low: 1.4141845703125    high: 1.414215087890625 guess: 1.4141998291015625       guess²: 1.9999611566308886
iteration: 17   low: 1.4141998291015625 high: 1.414215087890625 guess: 1.4142074584960938       guess²: 1.9999827356659807
iteration: 18   low: 1.4142074584960938 high: 1.414215087890625 guess: 1.4142112731933594       guess²: 1.9999935252271825
iteration: 19   low: 1.4142112731933594 high: 1.414215087890625 guess: 1.4142131805419922       guess²: 1.9999989200186974
iteration: 20   low: 1.4142131805419922 high: 1.414215087890625 guess: 1.4142141342163086       guess²: 2.0000016174171833
iteration: 21   low: 1.4142131805419922 high: 1.4142141342163086        guess: 1.4142136573791504       guess²: 2.000000268717713
iteration: 22   low: 1.4142131805419922 high: 1.4142136573791504        guess: 1.4142134189605713       guess²: 1.9999995943681483
iteration: 23   low: 1.4142134189605713 high: 1.4142136573791504        guess: 1.4142135381698608       guess²: 1.9999999315429164
iteration: 24   low: 1.4142135381698608 high: 1.4142136573791504        guess: 1.4142135977745056       guess²: 2.000000100130311
iteration: 25   low: 1.4142135381698608 high: 1.4142135977745056        guess: 1.4142135679721832       guess²: 2.000000015836613
iteration: 26   low: 1.4142135381698608 high: 1.4142135679721832        guess: 1.414213553071022        guess²: 1.9999999736897645
iteration: 27   low: 1.414213553071022  high: 1.4142135679721832        guess: 1.4142135605216026       guess²: 1.9999999947631886
iteration: 28   low: 1.4142135605216026 high: 1.4142135679721832        guess: 1.414213564246893        guess²: 2.000000005299901
iteration: 29   low: 1.4142135605216026 high: 1.414213564246893 guess: 1.4142135623842478       guess²: 2.0000000000315445
iteration: 30   low: 1.4142135605216026 high: 1.4142135623842478        guess: 1.4142135614529252       guess²: 1.9999999973973666
iteration: 31   low: 1.4142135614529252 high: 1.4142135623842478        guess: 1.4142135619185865       guess²: 1.9999999987144557
iteration: 32   low: 1.4142135619185865 high: 1.4142135623842478        guess: 1.4142135621514171       guess²: 1.9999999993730002
iteration: 33   low: 1.4142135621514171 high: 1.4142135623842478        guess: 1.4142135622678325       guess²: 1.9999999997022724
iteration: 34   low: 1.4142135622678325 high: 1.4142135623842478        guess: 1.4142135623260401       guess²: 1.9999999998669085
iteration: 35   low: 1.4142135623260401 high: 1.4142135623842478        guess: 1.414213562355144        guess²: 1.9999999999492266
iteration: 36   low: 1.414213562355144  high: 1.4142135623842478        guess: 1.4142135623696959       guess²: 1.9999999999903857
iteration: 37   low: 1.4142135623696959 high: 1.4142135623842478        guess: 1.4142135623769718       guess²: 2.000000000010965
Number of guesses: 38, Threshold: 1e-12, Estimate iterations: 39.

Approximation for the square root of 2.0 is: 1.4142135623733338

Compared to math.sqrt(2.0): 1.4142135623730951

Back to the top.

Conclusion

The Bisection method is very slow compared to the Babylonian (Heron’s) method and Halley’s method. This is because these techniques converge quadratically and cubically i.e., polynomially faster than a linear technique. Thus, computational software does not use the bisection search for calculating square roots.

The benefits of learning the Bisection method are that it is a simple method to understand and straight forward to code. The bisection search also offers the building blocks for how numerical techniques are designed and analysed. In a nutshell, it is a good technique to learn if you are new to iterative methods.

Back to the top.

Download

• Here is the link to my GitHub repo.

Back to the top.

Appendix: Multiprecision

Here is my multiple precision implementation of the Bisection method using the mpmath library accompanied by my disclaimer that there are probably better and more efficient implementations out there.

Nevertheless, this python library is brilliant! Try it out!

Also in this series:

• Computing the Square Root using the Babylonian / Heron’s Method
• Computing the Square Root using Halley’s Method

Back to the top.