1.1.7 实例：用牛顿法求平方根

上面介绍的函数很像常规的数学函数，它们描述的都是根据一个或几个参数确定一个值。然而，在数学的函数和计算机的函数之间有一个重要的差异，那就是，计算机的函数还必须是有效可行的。

作为实例，现在考虑计算平方根的问题。我们可以把平方根函数定义为：

得到那样的y，能使得y≥0而且y2=x

这句话描述了一个完全合法的数学函数，我们可以根据它去判断某个数是否为另一个数的平方根，或根据它推导出一些有关平方根的一般性事实。然而，在另一方面，这个定义并没有描述计算机函数，因为它确实没有告诉我们，在拿到一个数之后，如何实际地找出这个数的平方根。即使采用类似JavaScript的形式重写一遍这个定义也无济于事：

这只不过是重述了原来的问题。

数学函数与计算机的函数之间的明显对比，不过是描述事物的特征，与描述如何去做出这一事物之间的普遍性差异的一个具体反映。换一种说法，人们有时也把它说成是说明性的知识与行动性的知识之间的差异。在数学里，我们通常关心的是说明性的描述（是什么），而在计算机科学里，人们则通常关心行动性的描述（怎么做）[17]。

怎样才能计算出平方根呢？最常用的就是牛顿的逐步逼近方法。这一方法告诉我们，如果对x的平方根值有了一个猜测y，那么就可以通过执行一个简单操作，得到一个更好的猜测（它更接近实际平方根的值）：只需要求出y和x/y的平均值[18]。例如，我们可以用这种方式计算2的平方根，假定初始值是1：

继续这一计算过程，我们就能得到2的平方根的越来越好的近似值。

现在，让我们用函数的语言来描述这一计算过程。开始时，我们有被开方的数值（要做的就是计算它的平方根）和一个猜测值。如果猜测值对我们的用途而言已经足够好，工作就完成了。如若不然，就需要重复上述计算过程去改进这个猜测值。我们可以把这一基本策略写成下面的函数：

改进猜测值的方法，就是求出它与被开方数除以这个旧猜测的平均值：

其中

我们还必须说明什么是“足够好”。下面的做法只是为了说明问题，它实际上并不是一个很好的检测方法（参看练习1.7）。这里的想法是，不断改进答案直至它足够接近平方根，使其平方与被开方数之差小于某个事先确定的误差值（这里用的是0.001）[19]：

最后，还需要一种方法启动整个工作。例如，对任何数，我们都可以猜其平方根为1：

如果把这些声明都送给解释器，我们就可以像使用其他函数一样使用sqrt了：

这个sqrt程序也说明，至今已经介绍的这个简单的函数式语言，已经足以写出可以用其他语言（例如C或Pascal）写出的任何纯粹数值计算的程序了。这件事看起来可能很让人吃惊，因为在我们的语言里甚至没有包括任何迭代结构（循环，它们可用于指挥计算机去一遍遍地做某些事情）。而在另一方面，sqrt_iter展示了如何不用特殊的迭代结构来实现迭代，其中只需要使用常规的函数调用能力[20]。

练习1.6 Alyssa P.Hacker不喜欢条件表达式的语法，因为其中涉及符号?和:。她问：“为什么我不能直接声明一个常规的条件函数，其应用的工作方式就像条件表达式呢？”[21]Alyssa的朋友Eva Lu Ator断言确实可以这样做，并声明了一个名为conditional的函数：

Eva给Alyssa演示了她的程序：

她很高兴地用自己的conditional函数重写了求平方根的程序：

当Alyssa试着用这个函数去计算平方根时会发生什么情况？请给出解释。

练习1.7 在计算很小的数的平方根时，用is_good_enough检测不是很有效。还有，在实际计算机里，算术运算总以一定的有限精度进行。这会使我们的检测不适合用于对很大的数的计算。请解释上述论断，并用例子说明对很小的和很大的数，这种检测都可能失效。实现is_good_enough的另一策略是监视猜测值在一次迭代中的变化情况，当变化的值相对于猜测值之比很小时就结束。请设计一个采用这种终止测试方式的平方根函数。对很大的和很小的数，这一策略都能工作得更好吗？

练习1.8 求立方根的牛顿法基于如下事实，如果y是x的立方根的一个近似值，那么下式能给出一个更好的近似值：

请利用这个公式，实现一个类似平方根函数的求立方根的函数。（在1.3.4节，我们将看到如何实现一般的牛顿法，它是这里的求平方根和立方根函数的抽象。）