SICP

# SICP 3.5.2 Solutions

November 1, 2020 13:23

### Exercise 3.53

Here is our mystery stream:

The first element is of course going to be 1. Then each element after that is the sum of the stream with itself, starting from 1 again. That means the second element is the first element added to itself, and the third element is the second added to itself, and so on. Adding a number to itself also just means multiplying by 2. The *n*th element is thus 2*(*n*-1-th element); each subsequent value is twice the one before it. Since we start with 1, the sequence will end up just 2^{n – 1}, or the powers of 2, starting from 2^{0}.

### Exercise 3.54

The procedure to multiply streams term-wise is as simple as doing a map, and analagous to stream addition with a different procedure instead of the addition procedure. In the event that `stream-map`

is defined to take more than two streams, we can do the same with `mul-streams`

by using the `apply`

method (note we cons the multiply procedure to our input create the full argument list for `stream-map`

):

Factorials can be defined by coming up with a recursive formula for each term. Using the index *n* suggested, the *n*th term of the stream is (*n* + 1)!. That is *n* + 1 multiplied by *n*!, and *n*! is the previous term of the stream. Thus, the arguments to `mul-streams`

to construct the cdr of the stream are the terms of the stream (so `factorials`

itself) and the integers, starting from 2, and that stream is given by `(stream-cdr integers)`

.

### Exercise 3.55

To construct the partial sums stream, we need to have a first element, and then a way to construct all remaining elements. The first element is given as *S0*, so we can start with the `stream-car`

of the input. Each remaining partial sum adds the next element of the stream to the previous partial sum. That means the cdr of the partial sums stream is the cdr of the input (since we already took the first element), added to the partial sums stream itself, or:

There is a potentially useful optimization here. With this definition, the call to `partial-sums`

will occur for each element of the partial sums stream. That will create a new stream every time we force the cdr of the stream. Memoization may help in some situations, but it could still be slow when finding new values and creating another new stream. The solution is to use an internal definition to define the stream recursively, and return that, so there is just a single stream being added to `s`

. I did not implement it in the solution file, as this optimization is the same one explored in Exercise 3.63 in the next section to come, and will be discussed there.

### Exercise 3.56

The detailed statements describing the conditions on the stream S provide the answer to how to construct the stream. All that needs to be done is to merge the several scaled streams together. Since `merge`

only takes two stream arguments, then one of the arguments needs to be a merged stream itself. It doesn’t matter which scaled version of S we use in which place, since all will all end up corectly ordered in the stream after being merged.

### Exercise 3.57

For reference, here’s the stream being used:

Under normal operation, `stream-add`

performs a single addition for each element of its arguments. Therefore, there is one addition for each element of the Fibonacci sequence, once we are past the first 2 elements. As long as we are using memoization, there are no further additions required, making the total number of additions equal to one less than the index of the Fibonacci number; the total additions are therefore limited to a linear number of operations.

When memoization is not used for delayed procedures, then there will be additional calculations involved in accessing the elements to be added. Each time a Fibonacci number is calculated, the portions of the two streams being added together need to be completely recalculated. The total number of additions to create Fib(*n*) for *n* larger than 1 is the number needed to create Fib(*n* – 2), plus the number to create Fib(*n* – 1), plus the *n* – 1 additions that are used to add the streams (as in the memoized version). Using this pattern, I created a stream that represents the total number of additions required to compute the Fibonacci number of the same index (when memoization is not used), so that I could check it against an actual calculation.

To determine how many actual additions are used if memoization is disabled, we can make use of that ‘odious’ technique from the previous set of exercises, and create a version of the `fibs`

stream that maintains a count of the additions done. This is done by replacing the simple stream addition with a stream map of a ‘count & add’ procedure in construction of the stream. That verifies the actual number of additions that occur, and if desired, can also document exactly what the additions were. As we’re using a procedure with side effects here, the same cautions that were also explored in Section 3.5.1 pertain; namely that the count might not be repeatible with the same results, and thus should only be tested a single time.

What we find is that the number of additions performed if memoization is not used grows roughly the way the Fibonacci sequence itself does; indeed, it even increases a bit faster. The Fibonacci sequence is roughly exponential (a known result, with the approximation to an exponent of the number φ being explored in an earlier chapter). Therefore, the growth of the number of additions will similarly be roughly exponential.

### Exercise 3.58

The first element of the stream is the quotient when the numerator multiplied by the radix, divided by the the denominator (`den`

). Successive elements are calculated using the remainder from the previous division operation as the new numerator. When the denominator does another division, the remainder will again be multiplied by the radix first.

If we consider the first arguments `num`

and `den`

as a fraction, each element of the stream is thus the next digit of the representation of the original fraction scaled by progressively larger powers of the radix. What that amounts to is the digits of the decimal expansion of the number (when the radix is 10), and in fact what this stream gives is the representation of the fraction in the base-radix number system. For example the expansion of 3/8 is 0.375 with a radix of 10 (3/10 + 7/100 + 5/1000), but 0.6 (6/16) when the radix is 16.

The stream will be infinite. There are many denominators that will produce a repeated sequence when converted this way, just as many fractions yield a repeating decimal when converted. They only ‘terminate’ when the denominator’s prime factors are also factors of the radix. Even if the representation terminates, that just means the remainder is zero, and each term of the stream will be zero from then on.

### Exercise 3.59

a. The stream is nothing more than the input sequence, with each term *n* multiplied by 1/(*n* + 1). That means it can be generated using `mul-streams`

, as long as we have a stream representing 1/(*n* + 1). That can be created using a mapping of the integer stream to elements to their reciprocals. I implemented this using the `ones`

stream mapped with division to the `integers`

stream.

b.Although the text mentions the two functions in terms of being derivatives, we want to use them in terms of their integrals (which is an antiderivative). The relations are similar, of course: if you integrate sine you get the negative of cosine, and if you integrate cosine, you get sine. The initial terms (value at 0) are 1 and 0 for cosine and sine respectively, which means we get:

One way to check that we have the correct streams is to note the relation between the sine, cosine, and exponential function’s terms. This makes use of the Euler formula It turns out that the terms of the sine power series are equal to the odd terms of the exponential function (and alternating positive and negative), and the terms of the cosine power series are the even terms (again with alternating sign). There is also the series evaluation that we can perform to produce approximations of the function’s values with actual angle arguments, as long as we stay in the radius of convergence. Either method confirms the correctness of our stream generation.

### Exercise 3.60

This exercise’s definition of series multiplication is also known as the Cauchy Product when applied to any two infinite series. While it might seem like a moderately complex mathematical concept, for a power series we can figure out the terms without too much difficulty, as only algebra is required.

For two given streams representing power series coefficients, the first two terms are constants. Every other term will have a variable in it, so the first (i.e. constant) term of the output stream is just those two terms multiplied together. The first argument to `cons-stream`

will be the cars of *s1* and *s2*, multiplied normally since they are just two numbers.

We then have to multiply the first term of *s1* by every higher term in *s2*, and vice versa. That can be done using `scale-stream`

against the cdr of the other, again because those leading terms are just single numbers. Those two scaled streams will be aligned with the powers of *x* in the power series, so they can be added together. That is not the final argument to the second part, however, since we’ve only dealt with the first terms of each series so far.

The remaining terms are generated by doing a series multiplication on the remainder of the two series. In order to combine it properly, we construct a stream so we can add it to what was previously calculated. This stream has an initial term of 0, since when we start with the second terms of power series, multiplying them together produces a term two orders higher. Here’s an illustration showing how the terms of the sequence can be generated. All resulting terms of the same order are aligned vertically. Note that every term of degree x^{2} or lower in the result is shown here, since none of the source terms will give a lower-order result.

a0 * b0 + a0 * (b1 * x) + a0 * (b2 * x^{2}) + a0 * (b3 * x^{3}) + …

b0 * (a1 * x) + b0 * (a2 * x^{2}) + b0 * (a3 * x^{3}) + …

(a1 * x) * (b1 * x) + (a1 * x) * (b2 * x^{2}) + …

(b1 * x) * (a2 * x^{2}) + …

etc.

The pattern of combining the coefficients will repeat as the index increases, so this is enough to produce the terms for our stream. The code to do this is as follows:

There is an alternate, slightly more compact version of mul-series that employs recursion. We can generate the entire stream simply by taking every element of stream *s1* and multiplying by the elements of stream *s2* as a series. Instead of doing the second scaling by the car of *s2*, we just recursively call `mul-series`

with the cdr of *s1* and leave *s2* as it is. That reduces the answer to:

Either method will produce the correct result on the infinite streams.

### Exercise 3.61

We want to turn the right-hand side of the expression X = 1 – Sr*X into a stream. The first element is 1, of course, and the remaining elements are the negation of the series multiplication of Sr and X itself. Using our stream functions, we can write this (using `invert-unit-series`

to represent X) using this code:

That line is then the second argument to `cons-stream`

, to produce the remainder of stream X, which again is the result of `invert-unit-series`

itself. Note that the same optimization could be made as with `partial-sums`

to avoid creating a new stream at every step.

The testing of these involved some trigonemetric identities, since we can use the definition of the secant and cosecant to derive them from our sine and cosine series previously defined. Note that since the leading term of the sine series is 0, we start with its second term, which is 1, in order to produce the cosecant. While that does correctly produce an equivalent series, it is not a power series, and only valid for evaluation at the particular value used.

### Exercise 3.62

Division can be generically defined as multiplication by an inverse (of the divisor), once the inverse is appropriately defined. Using `invert-unit-series`

gives a suitable inverse, although we need to scale the initial stream to make sure that it is a unit series, i.e. its leading term is 1. To produce the correct final answer, we then must scale the stream back again, by multiplying by the former leading term. Division of the power series is accomplished with a `mul-series`

operation on the ‘dividend’ stream, by the inverse generated from the ‘divisor’ stream.