Justin Does SICP

It’s the transition from first line to second line there that I’m not getting.

I think I’m having a similar issue with your solution:

There are some missing lower level steps or something that I’m not following.

I do follow the stuff about \psi and \phi btw. I don’t think that’s the issue (could be wrong tho ofc). My guess is it’s something related to factoring or properties of exponents that’s intuitive enough for other people such that they don’t think it’s worth mentioning but that I need spelled out. Or could be that I’m just like misreading what’s happening.

I don’t expect unlimited help figuring this out btw … saying I’m still confused is partially about my own effort to practice honesty about such things.

Okay, so in Anne’s example (first image) the only thing that’s happening is factorization of the middle two terms. In my example (second image) there is both factorization and slight rearrangement going on. It might be simpler to understand like this:

Consider: \phi^n + \phi^{n-1}\psi - \phi\psi^{n-1} - \psi^n

Let m = n - 2, a = \phi, b = \psi. Thus:

\begin{align} & = \phi^n + \phi^{n-1}\psi - \phi\psi^{n-1} - \psi^n \\ \text{(sub $a$ and $b$)} \;\;\;\;\; & = a^n + a^{n-1}b - ab^{n-1} - b^n \\ \text{(sub $n = m + 2$)} \;\;\;\;\; & = a^{m + 2} + a^{m + 1}b - ab^{m + 1} - b^{m + 2} \tag{1} \\ \text{(factorize out $(ab)$ where possible)} \;\;\;\;\; & = a^{m + 2} + a^{m}(ab) - (ab)b^{m} - b^{m + 2} \tag{2} \\ \text{(sub $m=n-2$)} \;\;\;\;\; & = a^{n} + a^{n-2}(ab) - (ab)b^{n-2} - b^{n} \\ \text{(sub $\phi$ and $\psi$)} \;\;\;\;\; & = \phi^n + \phi^{n-2}(\phi\psi) - (\phi\psi)\psi^{n-2} - \psi^n \end{align}

The point of all the substitution stuff is that I guess it’ll be more straight forward to see what’s going on using normal letters for variables (instead of \phi and \psi) and using indices of the form m + 2 rather than n - 2.

The lines labeled 1 and 2 correspond to the operations/transformations going on in Anne’s thing.

Btw, if anyone wants to see the \LaTeX I used for the above (or whatever else) I think the easiest way to see it is check the edit history of the post. I think you can do that for any post to see what the source code was.

ah-ha!


The factoring works for turning a^{m+1}b into a^{m}(ab) cuz a^m \times a^1 = a^{m+1} (I knew that but was having trouble thinking about it before cuz there were other complications getting in the way).

Something related which I think I was looking for earlier is a^m = a^{m - 1 + 1} = a^{m-1} \times a^1

1 Like

Glad I could help! One thing that might have helped you earlier (without the substitutions) is going backwards. Like, you could try this with my example – start with the 2nd line and multiply things out, and try to get to the first line.

I wound up making a shorter post just about the mathematical induction stuff with a simpler example than the one from the current exercise

Fyi there’s an error here:

Screenshot_20210531-082751_Chrome

2\cdot3^n \ne 6^n

6^n = 2^n\cdot3^n

Your maths works out for the last step bc you just sort of undo the mistake (I would keep the left term as 2(3^n) for all relevant steps).

oic, instead of the mistaken intermediate step
= (6^n + 3^n) - 1
should just go straight to
= 2(3^n) + 3^n - 1
thanks

updated post

I found an explanation I thought was pretty good in this old google group

https://groups.google.com/g/seattle-sicp-study-group/c/MYOClwXtcIk/m/9vP26hTyXWkJ?pli=1

It goes into detail on the final step (which is the first thing the question actually asks for). I found most explanations on that part kind of thin

I was gonna attach the PDF directly since I’m not sure how much I trust google to keep up some 14 year old google group indefinitely, but it doesn’t seem that I can. Maybe I’ll post it to my own site

What is the exercise? Where can I find it?

It’s 1.13. link: Justin Does SICP - #41 by Max

@AnneB I tried running your solution to SICP exercise 1.12 with (pascal 2 0). I think that should correspond to the left most entry of the third row (including the summit as of the triangle as a row) and thus be 1. I am getting an infinite loop. Let me know if you have thoughts.

https://aelanteno.github.io/sicp-exercises/exercise-1.12

ah now i’m looking again and wondering if your procedure is meant to start counting rows and columns at 1 instead of 0, and so when i gave it unexpected input i caused it to loop

Yes, it was meant to start at 1.

new post

From Section 1.2.3:

I think I get the general idea re: what orders of growth is about but in this more mathematical statement of it, I don’t follow the stuff about the constants

Exercise 1.14: Draw the tree illustrating the process generated by the count-change procedure of 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

I made trees for (count-change 11) and (count-change 12) (to compare).

I’m planning on looking at these trees again to check for errors (I was having some issues in making them and only came up with an idea to help me error-correct my tree-making when I was mostly done making them).

Anyways, my general impression is that an increase in the amount of change to be made caused some increase in number of computational steps and in “depth” but it didn’t seem explosive like with Fibonacci. So maybe it’s linear? Gonna think about how to analyze this more rigorously.

Exercise 1-14 count-change 11.pdf (77.2 KB)
Exercise 1-14 count-change 12.pdf (60.0 KB)

I think what’s meant here is more like “The sine of an angle (specified in radians) can be computed by making use of the trigonometric identity \sin{x} = 3 \sin{\frac{x}{3}} - 4 \sin^3{\frac{x}{3}} to reduce the size of the argument and also by making use of the approximation \sin{x} ≈ x if x is sufficiently small.” As written it’s confusing.

I had the idea of analyzing the results of trace cc for different values of count-change in order to get a better handle on the procedure’s use of computational resources.

For count-change 6 i got the following:

>(count-change 6)
>{cc 6 5}
> {cc 6 4}
> >{cc 6 3}
> > {cc 6 2}
> > >{cc 6 1}
> > > {cc 6 0}
< < < 0
> > > {cc 5 1}
> > > >{cc 5 0}
< < < <0
> > > >{cc 4 1}
> > > > {cc 4 0}
< < < < 0
> > > > {cc 3 1}
> > > > >{cc 3 0}
< < < < <0
> > > > >{cc 2 1}
> > > > > {cc 2 0}
< < < < < 0
> > > > > {cc 1 1}
> > > >[10] {cc 1 0}
< < < <[10] 0
> > > >[10] {cc 0 1}
< < < <[10] 1
< < < < < 1
< < < < <1
< < < < 1
< < < <1
< < < 1
< < <1
> > >{cc 1 2}
> > > {cc 1 1}
> > > >{cc 1 0}
< < < <0
> > > >{cc 0 1}
< < < <1
< < < 1
> > > {cc -4 2}
< < < 0
< < <1
< < 2
> > {cc -4 3}
< < 0
< <2
> >{cc -19 4}
< <0
< 2
> {cc -44 5}
< 0
<2
2

I’m unsure what the “10” in brackets here signifies and it seems relevant:
Justin Does SICP - Friendly - Critical Falliblism 2021-06-08 15-36-38

The Racket page on debugging has some usual info:

18.6 Debugging

When traced procedures invoke each other, nested invocations are shown by printing a nesting prefix. If the nesting depth grows to ten and beyond, a number is printed to show the actual nesting depth.

So how I think it works is like this. The first > in the output returned by a trace indicates 0 depth. So if it’s the initial invocation of the procedure you’re invoking, or something evaluated within the body Then depth is indicated by an alternation between spaces and additional >'s.

So:
>{cc 7 5}
is 0 depth,
> > {cc 7 2}
is 3 depth (space-bracket-space, excluding first bracket), and
> > > > > {cc 2 1}
is 9 depth (5 spaces and 4 brackets excluding first bracket).
Then past that the number in the square brackets indicates the depth and you basically totally ignore the other stuff (the angle brackets and spaces), which don’t actually indicate anything meaningful when there is a number in square brackets.

I had a vague idea about what the trace output indicated before but in order to try to do the sort of analysis I wanted to do here I needed to make it more precise.