SICP
SICP 3.5.2 Solutions
November 1, 2020 13:23
Exercise 3.53
Here is our mystery stream:
(define s (cons-stream 1 (add-streams s s)))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 nth 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 2n – 1, or the powers of 2, starting from 20.
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):
(define (mul-streams . streams)
(apply stream-map (cons * streams))
)Factorials can be defined by coming up with a recursive formula for each term. Using the index n suggested, the nth 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:
(add-streams (stream-cdr s) (partial-sums s))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:
(define fibs
(cons-stream 0
(cons-stream 1
(add-streams (stream-cdr fibs)
fibs
)
)
)
)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.
(define fibc-additions (cons-stream 0 (cons-stream 0
(add-streams integers
(add-streams fibc-additions
(stream-cdr fibc-additions)
)
)
)
)
)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:
(define cosine-series
(cons-stream 1 (scale-stream (integrate-series sine-series) -1))
)
(define sine-series
(cons-stream 0 (integrate-series cosine-series))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 x2 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 * x2) + a0 * (b3 * x3) + …
b0 * (a1 * x) + b0 * (a2 * x2) + b0 * (a3 * x3) + …
(a1 * x) * (b1 * x) + (a1 * x) * (b2 * x2) + …
(b1 * x) * (a2 * x2) + …
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:
(define (mul-series s1 s2)
(cons-stream
(* (stream-car s1) (stream-car s2))
(add-streams
(add-streams (scale-stream (stream-cdr s2) (stream-car s1))
(scale-stream (stream-cdr s1) (stream-car s2))
)
(cons-stream 0 (mul-series (stream-cdr s1) (stream-cdr s2)))
)
)
)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:
(define (mul-series s1 s2)
(cons-stream (* (stream-car s1) (stream-car s2))
(add-streams (scale-stream (stream-cdr s2) (stream-car s1))
(mul-series (stream-cdr s1) s2)
)
)
)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:
(scale-stream (mul-series (invert-unit-series us) (stream-cdr us)) -1)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.