from __future__ import division


def sqrt(n, k):
    a, b = 0, n
    mid = n / 2
    sq = mid * mid
    prec = 10 ** -k
    while abs(sq - n) > prec:
        if sq > n:
            b = mid
        else:
            a = mid
        mid = a + (b - a) / 2
        sq = mid * mid
    return mid


def sqrt_newton(n, k):
    if n <= 1:
        return n
    guess = 10
    for _ in xrange(k):
        guess -= ((guess * guess) - n) / (2 * guess)
    return guess


if __name__ == '__main__':
    for i in xrange(101):
        print i, ':', sqrt(i, 10), ', '

    for i in xrange(101):
        print i, ':', sqrt_newton(i, 10), ', '
