Revision of 1.3.3 Procedures as General Methods from 14 July 2009 - 9:27pm

The revisions let you track differences between multiple versions of a post.

Printer-friendly versionPrinter-friendly version

We introduced compound procedures in section 1.1.4 as a mechanism for abstracting patterns of numerical operations so as to make them independent of the particular numbers involved. With higher-order procedures, such as the integral procedure of section 1.3.1, we began to see a more powerful kind of abstraction: procedures used to express general methods of computation, independent of the particular functions involved. In this section we discuss two more elaborate examples — general methods for finding zeros and fixed points of functions — and show how these methods can be expressed directly as procedures.

Finding roots of equations by the half-interval method

The half-interval method is a simple but powerful technique for finding roots of an equation f(x) = 0, where f is a continuous function. The idea is that, if we are given points a and b such that f(a) < 0 < f(b), then f must have at least one zero between a and b. To locate a zero, let x be the average of a and b and compute f(x). If f(x) > 0, then f must have a zero between a and x. If f(x) < 0, then f must have a zero between x and b. Continuing in this way, we can identify smaller and smaller intervals on which f must have a zero. When we reach a point where the interval is small enough, the process stops. Since the interval of uncertainty is reduced by half at each step of the process, the number of steps required grows as Θ(log( L/T)), where L is the length of the original interval and T is the error tolerance (that is, the size of the interval we will consider “small enough”). Here is a procedure that implements this strategy:

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

We assume that we are initially given the function f together with points at which its values are negative and positive. We first compute the midpoint of the two given points. Next we check to see if the given interval is small enough, and if so we simply return the midpoint as our answer. Otherwise, we compute as a test value the value of f at the midpoint. If the test value is positive, then we continue the process with a new interval running from the original negative point to the midpoint. If the test value is negative, we continue with the interval from the midpoint to the positive point. Finally, there is the possibility that the test value is 0, in which case the midpoint is itself the root we are searching for.

To test whether the endpoints are “close enough” we can use a procedure similar to the one used in section 1.1.7 for computing square roots:[55]

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

Search is awkward to use directly, because we can accidentally give it points at which f’s values do not have the required sign, in which case we get a wrong answer. Instead we will use search via the following procedure, which checks to see which of the endpoints has a negative function value and which has a positive value, and calls the search procedure accordingly. If the function has the same sign on the two given points, the half-interval method cannot be used, in which case the procedure signals an error.[56]

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sign" a b)))))

The following example uses the half-interval method to approximate π as the root between 2 and 4 of sin x = 0:

(half-interval-method sin 2.0 4.0)
3.14111328125

Here is another example, using the half-interval method to search for a root of the equation x3 - 2x - 3 = 0 between 1 and 2:

(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
                      1.0
                      2.0)
1.89306640625

Finding fixed points of functions

A number x is called a fixed point of a function f if x satisfies the equation f(x) = x. For some functions f we can locate a fixed point by beginning with an initial guess and applying f repeatedly,

f(x), f(f(x)), f(f(f(x))), . . .

until the value does not change very much. Using this idea, we can devise a procedure fixed-point that takes as inputs a function and an initial guess and produces an approximation to a fixed point of the function. We apply the function repeatedly until we find two successive values whose difference is less than some prescribed tolerance:

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

For example, we can use this method to approximate the fixed point of the cosine function, starting with 1 as an initial approximation:[57]

(fixed-point cos 1.0)
.7390822985224023

Similarly, we can find a solution to the equation y = sin y + cos y:

(fixed-point (lambda (y) (+ (sin y) (cos y)))
             1.0)
1.2587315962971173

The fixed-point process is reminiscent of the process we used for finding square roots in section 1.1.7. Both are based on the idea of repeatedly improving a guess until the result satisfies some criterion. In fact, we can readily formulate the square-root computation as a fixed-point search. Computing the square root of some number x requires finding a y such that y2 = x. Putting this equation into the equivalent form y = x/y, we recognize that we are looking for a fixed point of the function[58] yx/y, and we can therefore try to compute square roots as

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))

Unfortunately, this fixed-point search does not converge. Consider an initial guess y1. The next guess is y2 = x/y1 and the next guess is y3 = x/y2 = x/(x/y1) = y1. This results in an infinite loop in which the two guesses y1 and y2 repeat over and over, oscillating about the answer.

One way to control such oscillations is to prevent the guesses from changing so much. Since the answer is always between our guess y and x/y, we can make a new guess that is not as far from y as x/y by averaging y with x/y, so that the next guess after y is (1/2)(y + x/y) instead of x/y. The process of making such a sequence of guesses is simply the process of looking for a fixed point of y → (1/2)(y + x/y):

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

(Note that y = (1/2)(y + x/y) is a simple transformation of the equation y = x/y; to derive it, add y to both sides of the equation and divide by 2.)

With this modification, the square-root procedure works. In fact, if we unravel the definitions, we can see that the sequence of approximations to the square root generated here is precisely the same as the one generated by our original square-root procedure of section 1.1.7. This approach of averaging successive approximations to a solution, a technique we that we call average damping, often aids the convergence of fixed-point searches.

[55] We have used 0.001 as a representative “small” number to indicate a tolerance for the acceptable error in a calculation. The appropriate tolerance for a real calculation depends upon the problem to be solved and the limitations of the computer and the algorithm. This is often a very subtle consideration, requiring help from a numerical analyst or some other kind of magician. [back]
[56] This can be accomplished using error, which takes as arguments a number of items that are printed as error messages. [back]
[57] Try this during a boring lecture: Set your calculator to radians mode and then repeatedly press the cos button until you obtain the fixed point. [back]
[58] (pronounced “maps to”) is the mathematician’s way of writing lambda. y x/y means (lambda(y) (/ x y)), that is, the function whose value at y is x/y. [back]

Exercises

Exercise 1.35

Show that the golden ratio φ (section 1.2.2) is a fixed point of the transformation x → 1 + 1/x, and use this fact to compute φ by means of the fixed-point procedure.

Exercise 1.36

Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise 1.22. Then find a solution to xx = 1000 by finding a fixed point of xlog(1000)/log(x). (Use Scheme’s primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)

Exercise 1.37

  1. An infinite continued fraction is an expression of the form

    As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1/φ, where φ is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation — a so-called k-term finite continued fraction — has the form

    Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/φ using

    (cont-frac (lambda (i) 1.0)
               (lambda (i) 1.0)
               k)

    for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?

  2. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Exercise 1.38

In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In this fraction, the Ni are all 1, and the Di are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, . Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler’s expansion.

Exercise 1.39

A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert:

where x is in radians. Define a procedure (tan-cf x k) that computes an approximation to the tangent function based on Lambert’s formula. K specifies the number of terms to compute, as in exercise 1.37.

Comments

zpPtStHVBIJWtlSFeek

I could read a book about this wioutht finding such real-world approaches!

1.3.3 Procedures as General Methods | SICP in Clojure

http://www.rateamateapp.com

http://www.zmbgc.com/sm/thread-946020-1-1.html http://www.cpu520.com/read.php?tid=81427&ds=1 http://www.52jiaoxue.com/bbs/forum.php?mod=viewthread&tid=193447 http://0595.315.cm/thread-352320-1-1.html http://url.ylmov.com/forum.php?mod=viewthread&tid=497273&fromuid=46778 http://www.lhedu.net/bbs/read.php?tid-546125.html http://www.zqgs5188.com/forum.php?mod=viewthread&tid=626630 http://rangdecolours.com/node/49521 http://wiki.iproj.org/index.php?title=User:Hytlazkx#http:.2F.2Fwww.naec…. http://brchinese.com/forum.php?mod=viewthread&tid=214439 http://old.moto8.com/old/Review.asp?NewsID=1287 http://cwc.hlbrc.cn/Review.asp?NewsID=853 http://www.mtbyw.com/forum.php?mod=viewthread&tid=93108&fromuid=6409 http://www.qzmuseum.net/Review.asp?NewsID=139 http://qzmuseum.net/Review.asp?NewsID=139 http://maxxyme.free.fr/wiki/index.php?title=User:Cbxoyz9n#www.bihardiary… http://shamanita.org/wiki/index.php?title=User:I4ufwdck#http:.2F.2Fwww.e… http://www.qjqj.net/forum.php?mod=viewthread&tid=130574&fromuid=6042 http://inclusionwsuv.org/wiki/User:Ahgqyzf8#http:.2F.2Fwww.ihcc.sa.2Find… http://www.yxqnlxx.cn/Review.asp?NewsID=464 http://jingliansi.w204.mc-test.com/thread-140624-1-1.html http://www.zhongbanggongju.com/bbs/forum.php?mod=viewthread&tid=1554943 http://wanhaidao.com/index.php?title=User:Fgiqenl5#www.medhomealert.com…. http://360moneng.com/forum.php?mod=viewthread&tid=455993 http://www.gelou520.com/thread-672144-1-1.html http://winged-justice.com/wiki/User:K60sqof4#www.roc-tech.com.2Findex.as… http://www.hpv99.net/bbs/thread-1526387-1-1.html http://www.jzlsw.com/Review.asp?NewsID=1144 http://dallaslibrary2.org/wiki/index.php?title=User:Hcor8lny#www.sundayc… http://www.mcctv.com.cn/bbs/showtopic-200953.aspx http://bbs.ntwmall.com/forum.php?mod=viewthread&tid=3775632 http://www.rad3d.ca/plastic/index.php?title=User:Jhqp52xg#http:.2F.2Fwww… http://www.dtstudyclub.com/index.php?do=/blog/add/ http://qichexh.com/bbs/forum.php?mod=viewthread&tid=336020 http://hakerville.com/index.php?do=/blog/66377/www-loescher-it-index-asp… http://www.cinec.ca/network/forum.php?mod=viewthread&tid=98677 http://bbs4.zgyanshi.com/forum.php?mod=viewthread&tid=97194 http://www.nss184xx.com/Review.asp?NewsID=489 http://bbs.easy8.cc/thread-295197-1-1.html http://www.china-gutian.com/bbs/forum.php?mod=viewthread&tid=1854302 http://eredar.com.idserver-3.yunhosting.net/bbs/forum.php?mod=viewthread… http://www.hotliao.com/forum.php?mod=viewthread&tid=958986 http://www.xiangfanbbs.com/forum.php?mod=viewthread&tid=518620 http://oox766.g8.namepu.com/thread-604880-1-1.html http://www.caixinxian.com/forum.php?mod=viewthread&tid=319202 http://liu897.com/read.php?tid=65127 http://www.cncuu.cn/forum.php?mod=viewthread&tid=237877 http://www.moushi.cc/forum.php?mod=viewthread&tid=3834129 http://bbs.91youke.com/thread-910969-1-1.html http://www.n3368.com/thread-979424-1-1.html http://simotaoussi.com/index.php?do=/blog/190413/http-www-loescher-it-in… http://5941go.com/forum.php?mod=viewthread&tid=2218644 http://www.9tuan8.com/bbs/forum.php?mod=viewthread&tid=2298592 http://www.tsfgj.cn/Review.asp?NewsID=1882 http://bbs.m.1799.com/forum.php?mod=viewthread&tid=613662&fromuid=366245 http://hbyly.sfsly.com/bbs/forum.php?mod=viewthread&tid=390350 http://www.gz-12.com/forum.php?mod=viewthread&tid=1165757 http://www.ooxxxxoo.com/forum.php?mod=viewthread&tid=2776778 http://sanfuyuqi.com/bbs/forum.php?mod=viewthread&tid=695381 http://demo.bee.com.my/discuzx/forum.php?mod=viewthread&tid=670621 http://bbs.lybyjj.com/forum.php?mod=viewthread&tid=1658393 http://www.qjqj.net/forum.php?mod=viewthread&tid=130590&fromuid=6046 http://xinliweishi.118207.84g.com/forum.php?mod=viewthread&tid=1295678 http://bbs.chuangfe.com/forum.php?mod=viewthread&tid=904945 http://ev-evu.org/forum.php?mod=viewthread&tid=933822 http://www.ggfabu.com/thread-9954456-1-1.html http://cluo.cn/forum.php?mod=forumdisplay&fid=39&filter=typeid&typeid=1 http://www.gzchlz.com/bbs/forum.php?mod=viewthread&tid=349983 http://www.8080xs.com/forum.php?mod=viewthread&tid=106457 http://bimeido.lolipop.jp/luntan/forum.php?mod=viewthread&tid=601792
http://www.rateamateapp.com http://www.rateamateapp.com

iso certifications india

Nice post, I bookmark your blog because I found very good information on your blog, Thanks for sharing more information
Quality Services & Training Pvt.Ltd.

iso certification india

ISO 22000 is one of the highest marks of safety. It isn’t easy to get this mark. One needs to be able to showcase that they can handle obstacles that shall cause the food to spoil and manufacture it in such way that it is absolutely safe for consuming. Unless, this is proved, a firm cannot get the ISO 22000 mark.
Any and every organisation that is into food manufacture has to implement machinery to ensure that it produces absolutely safe quality of food. No matter, what part of the process of food manufacture, the firm is involved in, it has to ensure of the safety of the final produce. It isn’t easy to meet the mark required for ISO certification. One shall have to have access to a lot of capital from inside as well as outside the food chain. Moreover, the marks set by ISO 22000 are necessary because the firm can:

more information
Quality Services & Training Pvt.Ltd.

fssai india

FSSAI stands for the Food Safety Standards Authority of India. This was instigated via the Food Safety and Standards Act in the year 2006. The FSSAI looks into
Manufacture
Storage
Distribution
Sale
And Import of the food items
The main aim of this body is to make sure of the fact that food across the country is safe for consumption.
We can help your organisation get an FSSAI license. We’ll provide you with
Consultation
Training
Documentation
This will help you in getting an FSSAI license. However, you need to register, implement the standards and undergo training as well in order to attain an FSSAI license.
Hence, if you are a part of a food chain manufacturing then, you should waste no time in getting an FSSAI license. The following businesses must get an FSSAI license:
more information
Quality Services & Training Pvt.Ltd.

ヴィトン バッグ 定番

貴重品や必要なクスリ?コンタクト洗浄液なども機内持ち込みにしましょう。
ヴィトン バッグ 定番 http://www.coupar-angus.org/flash/link.asp?id=552

1.3.3 Procedures as General Methods | SICP in Clojure

I wanted to thank you for this fantastic read!! I certainly enjoyed every bit of it.
I’ve got you book-marked to look at new things you post

Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options