Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

jolisper

  • 2 years ago

I was working on the solution of the exercise 1.6 of the SICP book when I saw two different behaviors when I run the code depending on the numbers that I used. If I use natural numbers when I call the sqrt-iter procedure the interpreter just never stop but when I force the decimal division using float-point numbers the interpreter responds: Aborting!: maximum recursion depth exceeded. Does anyone know the reason for the different behavior? I made a gist with my answer to help anyone that wants to run the code, just copy & paste: http://bit.ly/Qv1wru

  • This Question is Closed
  1. jagan
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    this problem is similar to this question asked at berkeley. I haven't been able to find the ans myself. http://inst.eecs.berkeley.edu/~cs61AS/fa12/lab/0.1.html Exercise 4.

  2. jagan
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i found ans to my question.

  3. jolisper
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Hi @jagan, I read the exercise 4 and is true that is a similar exercise. In fact is like the exercise 1.5. But my question is aimed to the different behavior that the interpreter shows when you use natural numbers or decimal numbers. I wrote a note in my gist to point that. About the answer of the exercise I think that the key is the different evaluation of the primitive "if" and the "new-if" procedure. The primitive "if" ensure that the good-enough? procedure is called because the predicate part is evaluated first, so the end condition is reached at some point. But in the "new-if" implementation, because the alternative part (or else-clause) is evaluated first and in this part is there a recursive call to the sqrt-iter procedure this causes an infinitive loop. That is my better answer right now, I don't know if its totally correct. Please share your answer.

  4. jagan
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    for exercise 4 : if construct in scheme evaluate conditionally,take the below example if (condition ) ( evaluate 1) (evaluate 2)) if condition is true then expression evalute1 is evaluated but evaluate2 is not -evaluated similarly if condition is false then expression evalute2 is evaluated but evaluate1 is not -evaluated. (define (infinite-loop) (infinite-loop)) is a recursive procedure call with no argument . If you call this method it will keep executing in an infinite loop. (if (= 3 6) (infinite-loop) (/ 4 2)) But the above if statement executed because condition is false and infinite loop procedure is not called, only last statement (/ 4 2) is executed.So it doesn't go into a infinite loop. But new definition of IF is called the (define (new-if test then-case else-case) (if test then-case else-case)) call to new-if (new-if (= 3 6) (infinite-loop) (/ 4 2)) , all sub expression will be evaluated according to substitution model of procedure call. So before procedure is called all sub expression in procedure call will be evaluated and (= 36) evaluates to false (infinite-loop) - procedure will be called which will get stuck in infinite loop so in this new-if construct both then and else case are executed before they are passed to the function . Where as in scheme if construct only one of the case executes based on the test condition. I don't know the reason for your code behaviors. I will go through this section 1.6 SICP if I get something will post it here.

  5. jolisper
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    It's a well explained response, thanks for sharing ;-)

  6. ajiwo
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    did you miss the `abs` part of the `good-enough?` procedure? i think it has something to do with exercise 1.5: about how the interpreter evaluate the combination, applicative vs normal order. 'just never stop' and 'max recursion depth exceeded': it looks like the interpreter uses the applicative order. it tried to resolve all the subexpressions (operators and arguments) before applying the arguments to the operator. the mathematical procedures (+,-,/,*, etc) behaviour depends on how the interpreter treat numbers. i treat this as a matter of convention if i expect 0.5 from 1/2 i must multiply its result with a float eg: 1.0 (/ 1 2) ==> 1/2 (* 1.0 (/ 1 2)) ==> 0.5

  7. jolisper
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Thanks @ajiwo you are right! I miss the `abs` part in the `good-enough?` procedure. I corrected in the gist. But the behavior is the same, obviously. As you say, those different behaviors depends on the interpreter internals. I will run the code on a different implementation to see if its change.

  8. azka.niazi
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you pointed out very correctly @jolisper. I just tried the code on two different interpreters (DrScheme and MIT-GNU Scheme). At least on these two, the behavior is the similar to what you pointed out. I think it doesn't depend on the interpreter. It most probably has to do with floating point arithmetic. In a machine, floating point numbers are stored in a different format. There is an IEEE standard notation. So, I think, and I may be wrong: When you give a natural number x as an argument to sqrt-iter, it will try to computer a y such that y^2 = x (with some error tolerance)... Mathematically, we know that: if y^2 = x and x is a natural number -> y will be less than x so, in whatever format our machine (the hardware) stores the number x, if it can store x, it can also store y (because y < x). our machine will not run out of space. but floating numbers is a different story. there is this fractional part and exponent story (should refer to any article on floating point arithmetic). if i try to manually visualize the computations which might take place for a floating point number...then for any computation that wont stop...the machine is more likely to run out of space. The idea is still vague. Because then rises another question. when we try to evaluate (sqrt-iter 1 2), after the first iteration the variable guess (inside the definition of sqrt-iter) will not be a natural number any more. Because we will improve our guess by averaging by 2 but then, i must point out that neither it is a floating point number - it is FRACTION and not a floating point number. i mean, there is a difference between (/ 1 2) and (/ 1 2.) in scheme. the latter gives the answer .5 unlike 1/2 for the first expression. So, if you change the definition for the average procedure to (define (average x y) (/ (+ x y) 2.)) it will behave similarly for natural numbers and floating numbers. (because after the first iteration our guess will be a floating point number always irrespective of what we had before). Hope that answer some part of the question.

  9. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Ask a Question
Find more explanations on OpenStudy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.