exercise 1.6
平方根を求めるアルゴリズム sqrt-root.
ビルトイン関数に含まれているのだけど、アルゴリズムの演習って事で、
再実装してみる。
まずは、Schemeで。
(define (sqrt n) (define (abs n) (if (< n 0) (-n) n)) (define (sqare n) (* n n)) (define (average a b) (/ (+ a b) 2)) (define (improve guess n) (average guess (/ n guess))) (define (good-enough? guess n) (< (abs (- (square guess) n)) 0.001)) (define sqrt-iter (guess n) (if (good-enough? guess n) guess (sqrt-iter (improve guess n) n))) (sqrt-iter 1.0 n))
続いて OCaml
let sqrt n =
let abs n = if n < 0 then (-.n) else n and
square n = n *. n and
average a b = (a +. b) /. 2.0 and
improve guess n = average guess (n /. guess) and
good_enough guess n = abs((square guess) -. n) < 0.001 in
let rec sqrt_iter guess n =
if good_enough guess n then
guess
else
sqrt_iter (improve guess n) n
in
sqrt_iter 1.0 n;;
ローカル関数(?)の定義って and で良かったのかな。（未検証）
駄目なら let ... in で。
その次は、Haskell。OCaml と殆ど同じだけど、
型を気にしなくてもいいのと、再帰の宣言がいらないので楽。
ただし、sqrt の定義の上書きは無理みたい。
my_sqrt n = let abs n = if n < 0 then (-n) else n in let square n = n * n in let average a b = (a + b) / 2 in let improve guess n = average guess (n / guess) in let good_enough guess n = abs((square guess) - n) < 0.001 in let my_sqrt_iter guess n = if good_enough guess n then guess else my_sqrt_iter (improve guess n) n in my_sqrt_iter 1.0 n;;
OCaml と Haskell は、まだ始めたばかりなので、
コーディングスタイルがまだ解らない。パディングしてもいいのかな。
Pythonでは推奨されていないのだけど、
ここでは保守性より読みやすさ重視なので（・・・と断りを入れてから）
def sqrt(num): abs = lambda x : (x < 0) and -x or x square = lambda x : x * x average = lambda x,y : (x+y)/2 improve = lambda guess,n : average(guess,(n/guess)) good_enough = lambda guess,n : abs(square(guess)-n) < 0.001 def sqrt_iter(guess,n): if good_enough(guess,n): return guess else: sqrt_iter(improve(guess,n), n) sqrt_iter(1.0, num)
最後に、C 。
#define ABS(N) *1 #define SQUARE(N) *2 #define AVERAGE(A,B) (((A)+(B))/2) #define IMPROVE(GUESS,N) (AVERAGE*3<0.001) float sqrt_iter(float guess, int n){ if (GOOD_ENOUGH(guess, n)) return guess; else return sqrt_iter(IMPROVE(guess,n), n); } float my_sqrt(guess, n){ return sqrt_iter(1.0, n); }
