[plt-scheme] HtDP 27.3.2 and 27.3.4

From: David Yrueta (dyrueta at gmail.com)
Date: Sat Jul 4 13:38:47 EDT 2009

Thank you for the response, but I don't really get it....

For (poly 3 4) I find arguments:

I recast this as a table to see if I could figure out what you're driving at:

Step     left          (f left)               right     (f right)
    mid           (f mid)               diff
1          3             -1                    4         0
      3.5             -.75                 -1
2          3.5          -.75                 4          0
    3.75           -.4375              -.5
3          3.75        -.4375              4          0
  3.875         -.234375          -.25
4          3.875      -.234375          4          0
3.9375        -.1209...          -.125
5          3.9375    -.12109...         4          0
3.96875      -.0615...          -.0625
...

I can see that the value of 'right' remains constant, since with every
call (<= (f mid) 0 (f right)) evaluates to true. But isn't that
different from saying, as the exercise does, that with each midpoint
(f mid) is computed twice?

Thanks!

On Sat, Jul 4, 2009 at 3:37 AM, Jos Koot<jos.koot at telefonica.net> wrote:
> With TOLERANCE 1/100 I find that poly is called with the following
> arguments:
> 9/2
> 6
> 15/4
> 9/2
> 33/8
> 9/2
> 63/16
> 33/8
> 129/32
> 33/8
> 255/64
> 129/32
> 513/128
> 129/32
> 1023/256
> 513/128
> 2049/512
> 513/128
>
> For (poly 3 4) I find arguments:
> 7/2
> 4
> 15/4
> 4
> 31/8
> 4
> 63/16
> 4
> 127/32
> 4
> 255/64
> 4
> 511/128
> 4
> Poly is called 7 times with the same argument 4.
> Can you now find out why f is called with the same argument more than once
> (how to avoid that?
> Jos
>
> ----- Original Message ----- From: "David Yrueta" <dyrueta at gmail.com>
> To: "PLT-Scheme Mailing List" <plt-scheme at list.cs.brown.edu>
> Sent: Saturday, July 04, 2009 7:34 AM
> Subject: [plt-scheme] HtDP 27.3.2 and 27.3.4
>
>
>> Hi All --
>>
>> Questions for both exercises refer to the function "find-root" below:
>>
>> ;; find-root : (number  ->  number) number number  ->  number
>> ;; to determine a number R such that f has a
>> ;; root between R and (+ R TOLERANCE)
>> ;;
>> ;; ASSUMPTION: f is continuous and monotonic
>> (define (find-root f left right)
>>  (cond
>>   [(<= (- right left) TOLERANCE) left]
>>   [else
>>     (local ((define mid (/ (+ left right) 2)))
>> (cond
>>  [(<= (f mid) 0 (f right))
>>          (find-root f mid right)]
>>  [else
>>          (find-root f left mid)]))]))
>>
>> ;; poly : number  ->  number
>> (define (poly x)
>> (* (- x 2) (- x 4)))
>>
>> HtDP exercise 27.3.2:
>>
>> "Use poly from 27.3.1 to test find-root. Experiment with different
>> values for TOLERANCE. Use the strategy of section 17.8 to formulate
>> the tests as boolean-valued expressions."
>>
>> Are these tests meant to take place inside or outside the body of
>> "find-root." In other words, are they conditional expressions inside
>> "find-root"?  If not, how are these tests different from a typical
>> "check-expect?"
>>
>> (check-expect (find-root poly 3 6) 3.75)
>>
>> HtDP exercise 27.3.4
>>
>> "For every midpoint m, except for the last one, the function find-root
>> needs to determine the value of (f m) twice. Validate this claim for
>> one example with a hand-evaluation."
>>
>> For the life of me, I don't see (f m) computed twice for every
>> midpoint.  "Mid" is obviously computed twice, but I only see "(f mid)"
>> computed once per call.  Am I missing something totally obvious?
>>
>> Thanks!
>> Dave Yrueta
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>
>
>


Posted on the users mailing list.