CODEWITHSUNDEEP
python
Noctis Skytower
Noctis Skytower

Reputation: 22041

Could someone explain the speed difference between the following functions?

The first function is a naive binary search implementation to find the square root of a number:

def sqrt1(x):
    if x < 0:
        raise ValueError(x)
    if x > 0:
        if x < 1:
            root = 1
            while root ** 2 > x:
                root /= 2
            half = root
            while root ** 2 != x:
                half /= 2
                diff = root + half
                if diff == root:
                    return root
                if diff ** 2 <= x:
                    root = diff
            return root
        if x > 1:
            root = 1
            while root ** 2 < x:
                root *= 2
            half = root / 2
            while root ** 2 != x:
                half /= 2
                diff = root - half
                if diff == root:
                    return root
                if diff ** 2 >= x:
                    root = diff
            return root
        return 1
    return 0

The second function does the same thing but is simpler and about 15 times faster than the first:

def sqrt2(z):
    assert z > 0
    x, y = z, None
    while x != y:
        y = x
        x = (x + z / x) / 2
    return x
  1. Why is sqrt2 so much faster than sqrt1?
  2. Can sqrt1 be made to perform more like sqrt2?

Upvotes: 1

Views: 152

Answers (1)

Dietrich Epp
Dietrich Epp

Reputation: 213847

Binary search

Algorithm 1 does a binary search. So if you're looking for the square root of two, you'll get the following after each iteration:

1.0
1.0
1.25
1.375
1.375
1.40625
1.40625
1.4140625
1.4140625
1.4140625
1.4140625
1.4140625
1.4140625
1.4141845703125
1.4141845703125
1.4141845703125
1.4141998291015625
1.41420745849609375

We've run 17 iterations, and we have 6 correct digits: 1.41421. After another 17 iterations, we'll probably have around 12 correct digits. At the 34th iteration, we get:

1.4142135623260401189327239990234375

The correct digits here are 1.414213562, so only 10 digits.

Newton's method

The second method is Newton's method, which has quadratic convergence. This means that you get twice as many digits for each iteration, so you'll get:

0   2.0
1   1.5
2   1.41666666666666666666666666666666666666666666666666666666667
5   1.41421568627450980392156862745098039215686274509803921568627
12  1.41421356237468991062629557889013491011655962211574404458491
24  1.41421356237309504880168962350253024361498192577619742849829
49  1.41421356237309504880168872420969807856967187537723400156101
60+ 1.41421356237309504880168872420969807856967187537694807317668

The left column shows the number of correct digits -- notice how it grows exponentially. I cut off the output here, because after 7 iterations, the result is correct to the precision I chose. (This was actually run with a higher precision datatype than Python's float, which can't ever give you 60 digits of precision.)

Is it possible to make binary search faster?

No. If you make it faster, it could not possibly be called a binary search any more.

Upvotes: 4

Related Questions