计算机科学及编程导论(麻省理工)

Lecture 5: Floating point numbers, successive refinement, finding roots.

本课前半节基本介绍了浮点数和运用浮点数的一些注意点。后半节介绍了计算机常用的逐次逼近法和最经典的二分法。

浮点数(Floating numbers)也可以理解为数学中的实数(Real numbers)，但是在计算机浮点数运算中时常无法算出精确值。这是由于计算机使用了二进制数进行运算。

在使用浮点数进行运算时，需注意以下几点：

• 浮点数只能取到小数点后17位
• 由于浮点数运算结果为近似值，多次运算会导致误差的累计，从而使结果非常不精确
• 不可以用“==”判断浮点数，因为它们是不精确的，所以只能判断他们与理想数的误差。
• 例如：abs(a**2 - 2.0) < 0.0001 这就算出了根号2的近似值

（注意：在浮点数问题中，我们无法使用穷举法，因为浮点数的数量是无限的）

本课后半节介绍了计算机中非常有效和常用的方法，即逐次逼近法(Successive approximation method)。其基本程序结构如下：

    guess = initial guess

    for iter in range(ctr):

        if f(guess) close enough:

             return the guess

        else:

             guess =  a better guess

（注意：其中ctr是用于限制循环次数的控制变量，其用处是避免程序出现死循环）

另外，二分法(Bi-section method)是逐次逼近法中最经典的一种，它每次运算都可以使计算量减少一半，从而大大提高计算速度。

本课中举了一个开平方的例子，程序如下：

def sqrt(x, 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

    return guess

（注意：这个程序是有bug的，在Lecture 6一开始的时候会提到，当然这里也可以思考一下）

总结：本课最主要的是介绍逐次逼近法，并没有其他特别重要的东西。