Решение упражнения 1.7 из SICP
Перед тем, как что-то разрабатывать, как нас просят в упражнении, сначала убедимся в том, что проблема, которую мы хотим преодолеть, путем усовершенствования кода, действительно существует.
(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))
Write a comment