Exercise 1.15 shows an interesting procedure for computing the sine of an angle (in radians) by combined use of the approximation sin x ~ x (if x is sufficiently small) and the trigonometric identity
sin r = 3 * sin(r/3) - 4 * sin3(r/3)
which is used to reduce the argument of sin. The code provided implements the computation:
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
The exercise goes on to ask the following two questions:
a. How many times is the procedure
p applied when (sine 12.15) is evaluated?b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the
sine procedure when (sine a) is evaluated?Looking at how the process executes will help us answer both questions.
(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))
(p (p (p (p 0.1495))))
(p (p (p 0.4351345505)))
(p (p 0.9758465331678772))
(p -0.7895631144708228)
-0.39980345741334
As long as the angle stays greater than 0.1, the process keeps recursing. There are five calls to the procedure
p before that happens.Complexity
The
sine procedure is recursive, but it makes only a single call to itself, so it isn't tree recursive and its complexity isn't nearly as bad as some of the procedures we've seen in previous exercises. The complexity for this procedure in both space and number of steps is actually better than linear.Space - The amount of space required by this procedure would increase linearly as the input size is tripled. Only the calls to procedure
p are deferred, and we can triple the size of the input before an additional call would be made.Number of steps - It's also easy to see that we can triple the value of the starting input angle and only one more step would be required by this procedure.
The complexity of both the space and the number of steps required by this procedure can be described as O(log n).
Related:
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.
8 comments:
Hi.
I was interested in your comments about this exercise. I can see how the number of steps would grow at O(log n), but to me it seems the space expands at O(n). It seemed to me you suggested this when you said, "The amount of space required by this procedure would increase linearly as the input size is tripled."
The reason I say this is with a logarithmic curve I'm used to seeing a "hump" or "spike" on the left side of it. I could see this with the number of steps, but not with the amount of space. I realize that the space with this algorithm grows very gradually, but couldn't this be explained by the linear function having a very shallow slope?
Thanks.
Mark,
This is a very good question. I know because it's taken me awhile to come up with an answer that's not just repeating what I said originally. :)
The way you can tell that the space is not increasing linearly is by looking at the operation you need to apply to the space as you increase the input size by a given operation. For example, if you add to the input size, what operator do you have to apply to the space? If you keep adding one to the input size, the space required only increases by one every so often. The more you add to the input, the less often the space increases. This tells me that the growth is less than linear. If it was linear, then the space would increase at regular intervals.
If you multiply the input (by three in this case), then the space required increases by one at every step. The space (or time) growing by addition as the input grows by multiplication is the hallmark of logarithmic growth.
I hope that clears things up. If not, let me know. I might have to write a separate post on order of growth, since I think it's a very important topic, and not at all intuitive to most people.
Thanks for the great question.
Hi Bill.
Thanks for your response. I see what you mean about the pattern. This is something that made this section of SICP really hard for me: being able to recognize a pattern of behavior and then map it to a function. As I did these exercises I found I had very little knowledge of how to do this. For example with Exercise 1.14 (measuring the Counting Change algorithm) I had the darnedest time figuring what the Big-O function was. I tried collecting data points by walking through the algorithm manually, then counting the steps and the space, and plotting a graph to see what I could glean from that. If I went incrementally, parts of the graph looked linear, but every once in a while it would flatten out, and then jump up. Each jump, after an interval, was bigger and bigger. I started making bigger jumps with the input to try to see a larger pattern, and it was starting to look exponential, but what was the exponent? I struggled with curve fitting for a while to see if I could get something close. The book seemed to suggest this approach:
"We say that R(n) has order of growth (theta)(f(n)), written R(n) = (theta)(f(n))..., if there are positive constants k(1) and k(2) independent of n such that k(1)f(n) <= R(n) <= k(2)f(n) for any sufficiently large value of n. (In other words, for large n, the value R(n) is sandwiched between k(1)f(n) and k(2)f(n)."
I read your explanation for this Big-O function, and your method was better than mine. I ended up getting the wrong answer. It appeared to me that instead of looking at data points, you looked at patterns of behavior, and extrapolated the function from the patterns. After seeing that I felt like slapping my forehead. "Why didn't I think of this?" I encountered the same patterns you did, but I didn't interpret them the same way. A problem I identified is when one got into the larger inputs it was challenging to try to build the trees on paper. I'd run out of space, and have to split out subtrees on different pages. Had I been able to see a large tree all in one place maybe I would've been able to see it, but I'm not sure.
When I had CS in college we covered orders of growth, but what I remember is we only spent a little time identifying functions. I don't remember understanding it then either.
Maybe an explanation just on identifying functions from arithmetic patterns would help with understanding this. That's something I never got practice in from my math education. However I felt as though I could understand your method for getting the growth function for the Counting Change algorithm.
Your answer to the question was quite useful in understanding the algorithm, however, I suspect that you are answering a different question from what was printed. b) asked for the growth in space and number of steps as a function of a, which was the number of times p was executed, and not as a function of the input to p. The answer could be then easily given as O(n) and space at O(1) (I hope). If I am understanding your answer correctly, the O(log n) from your answer is due to the 0.1 "sufficiently small" error, which feels somewhat ungeneralizable (and thus unusual in this question) as it is a tradeoff between time, space and fractional error. The answer you gave helped give me a different perspective though.
Josiah,
I think part b is asking for he growth in space and number of steps as a function the input to p. When the question says "as a function of a" I don't think it's referring to part a of the question, but the input a to (sine a).
Whoops! Originally didn't see it that way. Thanks for your reply.
FWIW, I reached the same conclusion as you, however, by a different approach. I wonder if it is equally valid. First, recall that space refers to the depth of a tree. The depth of this tree is determined, primarily, by deferred applications of p. Specifically, the total depth of the tree is twice the depth it takes to reach the point where one begins evaluating p. This point is reached when a/3^x <= 0.1. The depth is then the least integer greater than twice this amount. Solving for a, one obtains an expression proportional to ln(a) (or log(a)). Second, the number of steps is, I believe, the same as the depth of the tree. Each step, each node, is determined by the application of a single procedure. This means each line is a node. Thus, the number of steps is also proportional to ln(a).
Hi, I think I can help with some people's doubts and/or want to see things more mathematically,
so suppose we have to calculate sine a and say it takes n iterations to bring it down to less than 0.1, then in each step since a is divided by 3 then a/(3^n) <= 0.5
We can solve this with only the equality considered, given that we only want a qualitative relation between a and n.
Post a Comment