Example4.4

「Example4.4」の編集履歴（バックアップ）一覧に戻る

Example4.4 - (2011/02/24 (木) 08:31:17) のソース

#co(){
4.4 Example: Square Roots by Newton's Method 

We now illustrate the language elements introduced so far in the construction of a more interesting program. The task is to write a function 
}


#setmenu2(ex-r-menu)
** 4.4 例 : ニュートン法による平方根計算

ここまでに紹介した構文を、もう少し興味深いプログラムを組み立てて、示しましょう。課題は x の平方根を計算する関数

 def sqrt(x: Double): Double = ... 

#co(){
which computes the square root of x.
}
を書くことです。

#co(){
A common way to compute square roots is by Newton's method of successive approximations. One starts with an initial guess y (say: y = 1). One then repeatedly improves the current guess y by taking the average of y and x/y. As an example, the next three columns indicate the guess y, the quotient x/y, and their average for the first approximations of √2.
}

平方根を計算する一般的な方法は、近似を繰り返すニュートン法です。まず初期推定値 y (たとえば y=1) から始めます。次いで現在の推定値 y を、y と  x/y の平均値を取って繰り返し改良します。次の例では √2 を近似する、推定値 y、商 x/y、その平均が３列に示されています。

 1              2/1 = 2                      1.5 
 1.5           2/1.5 = 1.3333         1.4167 
 1.4167     2/1.4167 = 1.4118    1.4142 
 1.4142     ...                               ... 
 y              x / y                            ( y + x / y )/2 
 
#co(){
One can implement this algorithm in Scala by a set of small functions, which each represent one of the elements of the algorithm. 

We first define a function for iterating from a guess to the result:
}
Scala では、このアルゴリズムを小さな関数群によって実装でき、各関数がアルゴリズムの各要素を表すようにできます。

はじめに、推定値から結果を得ることを繰り返す関数を定義します。

 def sqrtIter(guess: Double, x: Double): Double = 
   if (isGoodEnough(guess, x)) guess 
   else sqrtIter(improve(guess, x), x)

#co(){
Note that sqrtIter calls itself recursively. Loops in imperative programs can always be modeled by recursion in functional programs. 

Note also that the definition of sqrtIter contains a return type, which follows the parameter section. Such return types are mandatory for recursive functions. For a non-recursive function, the return type is optional; if it is missing the type checker will compute it from the type of the function's right-hand side. However, even for non-recursive functions it is often a good idea to include a return type for better documentation. 
}

sqrtIter は自分自身を再帰的に呼び出します。命令型プログラムのループは常に、関数型プログラムでは再帰でモデル化できます。

sqrtIter の定義には、パラメータ部に続いて戻り値型があることに注意して下さい。このような戻り値型は再帰関数では必須です。非再帰関数では戻り値型はオプションであり、もしそれがなければ、型チェッカーが関数の右辺から計算します。しかし非再帰関数であっても、よりよい文書化のために戻り値型を書いておくことは、しばしばよい考えです。

#co(){
As a second step, we define the two functions called by sqrtIter: a function to improve the guess and a termination test isGoodEnough. Here is their definition. 
}

二つ目のステップとして、sqrtIter から呼ばれる２つの関数を定義します。推定値を改良する関数 improve と、終了テスト isGoodEnough です。定義は次ようになります。

 def improve(guess: Double, x: Double) = 
   (guess + x / guess) / 2 
 
 def isGoodEnough(guess: Double, x: Double) = 
   abs(square(guess) - x) < 0.001 

#co(){
Finally, the sqrt function itself is defined by an application of sqrtIter. }

最後に、sqrt 関数自身を sqrtIter の適用として定義します。

 def sqrt(x: Double) = sqrtIter(1.0, x) 

#co(){
Exercise 4.4.1 The isGoodEnough test is not very precise for small numbers and might lead to non-termination for very large ones (why?). Design a different version of isGoodEnough which does not have these problems. 

Exercise 4.4.2 Trace the execution of the sqrt(4) expression. 

}

&b(){演習 4.4.1　} isGoodEnough の判定は小さな数に対してはあまり正確ではなく、大きな数に対しては終了しないかもしれません (何故でしょう？)。これらの問題のない別の isGoodEnough を設計しなさい。

&b(){演習 4.4.2　} 式 sqrt(4) の実行をトレースしなさい。

#center(){[[前ページ>Example4.3]]　[[ 4 章>ExampleChap4]]　[[目次>ScalaByExample和訳]]　[[次ページ>Example4.5]]}

----
#comment