[plt-scheme] HtDP 27.3.2 and 27.3.4

From: Jos Koot (jos.koot at telefonica.net)
Date: Sat Jul 4 21:39:10 EDT 2009

A better example is (find-root poly 2 3)
The first midpoint is 5/2 and poly is called twice with this argument. The same happens to other midpoints in this case.
I agree that the midpoint is not always passed twice to poly.
Sorry to have given a wrong example.
Nevertheless there is a solution that avoids poly to be called twice with the same argument (whether left, right or mid) I would go 
for a solution that never calls poly twice with the same argument (what if given an f that takes one hour to compute?)
I could read the table. Nevertheless thanks for sending the formatted table.
Sorry for the delay of my responce. I was visiting a grand feast a few hundred kilometers away from wher I live. Just got home, 
local time 03.15.
Jos

----- Original Message ----- 
From: "David Yrueta" <dyrueta at gmail.com>
To: "Jos Koot" <jos.koot at telefonica.net>
Cc: "PLT-Scheme Mailing List" <plt-scheme at list.cs.brown.edu>
Sent: Saturday, July 04, 2009 7:38 PM
Subject: Re: [plt-scheme] HtDP 27.3.2 and 27.3.4


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.