首页 > 代码库 > 计算机科学及编程导论(5)浮点数和二分法
计算机科学及编程导论(5)浮点数和二分法
1. Python的数字类型
Python的数字类型分为两类:整型(int)以及浮点型(float)。
对于Python来说,整型可以取无限大。
Python的整型可以取任意精度
例如,可以输入2**1000次方,仍然会返回正确结果。
Python的浮点类型按照IEE754标准,对于64位的计算机而言,表示成如下方式
1位:符号位
11位:指数位
52位:尾数位
这样总共可以表示17位长的精度,如果超过17位,Python就无法处理,比如 0.1**1000次方.
在教学视频中,如果输入 x = 0.1,那么最终打印的值则是0.10000000000000001。原因很简单,因计算机处理数字的方式是二进制,而0.1的二进制则是0.0001100110011...,这样转换过程中就会出现误差(新版的python可能对结果进行了处理再显示,所以显示出来仍为0.1)。比如下面程序对s进行累加,每次累加0.1
s = 0.1
for i in range(100):
s += 0.1 #=>10.09999999999998
由于误差的积累,最后一位变成了8.
误差的存在,使得浮点型在进行 == 判断的操作时,经常出现违背直觉的结果:
import math
a = math.sqrt(2)
a*a == 2 #=>False
所以,对于浮点型来说,我们不需要去判断结果是否相等,而是要判断结果是否小于某个允许的误差值:
abs(a*a - 2.0) < 某个极小的正数
2. 用二分法求平方根
之前已经学习过求X的平方根,不过X被假定为开平方后为整数,所以就可以从0开始进行枚举。现在,考虑更为一般的形式,X开方后不一定为确定的数,由于在实数范围内无法进行一一的枚举,所以要采用其他方法来求解。
基本的解题思路是逐次逼近法,即每一次让结果逼近正确答案一点,也就是说,采取猜想-》检查-》改进的过程:
guess = initial guess
迭代100次:
如果 f(guess)接近正确答案:返回guess
否则:令 guess = better guess
如果无返回值,则报错
而要判断f(guess)是否接近正确答案很简单,只需要进行验证即可:abs(guess**2 -x) < 某个极小的正数
#二分法求平方根
#epsilon:极小的正数 ctr:迭代次数
def squareRootBi1(x,epsilon):
assert epsilon > 0,‘epsilon must be postive,not‘ + str(epsilon)
low = 0
high = x
guess = (low + high)/2.0
ctr = 1
while abs(guess**2 -x) > epsilon and ctr <= 100:
if guess**2 < x:
low = guess
else:
high = guess
guess = (low +high)/2.0
ctr += 1
assert ctr <= 100,‘Iteration count exceeded‘
print(‘Bi method.Num.iterations:‘,ctr,‘Estimate:‘,guess)
return guess
assert语句相当于将调试的断点插入到程序中,比如,如果输入的epsilon的值为-1,则会显示如下错误:
File "/Users/ihuangmx/程序/Python/Untitled.py", line 2, in squareRootBi
assert epsilon > 0,‘epsilon must be postive,not‘ + str(epsilon)
AssertionError: epsilon must be postive,not-1
上面的程序还存在Bug,下一讲会进行完善。