Решение упражнения 1.7 из SICP

15 August, 2007 (23:25) | Решения упражнений

Перед тем, как что-то разрабатывать, как нас просят в упражнении, сначала убедимся в том, что проблема, которую мы хотим преодолеть, путем усовершенствования кода, действительно существует.

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))
(define (square x) (* x x))
(define (improve guess x)
  (average guess (/ x guess)))
(define (average x y)
  (/ (+ x y) 2))
(define (sqrt x)
  (sqrt-iter 1.0 x))

Вычислим sqrt для некоторых чисел:

> (sqrt 4)
2.0000000929222947
> (sqrt 100)
10.000000000139897
> (sqrt 0.01)
0.10032578510960605
> (sqrt 0.0001)
0.03230844833048122
> (sqrt 0.000001)
0.031260655525445276
> (sqrt 0.00000001)
0.03125010656242753

Видно, что проблема не надумана. На маленьких значениях аргумента функция вычисляет что угодно, но только не его квадратный корень.

Реализуем более точный вариант, как и сказано в условии упражнения. Доопределим недостающие функции:

(define (better-good-enough? guess prev-guess)
  (< (abs (/ (- guess prev-guess) prev-guess)) 0.001))
(define (better-sqrt-iter guess prev-guess x)
  (if (better-good-enough? guess prev-guess)
      guess
      (better-sqrt-iter (improve guess x)
                        guess
                        x)))
(define (better-sqrt x)
  (better-sqrt-iter 1.0 0.5 x))

Произведем новые вычисления тех же значений с помощью усовершенствованной функции вычисления квадратного корня:

> (better-sqrt 4)
2.0000000929222947
> (better-sqrt 100)
10.000000000139897
> (better-sqrt 0.01)
0.10000000000139897
> (better-sqrt 0.0001)
0.010000000025490743
> (better-sqrt 0.000001)
0.0010000001533016628
> (better-sqrt 0.00000001)
0.00010000000000082464

Как видим, новая функция дает хорошие результаты и на малых значениях аргумента.

Еще одно интересное наблюдение. Попробуйте вычислить что-то вроде (sqrt 1000000000000000). У меня происходит зацикливание. Причина тому указана в условии упражнения. В то же время (better-sqrt 1000000000000000) отрабатывает без каких-либо проблем и выдает неплохой результат.

Comments

Comment from thror
Date: February 14, 2008, 11:40 pm

Предлагаю свой вариант. На гаргантюанских =) числах он работает значительно лучше. Сами знаете почему. Обратите внимание на (epsilon guess)…

(define (sqrt x)
  (define (average a b)
    (/ (+ a b) 2))

  (define (iter guess)
    (if (good-enough? guess)
	guess
	(iter (improve guess))))

  (define (improve guess)
    (average guess (/ x guess)))

  (define (epsilon guess)
    (* 0.001 (min 1.0 (abs guess))))

  (define (good-enough? guess)
    (< (abs (- guess (improve guess))) (epsilon guess)))

  (if (= x 0)
      0
      (iter 1.0)))

Comment from Dan
Date: May 15, 2008, 7:48 pm

“Видно, что проблема не надумана. На маленьких значениях аргумента функция вычисляет что угодно, но только не его квадратный корень.”
Так причина в эпсилон. Подберите эпсилон, так и точность возрастет. thror - дело пишет.

Comment from JessicaFletcher
Date: December 10, 2009, 7:19 am

(define (better-sqrt-iter guess x)
(if (better-good-enough? guess (improve guess x))
guess
(better-sqrt-iter (improve guess x)
x)))

Comment from randomguy
Date: March 30, 2010, 7:08 pm

(define (good-enough? guess x)
 ( (sqrt 4)
guile> (sqrt 4)
2.00000009292229
guile> (sqrt 10)
3.16227766517567
guile> (sqrt 0.01)
0.100000528956427
guile> (sqrt 0.0001)
0.0100007140387117
guile> (sqrt 0.000001)
0.0010338412392442
guile> (sqrt 0.00000001)
1.48228473353842e-4
guile> (sqrt 1000000000000000)
31622776.6016839

Изменения минимальны, а точность повысилась, чем плох данный вариант?

Write a comment