Created
December 5, 2015 11:30
-
-
Save dispensable/d2dfed87cb4243584dd1 to your computer and use it in GitHub Desktop.
NR方法求平方根
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# _*_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() | |
# 使用函数来测试,而不是每次都调用测试对象,可以减少重复 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment