1.1.7 Example: Square Roots by Newton’s Method

Procedures, as introduced above, are much like ordinary mathematical functions.

They specify a value that is determined by one or more parameters. But there

is an important difference between mathematical functions and computer

procedures. Procedures must be effective.

如前所述，过程与普通的数学函数颇为相似，都是通过一个或多个参数来确定一个值。但数学函数与计算机过程之间存在一个重要区别：过程必须是能行的 (effective)。

As a case in point, consider the problem of computing square roots. We can

define the square-root function as

以计算平方根为例，我们可以将平方根函数定义为：

x

=

the

满足以下条件的

y

such that

使得

y
≥
0

and

且

y
2

=
x
.
=
x
。

This describes a perfectly legitimate mathematical function. We could use it

to recognize whether one number is the square root of another, or to derive

facts about square roots in general. On the other hand, the definition does

not describe a procedure. Indeed, it tells us almost nothing about how to

actually find the square root of a given number. It will not help matters to

rephrase this definition in pseudo-Lisp:

这描述的是一个完全合法的数学函数。我们可以用它来判断一个数是否为另一个数的平方根，或者推导有关平方根的一般性事实。然而，该定义并不描述一个过程——它几乎没有告诉我们如何实际求出某个给定数的平方根。将这一定义改写成伪 Lisp 形式也无济于事：

This only begs the question.

这不过是在回避问题。

The contrast between function and procedure is a reflection of the general

distinction between describing properties of things and describing how to do

things, or, as it is sometimes referred to, the distinction between declarative

knowledge and imperative knowledge. In mathematics we are usually concerned

with declarative (what is) descriptions, whereas in computer science we are

usually concerned with imperative (how to) descriptions.

函数与过程之间的对比，折射出一个更普遍的区分：描述事物的性质与描述如何去做事，也即陈述性知识 (declarative knowledge) 与命令性知识 (imperative knowledge) 之别。数学通常关注的是陈述性的（"是什么"）描述，而计算机科学通常关注的是命令性的（"如何做"）描述。

How does one compute square roots? The most common way is to use Newton’s

method of successive approximations, which says that whenever we have a guess

y for the value of the square root of a number x, we can perform a

simple manipulation to get a better guess (one closer to the actual square

root) by averaging y with x

如何计算平方根？最常用的方法是牛顿逐步逼近法 (Newton's method of successive approximations)：只要我们对某个数 x 的平方根有一个猜测值 y，就可以通过一个简单的操作得到一个更好的猜测值（一个更接近真实平方根的值）——将 y 与 x

/

y.

For example, we can compute the square root of 2 as follows.

Suppose our initial guess is 1:

y 求平均值。例如，我们可以按如下方式计算 2 的平方根。假设初始猜测值为 1：

Continuing this process, we obtain better and better approximations to the

square root.

不断重复这一过程，我们就能得到越来越精确的平方根近似值。

Now let’s formalize the process in terms of procedures. We start with a value

for the radicand (the number whose square root we are trying to compute) and a

value for the guess. If the guess is good enough for our purposes, we are

done; if not, we must repeat the process with an improved guess. We write this

basic strategy as a procedure:

现在我们用过程来形式化这一计算过程。我们从被开方数（即我们要求其平方根的那个数）的值和一个猜测值出发。如果猜测值对我们的目的已经足够精确，计算就此结束；否则，必须用改进后的猜测值重复整个计算过程。我们将这一基本策略写成一个过程：

A guess is improved by averaging it with the quotient of the radicand and the

old guess:

猜测值的改进方式是：用被开方数除以旧猜测值，再将所得商与旧猜测值求平均：

where

其中

We also have to say what we mean by “good enough.” The following will do for

illustration, but it is not really a very good test. (See Exercise 1.7.)

The idea is to improve the answer until it is close

enough so that its square differs from the radicand by less than a

predetermined tolerance (here 0.001):

我们还需要说明"足够好"的含义。下面的定义可用于说明，但并不是一个很好的判断标准。（见练习 1.7。）其基本思路是：不断改进答案，直到其平方与被开方数之差小于某个预先给定的容差（此处为 0.001）：

Finally, we need a way to get started. For instance, we can always guess that

the square root of any number is 1:

最后，我们需要给出一个起点。例如，我们总可以将任意数的平方根猜测值初始化为 1：

If we type these definitions to the interpreter, we can use sqrt just as

we can use any procedure:

将这些定义输入解释器后，我们就可以像使用任何其他过程一样使用 sqrt：

The sqrt program also illustrates that the simple procedural language we

have introduced so far is sufficient for writing any purely numerical program

that one could write in, say, C or Pascal. This might seem surprising, since

we have not included in our language any iterative (looping) constructs that

direct the computer to do something over and over again. Sqrt-iter, on

the other hand, demonstrates how iteration can be accomplished using no special

construct other than the ordinary ability to call a procedure.

sqrt 程序也说明了，我们迄今为止引入的这一简单过程式语言，已足以编写任何纯数值程序，就如同用 C 或 Pascal 所能编写的一样。这或许令人惊讶，因为我们的语言中并未引入任何指示计算机反复执行某项操作的迭代（循环）构造。而 sqrt-iter 恰恰展示了：只凭借普通的调用过程的能力，无需任何特殊构造，迭代同样可以实现。