In [1]:
import math
math.sqrt(2)
Out[1]:
1.4142135623730951
In [2]:
x, delta = 200, 1
y = 0
while (y + delta) ** 2 <= x:
    y = y + delta
y
Out[2]:
14
In [3]:
x, delta = 2, 0.00001
low, high = 0, max(1, x)
while high - low > delta:
    mid = (low + high) / 2
    if mid ** 2 > x:
        high = mid
    else:
        low = mid
mid
Out[3]:
1.4142074584960938
In [4]:
def sqrt_linear(x, delta):
    y = 0
    while (y + delta) ** 2 <= x:
        y = y + delta
    return y
In [5]:
def sqrt_binary(x, delta):
    low, high = 0, max(1, x)
    while high - low > delta:
        mid = (low + high) / 2
        if mid ** 2 > x:
            high = mid
        else:
            low = mid
    return mid
In [6]:
%time sqrt_linear(2, 0.1 ** 6)
CPU times: user 343 ms, sys: 3.93 ms, total: 347 ms
Wall time: 348 ms
Out[6]:
1.4142129999738422
In [7]:
%time sqrt_binary(2, 0.1 ** 6)
CPU times: user 15 µs, sys: 1 µs, total: 16 µs
Wall time: 18.1 µs
Out[7]:
1.4142141342163086
In [8]:
%timeit sqrt_binary(2, 0.1 ** 6)
100000 loops, best of 3: 7.46 µs per loop