80 lines
No EOL
3.1 KiB
Racket
80 lines
No EOL
3.1 KiB
Racket
#lang sicp
|
||
|
||
;1.1.7 Example: Square Roots by Newton's Method
|
||
;The most common way to compute square root is to use Newton's method of successive approximations --> whenever we have a guess y for the value of the square root of a number x, we can perform a simple manipulation to get a better guess.
|
||
;The procedure is
|
||
;(define (sqrt-iter guess x)
|
||
; (if (good-enough? guess x)
|
||
; guess
|
||
; (sqrt-iter (improve guess x) x))
|
||
;)
|
||
;A guess is improved by averaging it with the quotient of the radicand and the old guess
|
||
;(define (improve guess x)
|
||
; (/ (+ guess (/ x guess)) 2)
|
||
;)
|
||
;where
|
||
;(define (average x y)
|
||
; (/ (+ x y) 2)
|
||
;)
|
||
;The idea is to improve the answer until it is close enough so that its square differs from the radicand by less than a predetermined tolerance (here 0.001)
|
||
;(define (good-enough? guess x)
|
||
; (< (abs (- (square guess) x)) 0.001)
|
||
;)
|
||
;we need a way to get started. For instance, we can always guess that the square root of any number is 1 (if we start with an initial guess of 1 in our square-root program, and x is an exact integer, all subsequent values produced in the square-root computation will be rational numbers rather than decimals. Mixed operations on rational numbers
|
||
;and decimals always yield decimals, so starting with an initial guess of 1.0 forces all subsequent values to be decimals.)
|
||
;(define (sqrt x)
|
||
; (sqrt-iter 1.0 x)
|
||
;)
|
||
|
||
;(define (square x) (* x x))
|
||
|
||
;(sqrt 25) ;the result should be 5.000023178253949
|
||
;(sqrt 9) ;the result should be 3.00009155413138
|
||
|
||
;--------------------------------------------------------------------------------------------------------------------------
|
||
;ex_6
|
||
;Alyssa P. Hacker doesn’t see why if needs to be provided as a special form. “Why can’t I just define it as an ordinary procedure in terms of cond?” she asks. Alyssa’s friend Eva claims this can indeed be done, and she defines a new version of if:
|
||
;(define (new-if predicate then-clause else-clause)
|
||
; (cond (predicate then-clause)
|
||
; (else else-clause))
|
||
;)
|
||
;Eva demonstrates the program for Alyssa:
|
||
;(new-if (= 2 3) 0 5)
|
||
;5
|
||
;(new-if (= 1 1) 0 5)
|
||
;0
|
||
;Delighted, Alyssa uses new-if to rewrite the square-root
|
||
;program:
|
||
;(define (sqrt-iter guess x)
|
||
; (new-if (good-enough? guess x)
|
||
; guess
|
||
; (sqrt-iter (improve guess x) x))
|
||
;)
|
||
;What happens when Alyssa attempts to use this to compute square roots? Explain.
|
||
;--------------------------------------------------------------------------------------------------------------------------
|
||
|
||
(define (new-if predicate then-clause else-clause)
|
||
(cond (predicate then-clause)
|
||
(else else-clause)))
|
||
|
||
(define (average x y) (/ (+ x y) 2))
|
||
|
||
(define (square x) (* x x))
|
||
|
||
(define (improve guess x) (average guess (/ x guess)))
|
||
|
||
(define (good-enough? guess x)
|
||
(< (abs (- (square guess) x)) 0.001))
|
||
|
||
|
||
(define (sqrt-iter guess x)
|
||
(new-if (good-enough? guess x) ;(good-enough? guess x), guess and (sqrt-iter (improve guess x) x) will always be evaluated before new-if
|
||
guess
|
||
(sqrt-iter (improve guess x) x))
|
||
)
|
||
|
||
(define (sqrt x)
|
||
(sqrt-iter 1.0 x)
|
||
)
|
||
|
||
(sqrt 25) ;--> infinite loop// new-if will never be executed |