exercise06.tm

<TeXmacs|2.1.2>

<style|<tuple|exam|no-page-numbers|british|smart-ref>>

<\body>
  <\folded>
    <\render-exercise|Exercise 1.14>
      Draw the tree illustrating the process generated by the
      <code*|count-change> procedure of Section 1.2.2 in making change for 11
      cents. What are the orders of growth of the space and number of steps
      used by this process as the amount to be changed increases?
    </render-exercise>
  <|folded>
    <\session|scheme|default>
      <\unfolded-io|Scheme] >
        (define (first-denomination kinds-of-coins)

        \ \ (cond ((= kinds-of-coins 1) 1)

        \ \ \ \ \ \ \ \ ((= kinds-of-coins 2) 5)

        \ \ \ \ \ \ \ \ ((= kinds-of-coins 3) 10)

        \ \ \ \ \ \ \ \ ((= kinds-of-coins 4) 25)

        \ \ \ \ \ \ \ \ ((= kinds-of-coins 5) 50)))
      <|unfolded-io>
        first-denomination
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (define (cc amount kinds-of-coins)

        \ \ (cond ((= amount 0) 1)

        \ \ \ \ \ \ \ \ ((or (\<less\> amount 0) (= kinds-of-coins 0)) 0)

        \ \ \ \ \ \ \ \ (else (+ (cc amount

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (- kinds-of-coins 1))

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (cc (- amount

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (first-denomination
        kinds-of-coins))

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ kinds-of-coins)))))
      <|unfolded-io>
        cc
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (define (count-change amount)

        \ \ (cc amount 5))
      <|unfolded-io>
        count-change
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (count-change 11)
      <|unfolded-io>
        4
      </unfolded-io>

      <\input|Scheme] >
        \;
      </input>
    </session>
  </folded>

  <\folded>
    <\render-exercise|Exercise 1.15>
      The sine of an angle (specified in radians) can be computed by making
      use of the approximation <math|sin\<nospace\>x\<approx\>x> if <math|x>
      is sufficiently small, and the trigonometric identity
      <math|sin\<nospace\>x=3 sin\<nospace\><frac|x|3>-4
      sin<rsup|3>\<nospace\><frac|x|3>> to reduce the size of the argument of
      sin. (For purposes of this exercise an angle is considered
      \Psufficiently small\Q if its magnitude is not greater than 0.1
      radians.) These ideas are incorporated in the following procedures:

      <\scm-code>
        (define (cube x) (* x x x))

        (define (p x) (- (* 3 x) (* 4 (cube x))))

        (define (sine angle)

        \ \ \ (if (not (\<gtr\> (abs angle) 0.1))

        \ \ \ \ \ \ \ angle

        \ \ \ \ \ \ \ (p (sine (/ angle 3.0)))))
      </scm-code>

      <\enumerate-alpha>
        <item>How many times is the procedure <code*|p> applied when
        <code*|(sine 12.15)> is evaluated?

        <item>What is the order of growth in space and number of steps (as a
        function of <math|a>) used by the process generated by the
        <code*|sine> procedure when <code*|(sine a)> is evaluated?
      </enumerate-alpha>
    </render-exercise>
  <|folded>
    <\session|scheme|default>
      <\unfolded-io|Scheme] >
        (define (cube x) (* x x x))
      <|unfolded-io>
        cube
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (define (p x)

        \ \ (debug-message "std" (string-append "p " (number-\<gtr\>string x)
        "\\n"))

        \ \ (- (* 3 x) (* 4 (cube x))))
      <|unfolded-io>
        p
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (define (sine angle)

        \ \ \ (if (not (\<gtr\> (abs angle) 0.1))

        \ \ \ \ \ \ \ angle

        \ \ \ \ \ \ \ (p (sine (/ angle 3.0)))))
      <|unfolded-io>
        sine
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (sine 0.1)
      <|unfolded-io>
        0.1
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (sin 0.1)
      <|unfolded-io>
        0.09983341664682815
      </unfolded-io>

      <\input|Scheme] >
        \;
      </input>
    </session>
  </folded>

  <\folded>
    <\render-exercise|Exercise 1.16>
      <label|ex1.16>Design a procedure that evolves an iterative
      exponentiation process that uses successive squaring and uses a
      logarithmic number of steps, as does <code*|fast-expt>. (Hint: Using
      the observation that <math|<around*|(|b<rsup|n<around*|/|2|\<nobracket\>>>|)><rsup|2>=<around*|(|b<rsup|2>|)><rsup|n<around*|/|2|\<nobracket\>>>>,
      keep, along with the exponent <math|n> and the base <math|b>, an
      additional state variable <math|a>, and define the state transformation
      in such a way that the product <math|ab<rsup|n>> is unchanged from
      state to state. At the beginning of the process <math|a> is taken to be
      1, and the answer is given by the value of <math|a> at the end of the
      process. In general, the technique of defining an
      <label|index-invariant-quantity> <em|invariant
      quantity><index|invariant quantity> that remains unchanged from state
      to state is a powerful way to think about the design of iterative
      algorithms.)
    </render-exercise>
  <|folded>
    <\render-exercise|\<#63D0\>\<#793A\>>
      \;

      <\eqnarray*>
        <tformat|<table|<row|<cell|f<around*|(|b|)>>|<cell|=>|<cell|b<rsup|n>>>|<row|<cell|>|<cell|=>|<cell|f<around*|(|b,n,1|)>>>|<row|<cell|f<around*|(|b,n,a|)>>|<cell|=>|<cell|a*b<rsup|n>>>|<row|<cell|f<around*|(|b,n,a|)>>|<cell|=>|<cell|<choice|<tformat|<table|<row|<cell|f<around*|(|b<rsup|2>,<frac|n|2>,a|)>=<around*|(|b<rsup|2>|)><rsup|<frac|n|2>>*a>|<cell|,
        n\<#662F\>\<#5076\>\<#6570\>>>|<row|<cell|f<around*|(|b<rsup|2>,<frac|n-1|2>,a*b|)>=<around*|(|b<rsup|2>|)><rsup|<frac|n-1|2>>*b*a=b<rsup|n>>|<cell|,n\<#662F\>\<#5947\>\<#6570\>>>|<row|<cell|>|<cell|,n=2>>|<row|<cell|a*b>|<cell|,n=1>>|<row|<cell|a>|<cell|,n=0>>>>>>>>>
      </eqnarray*>
    </render-exercise>
  </folded>

  <\folded>
    <\render-exercise|Exercise 1.17>
      <label|ex1.17>The exponentiation algorithms in this section are based
      on performing exponentiation by means of repeated multiplication. In a
      similar way, one can perform integer multiplication by means of
      repeated addition. The following multiplication procedure (in which it
      is assumed that our language can only add, not multiply) is analogous
      to the <code*|expt> procedure:

      <\scm-code>
        (define (* a b)

        \ \ (if (= b 0)

        \ \ \ \ \ \ 0

        \ \ \ \ \ \ (+ a (* a (- b 1)))))
      </scm-code>

      This algorithm takes a number of steps that is linear in <code*|b>. Now
      suppose we include, together with addition, operations <code*|double>,
      which doubles an integer, and <code*|halve>, which divides an (even)
      integer by 2. Using these, design a multiplication procedure analogous
      to <code*|fast-expt> that uses a logarithmic number of steps.
    </render-exercise>
  <|folded>
    0-255

    -128~+127

    64bit

    -2^63 ~ +2^63-1

    Kb*8= KB

    1Mb=128KB 1MB=1024KB

    Gb GB

    <\big-table|<tabular|<tformat|<table|<row|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|0>|<cell|>|<cell|-126>>|<row|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|>|<cell|-127>>|<row|<cell|1>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|>|<cell|-128>>|<row|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|>|<cell|0>>|<row|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|>|<cell|1>>|<row|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|0>|<cell|>|<cell|2>>|<row|<cell|0>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|>|<cell|127>>>>>>
      \;
    </big-table>

    <\big-table|<tabular|<tformat|<cwith|1|1|2|2|cell-row-span|1>|<cwith|1|1|2|2|cell-col-span|8>|<cwith|1|1|2|2|cell-halign|c>|<cwith|1|-1|11|11|cell-halign|c>|<cwith|2|2|9|9|cell-background|#afa>|<cwith|3|3|8|8|cell-background|#afa>|<cwith|4|4|7|7|cell-background|#afa>|<cwith|6|6|2|9|cell-background|#faa>|<cwith|7|7|3|9|cell-background|#faa>|<cwith|8|8|4|9|cell-background|#faa>|<cwith|6|6|3|3|cell-background|#afa>|<cwith|7|7|4|4|cell-background|#afa>|<cwith|8|8|5|5|cell-background|#afa>|<cwith|6|6|4|4|cell-background|#aaf>|<cwith|7|7|5|5|cell-background|#aaf>|<cwith|8|8|6|6|cell-background|#aaf>|<cwith|6|6|5|9|cell-background|>|<cwith|7|7|6|9|cell-background|>|<cwith|8|8|7|9|cell-background|>|<cwith|3|3|2|7|cell-background|pastel
    grey>|<cwith|2|2|2|8|cell-background|pastel
    grey>|<cwith|4|4|2|6|cell-background|pastel
    grey>|<cwith|7|7|2|2|cell-background|pastel
    grey>|<cwith|8|8|2|3|cell-background|pastel
    grey>|<table|<row|<cell|>|<cell|\<#4E00\>\<#4E2A\>\<#5B57\>\<#8282\>\<#FF08\>\<#4E8C\>\<#8FDB\>\<#5236\>\<#FF09\>>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|\<#5341\>\<#8FDB\>\<#5236\>>>|<row|<cell|<scm|x>>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|>|<cell|1>>|<row|<cell|<scm|(ash
    x 1)>>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|0>|<cell|>|<cell|2>>|<row|<cell|<scm|(ash
    x 2)>>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|0>|<cell|0>|<cell|>|<cell|4>>|<row|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>>|<row|<cell|y>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|>|<cell|255>>|<row|<cell|<scm|(ash
    y -1)>>|<cell|0>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|>|<cell|127>>|<row|<cell|<scm|(ash
    y -2)>>|<cell|0>|<cell|0>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|1>|<cell|>|<cell|63>>>>>>
      \<#5DE6\>\<#79FB\>\<#64CD\>\<#4F5C\>\<#7B26\><scm|ash>
    </big-table>

    <\big-table|<tabular|<tformat|<cwith|2|2|2|5|cell-background|pastel
    grey>|<cwith|3|3|2|8|cell-background|pastel
    grey>|<cwith|4|4|2|8|cell-background|pastel
    grey>|<cwith|1|1|2|2|cell-row-span|1>|<cwith|1|1|2|2|cell-col-span|8>|<cwith|2|-1|11|11|cell-halign|c>|<cwith|1|1|2|2|cell-halign|c>|<table|<row|<cell|>|<cell|\<#4E8C\>\<#8FDB\>\<#5236\>>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|\<#4E8C\>\<#8FDB\>\<#5236\>>>|<row|<cell|x>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|0>|<cell|0>|<cell|1>|<cell|>|<cell|9>>|<row|<cell|y>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|>|<cell|1>>|<row|<cell|<scm|(logand
    x y)>>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|>|<cell|1>>|<row|<cell|<scm|(logior
    x y)>>|<cell|>|<cell|>|<cell|>|<cell|>|<cell|1>|<cell|0>|<cell|0>|<cell|1>|<cell|>|<cell|9>>|<row|<cell|<scm|(logxor
    x y)>>|<cell|0>|<cell|0>|<cell|0>|<cell|0>|<cell|1>|<cell|0>|<cell|0>|<cell|0>|<cell|>|<cell|8>>>>>>
      \<#903B\>\<#8F91\>\<#4E0E\>\<#64CD\>\<#4F5C\>\<#7B26\>
    </big-table>

    <\session|scheme|default>
      <\unfolded-io|Scheme] >
        (logxor 9 1)
      <|unfolded-io>
        8
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (logxor 0 1)
      <|unfolded-io>
        1
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (logxor 1 0)
      <|unfolded-io>
        1
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (logxor 1 1)
      <|unfolded-io>
        0
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (define (halve x) (ash x -1))
      <|unfolded-io>
        halve
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (halve 10)
      <|unfolded-io>
        5
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (halve 9)
      <|unfolded-io>
        4
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (logand 1 9)
      <|unfolded-io>
        1
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (logand 1 8)
      <|unfolded-io>
        0
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (define (is-odd? x) (= (logand 1 x) 1))
      <|unfolded-io>
        is-odd?
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (define (is-even? x) (= (logand 1 x) 0))
      <|unfolded-io>
        is-even?
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (is-odd? 9)
      <|unfolded-io>
        #t
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (is-even? 10)
      <|unfolded-io>
        #t
      </unfolded-io>

      <\unfolded-io|Scheme] >
        (expt 2 63)
      <|unfolded-io>
        9223372036854776000.0
      </unfolded-io>

      <\unfolded-io|Scheme] >
        9223372036854775808
      <|unfolded-io>
        -9223372036854775808
      </unfolded-io>

      <\input|Scheme] >
        \;
      </input>
    </session>
  </folded>

  <\folded>
    <\render-exercise|Exercise 1.18>
      <label|ex1.18>Using the results of Exercise 1.16 and Exercise 1.17,
      devise a procedure that generates an iterative process for multiplying
      two integers in terms of adding, doubling, and halving and uses a
      logarithmic number of steps.<\footnote>
        This algorithm, which is sometimes known as the \PRussian peasant
        method\Q of multiplication, is ancient. Examples of its use are found
        in the Rhind Papyrus, one of the two oldest mathematical documents in
        existence, written about 1700 <abbr|B.C.> (and copied from an even
        older document) by an Egyptian scribe named A'h-mose.
      </footnote>
    </render-exercise>
  <|folded>
    \;
  </folded>

  <\folded>
    <\render-exercise|Exercise 1.19>
      There is a clever algorithm for computing the Fibonacci numbers in a
      logarithmic number of steps. Recall the transformation of the state
      variables <math|a> and <math|b> in the <code*|fib-iter> process of
      Section 1.2.2: <math|a\<leftarrow\>a+b> and <math|b\<leftarrow\>a>.
      Call this transformation <math|T>, and observe that applying <math|T>
      over and over again <math|n> times, starting with 1 and 0, produces the
      pair <math|<with|mode|text|Fib><around*|(|n+1|)>> and
      <math|<with|mode|text|Fib><around*|(|n|)>>. In other words, the
      Fibonacci numbers are produced by applying <math|T<rsup|n>>, the
      <math|n<rsup|<with|mode|text|th>>> power of the transformation
      <math|T>, starting with the pair (1, 0). Now consider <math|T> to be
      the special case of <math|p=0> and <math|q=1> in a family of
      transformations <math|T<rsub|pq>>, where <math|T<rsub|pq>> transforms
      the pair <math|<around*|(|a,b|)>> according to
      <math|a\<leftarrow\>bq+aq+ap> and <math|b\<leftarrow\>bp+aq>. Show that
      if we apply such a transformation <math|T<rsub|pq>> twice, the effect
      is the same as using a single transformation
      <math|T<rsub|p<rsup|\<prime\>>*q<rsup|\<prime\>>>> of the same form,
      and compute <math|p<rsup|\<prime\>>> and <math|q<rsup|\<prime\>>> in
      terms of <math|p> and <math|q>. This gives us an explicit way to square
      these transformations, and thus we can compute <math|T<rsup|n>> using
      successive squaring, as in the <code*|fast-expt> procedure. Put this
      all together to complete the following procedure, which runs in a
      logarithmic number of steps:<\footnote>
        This exercise was suggested to us by Joe Stoy, based on an example in
        Kaldewaij 1990.
      </footnote>

      <\scm-code>
        (define (fib n)

        \ \ (fib-iter 1 0 0 1 n))

        (define (fib-iter a b p q count)

        \ \ (cond ((= count 0) b)

        \ \ \ \ \ \ \ \ ((even? count)

        \ \ \ \ \ \ \ \ \ (fib-iter a

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ b

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \<less\>??\<gtr\> \ \ \ \ \ ;
        compute p'

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \<less\>??\<gtr\> \ \ \ \ \ ;
        compute q'

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (/ count 2)))

        \ \ \ \ \ \ \ \ (else (fib-iter (+ (* b q) (* a q) (* a p))

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (+ (* b p) (* a q))

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ q

        \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (- count 1)))))
      </scm-code>
    </render-exercise>
  <|folded>
    <\equation*>
      f<around*|(|x|)>=<choice|<tformat|<table|<row|<cell|0>|<cell|,x=0>>|<row|<cell|1>|<cell|,x=1>>|<row|<cell|f<around*|(|x-1|)>+f<around*|(|x-2|)>>|<cell|,x\<gtr\>1>>>>>
    </equation*>

    <\equation*>
      <matrix|<tformat|<table|<row|<cell|a>|<cell|b>>>>>*<matrix|<tformat|<cwith|1|-1|1|1|cell-background|pastel
      green>|<cwith|1|-1|2|2|cell-background|#faa>|<table|<row|<cell|1>|<cell|1>>|<row|<cell|1>|<cell|0>>>>>=<matrix|<tformat|<table|<row|<cell|a+b>|<cell|a>>>>>
    </equation*>

    <\equation*>
      <matrix|<tformat|<table|<row|<cell|f<around*|(|x-1|)>>|<cell|f<around*|(|x-2|)>>>>>>*<matrix|<tformat|<table|<row|<cell|1>|<cell|1>>|<row|<cell|1>|<cell|0>>>>>=<matrix|<tformat|<table|<row|<cell|f<around*|(|x-1|)>+f<around*|(|x-2|)>>|<cell|f<around*|(|x-1|)>>>>>>=<matrix|<tformat|<table|<row|<cell|f<around*|(|x|)>>|<cell|f<around*|(|x-1|)>>>>>>
    </equation*>

    <\eqnarray*>
      <tformat|<table|<row|<cell|<matrix|<tformat|<table|<row|<cell|f<around*|(|n|)>>|<cell|f<around*|(|n-1|)>>>>>>>|<cell|=>|<cell|<matrix|<tformat|<table|<row|<cell|f<around*|(|n-1|)>>|<cell|f<around*|(|n-2|)>>>>>>*<matrix|<tformat|<table|<row|<cell|1>|<cell|1>>|<row|<cell|1>|<cell|0>>>>>>>|<row|<cell|>|<cell|=>|<cell|<matrix|<tformat|<table|<row|<cell|f<around*|(|n-2|)>>|<cell|f<around*|(|n-3|)>>>>>>*<matrix|<tformat|<table|<row|<cell|1>|<cell|1>>|<row|<cell|1>|<cell|0>>>>><rsup|2>>>|<row|<cell|>|<cell|=>|<cell|<matrix|<tformat|<table|<row|<cell|f<around*|(|1|)>>|<cell|f<around*|(|0|)>>>>>>*<matrix|<tformat|<table|<row|<cell|1>|<cell|1>>|<row|<cell|1>|<cell|0>>>>><rsup|n-1>>>|<row|<cell|>|<cell|=>|<cell|<matrix|<tformat|<table|<row|<cell|1>|<cell|0>>>>>*<matrix|<tformat|<table|<row|<cell|1>|<cell|1>>|<row|<cell|1>|<cell|0>>>>><rsup|n-1>>>>>
    </eqnarray*>

    <\session|octave|default>
      <\unfolded-io>
        \<gtr\>\<gtr\>\ 
      <|unfolded-io>
        [1 1]
      <|unfolded-io>
        <with|mode|math|math-display|true|<matrix|<tformat|<table|<row|<cell|<with|mode|math|1>>|<cell|<with|mode|math|1>>>>>>>
      </unfolded-io>

      <\unfolded-io>
        \<gtr\>\<gtr\>\ 
      <|unfolded-io>
        [1 1; 1 0]
      <|unfolded-io>
        <with|mode|math|math-display|true|<matrix|<tformat|<table|<row|<cell|<with|mode|math|1>>|<cell|<with|mode|math|1>>>|<row|<cell|<with|mode|math|1>>|<cell|<with|mode|math|0.0>>>>>>>
      </unfolded-io>

      <\input>
        \<gtr\>\<gtr\>\ 
      <|input>
        \;
      </input>
    </session>

    <\session|octave|default>
      <\output>
        GNU Octave (8.3.0) Session in GNU TeXmacs

        Welcome to star and fork it at https://github.com/texmacs/octave
      </output>

      <\unfolded-io>
        \<gtr\>\<gtr\>\ 
      <|unfolded-io>
        [1 1; 1 0]
      <|unfolded-io>
        <with|mode|math|math-display|true|<matrix|<tformat|<table|<row|<cell|<with|mode|math|1>>|<cell|<with|mode|math|1>>>|<row|<cell|<with|mode|math|1>>|<cell|<with|mode|math|0.0>>>>>>>
      </unfolded-io>

      <\unfolded-io>
        \<gtr\>\<gtr\>\ 
      <|unfolded-io>
        [1 0] * [1 1; 1 0]; # f(2), f(1)
      <|unfolded-io>
        <with|mode|math|math-display|true|<matrix|<tformat|<table|<row|<cell|<with|mode|math|1>>|<cell|<with|mode|math|1>>>>>>>
      </unfolded-io>

      <\unfolded-io>
        \<gtr\>\<gtr\>\ 
      <|unfolded-io>
        [1 0] * [1 1; 1 0]^2; # f(3), f(2)
      <|unfolded-io>
        <with|mode|math|math-display|true|<matrix|<tformat|<table|<row|<cell|<with|mode|math|2>>|<cell|<with|mode|math|1>>>>>>>
      </unfolded-io>

      <\unfolded-io>
        \<gtr\>\<gtr\>\ 
      <|unfolded-io>
        [1 0]*[1 1; 1 0]^10; # f(11), f(10)
      <|unfolded-io>
        <with|mode|math|math-display|true|<matrix|<tformat|<table|<row|<cell|<with|mode|math|89>>|<cell|<with|mode|math|55>>>>>>>
      </unfolded-io>

      <\unfolded-io>
        \<gtr\>\<gtr\>\ 
      <|unfolded-io>
        [1 1; 1 0]^5 * [1 1; 1 0]^5
      <|unfolded-io>
        <with|mode|math|math-display|true|<matrix|<tformat|<table|<row|<cell|<with|mode|math|89>>|<cell|<with|mode|math|55>>>|<row|<cell|<with|mode|math|55>>|<cell|<with|mode|math|34>>>>>>>
      </unfolded-io>

      <\input>
        \<gtr\>\<gtr\>\ 
      <|input>
        \;
      </input>
    </session>

    <\equation*>
      <matrix|<tformat|<table|<row|<cell|a>|<cell|b>>>>>*T<rsub|pq>=<matrix|<tformat|<table|<row|<cell|bq+aq+ap>|<cell|bp+aq>>>>>
    </equation*>

    <\equation*>
      T<rsub|pq>=<matrix|<tformat|<table|<row|<cell|q+p>|<cell|q>>|<row|<cell|q>|<cell|p>>>>>
    </equation*>
  </folded>

  <\folded>
    <\render-exercise|Exercise 1.20>
      The process that a procedure generates is of course dependent on the
      rules used by the interpreter. As an example, consider the iterative
      <code*|gcd> procedure given above. Suppose we were to interpret this
      procedure using normal-order evaluation, as discussed in Section 1.1.5.
      (The normal-order-evaluation rule for <code*|if> is described in
      Exercise 1.5.) Using the substitution method (for normal order),
      illustrate the process generated in evaluating <code*|(gcd 206 40)> and
      indicate the <code*|remainder> operations that are actually performed.
      How many <code*|remainder> operations are actually performed in the
      normal-order evaluation of <code*|(gcd 206 40)>? In the
      applicative-order evaluation?
    </render-exercise>
  <|folded>
    \;
  </folded>

  <\render-exercise|Exercise 1.21>
    Use the <scm|smallest-divisor> procedure to find the smallest divisor of
    each of the following numbers: 199, 1999, 19999.
  </render-exercise>

  <\render-exercise|Exercise 1.22>
    <label|ex1.22>Most Lisp implementations include a primitive called
    <code*|runtime> that returns an integer that specifies the amount of time
    the system has been running (measured, for example, in microseconds). The
    following <code*|timed-prime-test> procedure, when called with an integer
    <math|n>, prints <math|n> and checks to see if <math|n> is prime. If
    <math|n> is prime, the procedure prints three asterisks followed by the
    amount of time used in performing the test.

    <\scm-code>
      (define (timed-prime-test n)

      \ \ (newline)

      \ \ (display n)

      \ \ (start-prime-test n (runtime)))

      (define (start-prime-test n start-time)

      \ \ (if (prime? n)

      \ \ \ \ \ \ (report-prime (- (runtime) start-time))))

      (define (report-prime elapsed-time)

      \ \ (display " *** ")

      \ \ (display elapsed-time))
    </scm-code>

    Using this procedure, write a procedure <code*|search-for-primes> that
    checks the primality of consecutive odd integers in a specified range.
    Use your procedure to find the three smallest primes larger than 1000;
    larger than 10,000; larger than 100,000; larger than 1,000,000. Note the
    time needed to test each prime. Since the testing algorithm has order of
    growth of <math|\<Theta\><around*|(|<sqrt|n>|)>>, you should expect that
    testing for primes around 10,000 should take about <math|<sqrt|10>> times
    as long as testing for primes around 1000. Do your timing data bear this
    out? How well do the data for 100,000 and 1,000,000 support the
    <math|\<Theta\><around*|(|<sqrt|n>|)>> prediction? Is your result
    compatible with the notion that programs on your machine run in time
    proportional to the number of steps required for the computation?
  </render-exercise>

  <\render-exercise|Exercise 1.23>
    The <code*|smallest-divisor> procedure shown at the start of this section
    does lots of needless testing: After it checks to see if the number is
    divisible by 2 there is no point in checking to see if it is divisible by
    any larger even numbers. This suggests that the values used for
    <code*|test-divisor> should not be 2, 3, 4, 5, 6, \<ldots\>, but rather
    2, 3, 5, 7, 9, \<ldots\>. To implement this change, define a procedure
    <code*|next> that returns 3 if its input is equal to 2 and otherwise
    returns its input plus 2. Modify the <code*|smallest-divisor> procedure
    to use <code*|(next test-divisor)> instead of <code*|(+ test-divisor 1)>.
    With <code*|timed-prime-test> incorporating this modified version of
    <code*|smallest-divisor>, run the test for each of the 12 primes found in
    Exercise <reference|ex1.22>. Since this modification halves the number of
    test steps, you should expect it to run about twice as fast. Is this
    expectation confirmed? If not, what is the observed ratio of the speeds
    of the two algorithms, and how do you explain the fact that it is
    different from 2?
  </render-exercise>

  <\render-exercise|Exercise 1.24>
    <label|ex1.24>Modify the <code*|timed-prime-test> procedure of Exercise
    1.22 to use <code*|fast-prime?> (the Fermat method), and test each of the
    12 primes you found in that exercise. Since the Fermat test has
    <math|\<Theta\><around*|(|log\<nospace\>n|)>> growth, how would you
    expect the time to test primes near 1,000,000 to compare with the time
    needed to test primes near 1000? Do your data bear this out? Can you
    explain any discrepancy you find?
  </render-exercise>

  <\render-exercise|Exercise 1.25>
    <label|ex1.25>Alyssa P. Hacker complains that we went to a lot of extra
    work in writing <code*|expmod>. After all, she says, since we already
    know how to compute exponentials, we could have simply written

    <\scm-code>
      (define (expmod base exp m)

      \ \ (remainder (fast-expt base exp) m))
    </scm-code>

    Is she correct? Would this procedure serve as well for our fast prime
    tester? Explain.
  </render-exercise>

  <\render-exercise|Exercise 1.26>
    Louis Reasoner is having great difficulty doing Exercise
    <reference|ex1.24>. His <code*|fast-prime?> test seems to run more slowly
    than his <code*|prime?> test. Louis calls his friend Eva Lu Ator over to
    help. When they examine Louis's code, they find that he has rewritten the
    <code*|expmod> procedure to use an explicit multiplication, rather than
    calling <code*|square>:

    <\scm-code>
      (define (expmod base exp m)

      \ \ (cond ((= exp 0) 1)

      \ \ \ \ \ \ \ \ ((even? exp)

      \ \ \ \ \ \ \ \ \ (remainder (* (expmod base (/ exp 2) m)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (expmod base (/ exp 2)
      m))

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m))

      \ \ \ \ \ \ \ \ (else

      \ \ \ \ \ \ \ \ \ (remainder (* base (expmod base (- exp 1) m))

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m))))
    </scm-code>

    \PI don't see what difference that could make,\Q says Louis.
    \PI<nbsp>do.\Q says Eva. \PBy writing the procedure like that, you have
    transformed the <math|\<Theta\><around*|(|log\<nospace\>n|)>> process
    into a <math|\<Theta\><around*|(|n|)>> process.\Q Explain.
  </render-exercise>

  <\render-exercise|Exercise 1.27>
    Demonstrate that the Carmichael numbers listed in Footnote 1.47 really do
    fool the Fermat test. That is, write a procedure that takes an integer
    <math|n> and tests whether <math|a<rsup|n>> is congruent to <math|a>
    modulo <math|n> for every <math|a\<less\>n>, and try your procedure on
    the given Carmichael numbers.
  </render-exercise>

  <\render-exercise|Exercise 1.28>
    <label|ex1.28>One variant of the Fermat test that cannot be fooled is
    called the <em|Miller-Rabin test><index|Miller-Rabin test> (Miller 1976;
    Rabin 1980). This starts from an alternate form of Fermat's Little
    Theorem, which states that if <math|n> is a prime number and <math|a> is
    any positive integer less than <math|n>, then <math|a> raised to the
    <math|<around*|(|n-1|)>>-st power is congruent to 1 modulo <math|n>. To
    test the primality of a number <math|n> by the Miller-Rabin test, we pick
    a random number <math|a\<less\>n> and raise <math|a> to the
    <math|<around*|(|n-1|)>>-st power modulo <math|n> using the
    <code*|expmod> procedure. However, whenever we perform the squaring step
    in <code*|expmod>, we check to see if we have discovered a \Pnontrivial
    square root of 1 modulo <math|n>,\Q that is, a number not equal to 1 or
    <math|n-1> whose square is equal to 1 modulo <math|n>. It is possible to
    prove that if such a nontrivial square root of 1 exists, then <math|n> is
    not prime. It is also possible to prove that if <math|n> is an odd number
    that is not prime, then, for at least half the numbers <math|a\<less\>n>,
    computing <math|a<rsup|n-1>> in this way will reveal a nontrivial square
    root of 1 modulo <math|n>. (This is why the Miller-Rabin test cannot be
    fooled.) Modify the <code*|expmod> procedure to signal if it discovers a
    nontrivial square root of 1, and use this to implement the Miller-Rabin
    test with a procedure analogous to <code*|fermat-test>. Check your
    procedure by testing various known primes and non-primes. Hint: One
    convenient way to make <code*|expmod> signal is to have it return 0.
  </render-exercise>
</body>

<\initial>
  <\collection>
    <associate|page-screen-margin|false>
  </collection>
</initial>

<\references>
  <\collection>
    <associate|auto-1|<tuple|invariant quantity|?>>
    <associate|auto-2|<tuple|1|?>>
    <associate|auto-3|<tuple|2|?>>
    <associate|auto-4|<tuple|3|?>>
    <associate|auto-5|<tuple|Miller-Rabin test|?>>
    <associate|ex1.16|<tuple|b|?>>
    <associate|ex1.17|<tuple|invariant quantity|?>>
    <associate|ex1.18|<tuple|3|?>>
    <associate|ex1.22|<tuple|2|?>>
    <associate|ex1.24|<tuple|2|?>>
    <associate|ex1.25|<tuple|2|?>>
    <associate|ex1.28|<tuple|2|?>>
    <associate|footnote-1|<tuple|1|?>>
    <associate|footnote-2|<tuple|2|?>>
    <associate|footnr-1|<tuple|1|?>>
    <associate|footnr-2|<tuple|2|?>>
    <associate|index-invariant-quantity|<tuple|b|?>>
  </collection>
</references>

<\auxiliary>
  <\collection>
    <\associate|idx>
      <tuple|<tuple|invariant quantity>|<pageref|auto-1>>

      <tuple|<tuple|Miller-Rabin test>|<pageref|auto-5>>
    </associate>
    <\associate|table>
      <tuple|normal|<\surround|<hidden-binding|<tuple>|1>|>
        \;
      </surround>|<pageref|auto-2>>

      <tuple|normal|<\surround|<hidden-binding|<tuple>|2>|>
        \<#5DE6\>\<#79FB\>\<#64CD\>\<#4F5C\>\<#7B26\><with|mode|<quote|prog>|prog-language|<quote|scheme>|font-family|<quote|rm>|ash>
      </surround>|<pageref|auto-3>>

      <tuple|normal|<\surround|<hidden-binding|<tuple>|3>|>
        \<#903B\>\<#8F91\>\<#4E0E\>\<#64CD\>\<#4F5C\>\<#7B26\>
      </surround>|<pageref|auto-4>>
    </associate>
  </collection>
</auxiliary>