首页 > 代码库 > 计算机科学及编程导论(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,下一讲会进行完善。