SICP

Exercise 3.60.    With power series represented as streams of coefficients as in exercise  3.59 , adding series is implemented by  add-streams . Complete the definition of the following procedure for multiplying series: (define (mul-series s1 s2)   (cons-stream < ?? > (add-streams < ?? > < ?? >))) You can test your procedure by verifying that  s i n 2   x  +  c o s 2   x  = 1, using the series from exercise  3.59 . SOLUTION Logic used in mul-series: (a0 + a1x + a2x^2 + a3x^3 + ...) * (b0 + b1x + b2x^2 + b3x^3 + ...) is: (a0 * b0) + {a0 * (b1x + b2x^2 + b3x^3 + ...)} + {b0 * (a1x + a2x^2 + a3x^3 + ...)} + {(a1x + a2x^2 + a3x^3 + ...) * (b1x + b2x^2 + b3x^3 + ...)} The coefficients after multiplying the two series above will be: Variable | Coefficient ------------------------------- x^0 | a0*b0 x^1 | a0*b1 + a1*b0 x^2 | a0*b2 + a1*b1 + a2*b0 x^3 | a0*b3 + a1*b2 + a2*b1 + a3*b0 x^4 | a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0

Exercise 3.59.    In section  2.5.3  we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with  power series , such as represented as infinite streams. We will represent the series  a 0  +  a 1   x  +  a 2   x 2  +  a 3   x 3  +  ···  as the stream whose elements are the coefficients  a 0 ,  a 1 ,  a 2 ,  a 3 ,  ... . a. The integral of the series  a 0  +  a 1   x  +  a 2   x 2  +  a 3   x 3  +  ···  is the series where  c  is any constant. Define a procedure  integrate-series  that takes as input a stream  a 0 ,  a 1 ,  a 2 ,  ... representing a power series and returns the stream  a 0 , (1/2) a 1 , (1/3) a 2 ,  ...  of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use  integrate-series , we will  cons  on the appropriate constant.) b. The function  x     e x  is its own deriv

Exercise 3.58.   Give an interpretation of the stream computed by the following procedure: (define (expand num den radix)   (cons-stream    (quotient (* num radix) den)    (expand (remainder (* num radix) den) den radix))) ( Quotient  is a primitive that returns the integer quotient of two integers.) What are the successive elements produced by  (expand 1 7 10)  ? What is produced by  (expand 3 8 10)  ? SOLUTION The code and tests are here . EXPLANATION (expand 1 7 10) produces: 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4 ... (expand 3 8 10) produces 3, 7, 5, 0, 0, 0, 0 ...

Exercise 3.57.    How many additions are performed when we compute the  n th Fibonacci number using the definition of  fibs  based on the  add-streams  procedure? Show that the number of additions would be exponentially greater if we had implemented  (delay < exp >)  simply as  (lambda () < exp >) , without using the optimization provided by the  memo-proc  procedure described in section  3.5.1 . 64 SOLUTION The Racket code and explanation is here . The Scheme code and tests are here . EXPLANATION (define fibs (stream-cons 0 (stream-cons 1 (add-streams (stream-rest fibs) fibs) ) ) ) Number of additions performed: 0th Fibonacci number (0): 0 additions 1st Fibonacci number (1): 0 additions 2nd Fibonacci number (1): 1 addition 3rd Fibonacci number (2): 2 additions 4th Fibonacci number (3): 3 additions As we can see above, for every higher Fibonacci number, one additional addition is performed.  So when we compute the nth Fibonacci num

Exercise 3.56.   A famous problem, first raised by  R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers  S  and notice the following facts about it. S  begins with 1. The elements of  (scale-stream S 2)  are also elements of  S . The same is true for  (scale-stream S 3)  and  (scale-stream 5 S) . These are all the elements of  S . Now all we have to do is combine elements from these sources. For this we define a procedure  merge  that combines two ordered streams into one ordered result stream, eliminating repetitions: (define (merge s1 s2)   (cond ((stream-null? s1) s2)         ((stream-null? s2) s1)  

Exercise 3.55.   Define a procedure  partial-sums  that takes as argument a stream  S  and returns the stream whose elements are  S 0 ,  S 0  +  S 1 ,  S 0  +  S 1  +  S 2 ,  ... . For example,  (partial-sums integers)  should be the stream 1, 3, 6, 10, 15,  ... . SOLUTION The code and tests are here .

Exercise 3.54.   Define a procedure  mul-streams , analogous to  add-streams , that produces the elementwise product of its two input streams. Use this together with the stream of  integers  to complete the following definition of the stream whose  n th element (counting from 0) is  n  + 1 factorial: (define factorials (cons-stream 1 (mul-streams < ?? > < ?? >))) SOLUTION The code and tests are here .