NR方法求平方根

squarerootbi.py

# _*_coding:utf-8_*_
#!/usr/bin/env python

# define a function which can compute the squareroot of the number

def squarerootbi(number, epsilon):
    """
    利用二分法计算给定数字和精度的近似平方根
    :rtype: float
    :param number:给定的数字
    :param epsilon:要求的平方根的精确度
    :return:返回给定数字和精度的平方根
    """
    assert number > 0, 'number must > 0' + str(number)
    assert epsilon > 0, 'epsilon must > 0' + str(epsilon)

    # high = number 假设给定数的平方根在0-数字本身之间,然而小数并不是这样
    high = max(number, 1)
    low = 0
    count = 0
    guess = (high + low) / 2.0

    while (abs(guess ** 2 - number) > epsilon) and count <= 100:
        if guess ** 2 > number:
            high = guess
        elif guess ** 2 < number:
            low = guess
        guess = (high + low) / 2.0
        count += 1

    assert count <= 100, 'iter up to 100 the counter is:' + str(count)

    print 'the squareroot of this number is: ' + str(guess) + '       ' + 'count:' + str(count)

    return count


def sqrtnr(number, epsilon):
    """
    根据给定的>0的数字和要求的精确度,返回平方根计算的迭代次数
    :param number: 必须大于0
    :param epsilon: 平方根与近似平方根的差值
    :return: 计算平方根所使用的迭代次数
    """
    assert number > 0, 'number must > 0' + str(number)
    assert epsilon > 0, 'epsilon must > 0' + str(epsilon)

    # 用NR方法求平方根
    number = float(number)
    guess = 0.001
    count = 0
    diff = guess ** 2 - number

    while abs(guess ** 2 - number) > epsilon and count <= 100:
        # 使用NR方法计算平方根 guess(next)=guess(pre) - f(guess) / f'(guess)
        # f(x): guess**2 - x = 0
        # f'(x)是f(x)的导数
        # NR方法参见https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95
        # 学好数学很重要啊
        # 不如不写diff,反正这里只用到一次diff,不过如果修改程序的话可能就比较重要了
        guess -= diff / (2.0 * guess)
        diff = guess ** 2 - number
        
        count += 1

    print 'the sqrt of number is:' + str(guess) + ' '*5 + 'count:' + str(count)

    return count



def testsuqarerootbi():
    squarerootbi(9, 0.00000000001)
    # squarerootbi(-1, 0.001)
    # squarerootbi(1, -0.1)
    squarerootbi(9, 0.00000001)
    squarerootbi(0.25, 0.0000001)

    print '-' * 10
    sqrtnr(2, 0.00001)
    squarerootbi(2, 0.00001)

    print '---compare---'
    a =sqrtnr(2, 0.01)
    b = squarerootbi(2, 0.01)
    print '迭代次数差值:', a - b

    print '--0.001---'
    c = sqrtnr(2, 0.001)
    d = squarerootbi(2, 0.001)
    print '迭代次数差值:', c - d

    print '---0.00001---'
    e = sqrtnr(5555555, 0.0000001)
    f = squarerootbi(5555555, 0.0000001)
    print '迭代次数差值:', e - f


testsuqarerootbi()

# 使用函数来测试,而不是每次都调用测试对象,可以减少重复