Решение упражнения 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

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

Comment from ikuchmin
Date: October 24, 2010, 4:38 pm

Не совсем понимаю зачем искать долю изменения в предыдущим приближении. Можно просто исходить из разности двух приближений:

(define (good-enough? guess storyguess)
(< (abs (- guess storyguess)) 0.0001))

Хотя тут возникает вопрос о понятии "точность" и его трактовке

Comment from Nori
Date: November 17, 2011, 7:58 pm

Всего лишь изменил good-enough?.

(define (good-enough? guess x)
(< (abs (- guess (improve guess x))) 0.000000000000001))

Больше ничего не менял.
Выдаёт:

> (sqrt 3)
1.7320508075688772
> (sqrt 2)
1.414213562373095
> (sqrt 1000000)
1000.0
> (sqrt 4)
2.0
> (sqrt 9)
3.0
> (sqrt 16)
4.0

Comment from Elvis
Date: August 12, 2012, 2:31 pm

Согласен с ikuchmin его вариант самый простой, я тоже додумался до такого варианта.
Я сравнительно новичок а следовательно вариант до которого я додумался, самый простой. Пока читал все остальные(те что на первых позициях) просто их не понимал (у меня с математикой не все гладко), вариант с разницей самый простой, зачем еще и делить.

(define (good-enough? oldguess guess)
(< (abs (- oldguess guess)) 0.0000000000001))

(define (sqrt-iter oldguess guess x)
(if (good-enough? guess oldguess)
guess
(sqrt-iter guess (improve guess x)
x)))
(define (square x) (* x x))

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

(define (average x y)
(/ (+ x y) 2))


> (sqrt-iter 0.00000000001 1.0 0.00000000001)
3.162277660168379e-006
> (sqrt-iter 0.000000000001 1.0 0.000000000001)
1e-006

В место первого oldguess я пишу значение вычисляемого числа, так как первый раз написать что-то нужно, и это что-то не должно совпадать с первым приближением.

Comment from alchimik
Date: August 28, 2013, 4:17 pm

to Elvis, ikuchmin
если в good-enough? просто искать разницу двух предложений, то:
1 при больших числах точность будет слишком большой
2 при маленьких – слишком маленькой.
В общем, те же проблемы что и в изначальном варианте.

Nori +1
Автор переписал всё к чертям, а достаточно изменить только good-enough?

to Dan
проблема в том что в начальном варианте эпсилон соотносится с точность результата весьма непростым способом. Т.е, если мне надо получить результат с точностью 1%, то какой мне надо указывать эпсилон в изначальном варианте good-enough? .Придётся как-то хитро вычислять.

to thror
Имхо, (epsilon guess) – это не нужно, просто получаем излишнюю точность на больших числах.

Comment from niar6
Date: September 7, 2013, 5:45 pm

Хм.
Не знаю, но у меня все отлично работает путем улучшения разницы между нынешным и следющими значениями.
> (define (sqrt x) (sqrtiter 1.0 x))
> (define (sqriter guess x) (if ( (define (sqrt x) (sqriter 1.0 x))
> (define (sqriter guess x) (if ( (define (sqriter guess x) (if ( (define (improve guess x) (average guess (/ x guess))

И на маленьких и на больших значениях отлично работает.

Comment from niar6
Date: September 7, 2013, 5:47 pm

Oh. Моя косяк.

(define (sqrt x) (sqrtiter 1.0 x))
(define (sqriter guess x) (if (< (abs (- guess (improve guess x))) 0.0001) guess (sqriter (improve guess x) x)))
(define (improve guess x) (average guess (/ x guess))
(define (average x y) (/ (+ x y) 2))

Comment from trollface
Date: January 20, 2014, 11:52 pm

точность наше всьо!
> (define (sqrt-iter guess x epsilon)
(if (good-enough? guess x epsilon)
guess
(sqrt-iter (improve guess x)
x)))
> (define (sqrt-iter guess x epsilon)
(if (good-enough? guess x epsilon)
guess
(sqrt-iter (improve guess x)
x epsilon)))
> (define (improve guess x)
(average guess (/ x guess)))
> (define (good-enough? guess x epsilon)
( (define (sqrt x epsilon) (sqrt-iter 1.0 x epsilon))

Comment from Илья Иванов
Date: January 3, 2015, 5:37 pm

(define (sqrt-iter guess x)
        (if
                (good-enough? guess x)
                guess
                (sqrt-iter (improve guess 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))
 
;изменения и добавление del-min-max
 
;добавляем функцию del-min-max
 
(define (del-min-max x y)
        (> x y)
        (/ y x)
        (/ x y))
 
;изменяем good-enough?
 
(define (good-enough? guess x)
        (> (del-min-max guess (improve guess x)) 0.9999))

Comment from GhostDog
Date: August 7, 2017, 4:26 pm

(define (abs x)
  (if (< x 0)
      (- x)
      x))

(define (square x)
  (* x x))

(define (qube x)
  (* x x x))

(define (better-good-enough? guess x)
  (and (< (abs (- (square guess) x)) 0.00000001)
       (< (abs (- (improve guess x) guess)) 0.00000001)))


(define (average x y)
  (/ (+ x y)
     2))

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

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

(define (sqrt x)
  (sqrt-iter 1.0 x))

Write a comment