1 #!/usr/local/bin/ruby
2 # encoding: utf-8
3
4 #Newton's method
5 def sqrt_iter(guess, x)
6 if good_enough?(guess, x)
7 guess
8 else
9 sqrt_iter(improve(guess, x), x)
10 end
11 end
12
13 def improve(guess, x)
14 average(guess, x/guess)
15 end
16
17 def average(x, y)
18 (x + y) / 2
19 end
20
21 def good_enough?(guess, x)
22 (square(guess) - x).abs < 0.001
23 end
24
25 def square(x)
26 x * x
27 end
28
29 def sqrt(x)
30 sqrt_iter(1.0, x)
31 end
32
33 sqrt 9 # => 3.00009155413138
34
35 #fixed point method
36 Tolerance = 0.00001
37 def fixed_point(f, first_guess)
38 def close_enough?(v1, v2)
39 (v1 - v2).abs < Tolerance
40 end
41 def try(guess, f)
42 _next = f.call(guess)
43 if close_enough?(guess, _next)
44 _next
45 else
46 try(_next, f)
47 end
48 end
49 try(first_guess, f)
50 end
51
52 fixed_point(lambda{ |y| Math.sin(y) + Math.cos(y) }, 1.0) # => 1.25873159629712
53
54 def sqrt(x)
55 fixed_point(lambda { |y| average(y, x/y) }, 1.0)
56 end
57
58 sqrt 3 # => 1.73205080756888
59
60 def average_damp(f)
61 lambda { |x| average(x, f.call(x)) }
62 end
63
64 def sqrt(x)
65 fixed_point(average_damp(lambda { |y| x/y }), 1.0)
66 end
67
68 sqrt 3 # => 1.73205080756888
69
70 def average_damp
71 lambda { |x| average(x, yield(x)) }
72 end
73
74 def sqrt(x)
75 fixed_point(average_damp{ |y| x/y }, 1.0)
76 end
77
78 sqrt 5 # => 2.23606797749998
1 #!/usr/local/bin/ruby
2 # encoding: utf-8
3 class Numeric
4 def square
5 self**2
6 end
7
8 def sqrt
9 sqrt_iter(1.0)
10 end
11
12 def sqrt_by_fp
13 fixed_point(1.0) { |y| average(y, self/y) }
14 end
15
16 def sqrt_with_adump
17 fixed_point(1.0) { |y| average_damp(y) }
18 end
19
20 private
21 def sqrt_iter(guess)
22 if good_enough?(guess, self)
23 guess
24 else
25 sqrt_iter(improve(guess))
26 end
27 end
28
29 def improve(guess)
30 average(guess, self/guess)
31 end
32
33 def average(x, y)
34 (x + y) / 2
35 end
36
37 def good_enough?(guess, x)
38 (guess.square - x).abs < 0.001
39 end
40
41 def fixed_point(first_guess)
42 try(first_guess) { |y| yield(y) }
43 end
44
45 Tolerance = 0.00001
46 def close_enough?(v1, v2)
47 (v1 - v2).abs < Tolerance
48 end
49
50 def try(guess)
51 _next = yield(guess)
52 if close_enough?(guess, _next)
53 _next
54 else
55 try(_next){ |y| yield(y) }
56 end
57 end
58
59 def average_damp
60 lambda { |x| average(x, yield(x)) }
61 end
62 end
63
64 2.sqrt # => 1.41421568627451
65 2.square # => 4
66 2.sqrt_by_fp # => 1.41421356237469
67
