Justin Does SICP

Other Friendly
,
81

This table and chart reflect the number of computational steps (reflected in calls to cc) that result when invoking count-change with a given input

input value to count-change calls to cc
0 1
1 12
2 13
3 15
4 17
5 19
6 25
7 29
8 33
9 37
10 41
11 55
12 63

looks pretty linear to me though with occasionally jumps. I’m not sure if the jumps matter for Order of Growth analysis

Exercise 1-14.numbers 2021-06-08 17-11-27

82

and the increase in max depth (which, per SICP, is an indicator of the space/memory required when analyzing a tree-recursive process like count-change) is so linear it’s a straight line

input value to count-change
 maximum depth of calls for cc procedure
0 0
1 5
2 6
3 7
4 8
5 9
6 10
7 11
8 12
9 13
10 14
11 15
12 16

Exercise 1-14.numbers 2021-06-08 17-21-05

83

btw i was able to paste the table straight from Numbers and it worked

84

there’s a pattern in the increases of calls to for higher inputs. Like it starts going up by 1, then by 2, then by 4, and further increases after that.

possibly the pattern of increase would be more clear if i looked at all the computational steps instead of just focusing on cc. i wanted to try that first cuz i wanted to try something simpler. the increase in space seems linear at least

85

looked at some more data. count-change's number of steps definitely seems to increase massively as the input number increases, though I’m still not confident how to characterize that increase

input value to count-change
 calls to cc calls to first-denomination calls to cc + first-denomination
0 1 0 1
1 12 5 17
2 13 6 19
3 15 7 22
4 17 8 25
5 19 9 28
6 25 12 37
7 29 14 43
8 33 16 49
9 37 18 55
10 41 20 61
11 55 23 78
12 63 31 94
20 151 75 226
30 391 195 586
100 15499 7749 23248
86

Still not feeling confident/clear re: exercise 1.14. Gonna try reading this and maybe some other stuff next How to compute Time Complexity or Order of Growth of any program | Rookie's Lab

87

Wound up looking at some answers for 1.14.
Been looking at this one and trying to figure it out:

In particular I’ve been trying to figure out the section with the equations that starts with:

T(n,2);=\frac n5+1+;\sum_{i=0}^{n/5}T(n-5i,1)

I looked up Sigma notation and I think I get the idea but I’m still having trouble following all the steps in that solution.

88

So far my impression is that SICP seems kinda like a math textbook that uses computer science examples rather than the other way around. I know that’s not literally true but that’s how it seems from the perspective of my current skills. (Maybe it’s kinda like, if you don’t know English well then any random English book can feel like a test of vocab/grammar/comprehension)

I’m finding that even reading other people’s solutions to problems seems to have mathematical prerequisites I don’t meet and I’m getting stuck cuz of that. It’s one thing to not be able to come up with a solution on my own but if I’m struggling to understand answers then that seems like a big problem.

It’s possible that I should work on improving my math skills. Idk.

89

you could try skipping the most mathy problems

1 Like
90

New post

91

Hint/help request:

Here is some of Section 1.2.4 as context:

image
image1590×1776 264 KB

Then it asks the following:

Exercise 1.16: Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (b^{n/2})^2=(b^2)^{n/2}, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product ab^n is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

I was a bit confused as to what they were asking for here at first. I found something online which said “The goal is to use the algorithm of fast-exp […] but avoid using the recursive call as an argument to something else.”

Here is a partially pseudocode solution (cuz there is a step missing)

(define (new-expt b n)
  (new-expt-iter b n a))


(define (new-expt-iter b n a)
  (cond ((= n 0)
         a)
        ((even? n)
         (new-expt-iter b (/ n 2)(MAGIC GOES HERE?)))
        (else
         (new-expt-iter b (- n 1)(* b a)))))

Assuming I am vaguely on the right track, I think what I am missing is how to “define the state transformation in such a way that the product ab^n is unchanged from state to state.”

92

I wound up starting to read someone else’s answer and now see the problem.

I got stuck on wanting to try to solve the problem without changing the base value b. I think my issue was that I read this part of the hint…

Using the observation that (b^{n/2})^2=(b^2)^{n/2}, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product ab^n is unchanged from state to state.

…and for some reason I decided that the base needed to remain constant. I didn’t apply this idea to any of the other values, though.

Anyways here’s the answer:


(define (new-expt b n)
  (new-expt-iter b n 1))

(define (new-expt-iter b n a)
  (cond ((= n 0)
         a)
        ((even? n)
         (new-expt-iter (* b b)(/ n 2) a))
        (else
         (new-expt-iter b (- n 1)(* b a)))))

I managed to avoid spending lots of time ineffectively spinning my wheels on this. I came back to it a couple of times over some period of time and tried thinking about it some before finally deciding to look at the answer. I’ve also been working on some stuff I think is related (like trying to make sure I’ve actually mastered the Simply Scheme material and working on my basic math skills)