SICP

Exercise 3.82.    Redo exercise  3.5  on Monte Carlo integration in terms of streams. The stream version of  estimate-integral  will not have an argument telling how many trials to perform. Instead, it will produce a stream of estimates based on successively more trials. SOLUTION The code and tests are here .

Exercise 3.81.    Exercise  3.6  discussed generalizing the random-number generator to allow one to reset the random-number sequence so as to produce repeatable sequences of ``random'' numbers. Produce a stream formulation of this same generator that operates on an input stream of requests to  generate  a new random number or to  reset  the sequence to a specified value and that produces the desired stream of random numbers. Don't use assignment in your solution. SOLUTION The code and tests are here .

Exercise 3.80.    A  series RLC circuit  consists of a resistor, a capacitor, and an inductor connected in series, as shown in figure  3.36 . If  R ,  L , and  C  are the resistance, inductance, and capacitance, then the relations between voltage ( v ) and current ( i ) for the three components are described by the equations and the circuit connections dictate the relations Combining these equations shows that the state of the circuit (summarized by  v C , the voltage across the capacitor, and  i L , the current in the inductor) is described by the pair of differential equations The signal-flow diagram representing this system of differential equations is shown in figure  3.37 . Figure 3.36:   A series RLC circuit. Figure 3.37:   A signal-flow diagram for the solution to a series RLC circuit. Write a procedure  RLC  that takes as arguments the parameters  R ,  L , and  C  of the circuit and the time increment  d t . In a manner similar to that of th

Exercise 3.79.    Generalize the  solve-2nd  procedure of exercise  3.78  so that it can be used to solve general second-order differential equations  d 2   y / d t 2  =  f ( d y / d t ,  y ). SOLUTION The code is here .

Exercise 3.78.    Figure 3.35:   Signal-flow diagram for the solution to a second-order linear differential equation. Consider the problem of designing a signal-processing system to study the homogeneous second-order linear differential equation The output stream, modeling  y , is generated by a network that contains a loop. This is because the value of  d 2 y / d t 2 depends upon the values of  y  and  d y / d t  and both of these are determined by integrating  d 2 y / d t 2 . The diagram we would like to encode is shown in figure  3.35 . Write a procedure  solve-2nd  that takes as arguments the constants  a ,  b , and  d t and the initial values  y 0  and  d y 0  for  y  and  d y / d t  and generates the stream of successive values of  y . SOLUTION The code and tests are here . The plots are pasted below and also available  here . 

Exercise 3.77.   The  integral  procedure used above was analogous to the ``implicit'' definition of the infinite stream of integers in section  3.5.2 . Alternatively, we can give a definition of  integral  that is more like  integers-starting-from  (also in section  3.5.2 ): (define (integral integrand initial-value dt)   (cons-stream initial-value                (if (stream-null? integrand)                    the-empty-stream                    (integral (stream-cdr integrand)                              (+ (* dt (stream-car integrand))                                 initial-value)                              dt)))) When used in systems with loops, this procedure has the same problem as does our original version of  integral . Modify the procedure so that it expects the  integrand  as a delayed argument and hence can be used in the  solve  procedure shown above. SOLUTION The code is here .

Exercise 3.76.    Eva Lu Ator has a criticism of Louis's approach in exercise  3.75 . The program he wrote is not modular, because it intermixes the operation of smoothing with the zero-crossing extraction. For example, the extractor should not have to be changed if Alyssa finds a better way to condition her input signal. Help Louis by writing a procedure  smooth  that takes a stream as input and produces a stream in which each element is the average of two successive input stream elements. Then use  smooth  as a component to implement the zero-crossing detector in a more modular style. SOLUTION See in the tests below that the 'smooth' procedure after processing the parabolic  stream from Exercise 3.75, produces the same stream as what we saw produced by the  corrected procedure in Exercise 3.75. The new procedures are also tested on a random  value stream after this. The code and tests are here .

Exercise 3.75.    Unfortunately, Alyssa's zero-crossing detector in exercise  3.74  proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows: (define (make-zero-crossings input-stream last-value)   (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))     (cons-stream (sign-change-detector avpt last-value)                  (make-zero-crossings (stream-cdr input-stream)                                       avpt)))) This does not correctly implement Alyssa's plan. Find the bug that Louis has in

Exercise 3.74.    Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the  zero crossings  of the input signal. That is, the resulting signal should be + 1 whenever the input signal changes from negative to positive, - 1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be ... 1  2  1.5  1  0.5  -0.1  -2  -3  -2  -0.5  0.2  3  4  ... ...  0  0    0  0    0     -1  0   0   0     0    1  0  0  ... In Alyssa's system, the signal from the sensor is represented as a stream  sense-data  and the stream  zero-crossings  is the corresponding stream of zero crossings. Alyssa first writes a procedure  sign-change-detector  that takes two values as arguments and compares the signs of the values to produce an appropriate 0, 1,

Exercise 3.73.               v  =  v 0  + (1/ C ) 0 t i   d t  +  R   i        Figure 3.33:   An RC circuit and the associated signal-flow diagram. We can model electrical circuits using streams to represent the values of currents or voltages at a sequence of times. For instance, suppose we have an  RC circuit  consisting of a resistor of resistance  R  and a capacitor of capacitance  C  in series. The voltage response  v  of the circuit to an injected current  i  is determined by the formula in figure  3.33 , whose structure is shown by the accompanying signal-flow diagram. Write a procedure  RC  that models this circuit.  RC  should take as inputs the values of  R ,  C , and  d t and should return a procedure that takes as inputs a stream representing the current  i  and an initial value for the capacitor voltage  v 0  and produces as output the stream of voltages  v . For example, you should be able to use  RC  to model an RC circuit with  R  = 5 ohms,  C  = 1 far

Exercise 3.72.   In a similar way to exercise  3.71  generate a stream of all numbers that can be written as the sum of two squares in three different ways (showing how they can be so written). SOLUTION The code and tests are here .

Exercise 3.71.    Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called  Ramanujan numbers , in honor of the mathematician Srinivasa Ramanujan. 70 Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers ( i , j ) weighted according to the sum  i 3  +  j 3  (see exercise  3.70 ), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five? SOLUTION The code and tests are here .

Exercise 3.70.    It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an  ad hoc  interleaving process. We can use a technique similar to the  merge  procedure of exercise  3.56 , if we define a way to say that one pair of integers is ``less than'' another. One way to do this is to define a ``weighting function'' W ( i , j ) and stipulate that ( i 1 , j 1 ) is less than ( i 2 , j 2 ) if  W ( i 1 , j 1 ) <  W ( i 2 , j 2 ). Write a procedure  merge-weighted  that is like  merge , except that  merge-weighted  takes an additional argument  weight , which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream. 69  Using this, generalize  pairs  to a procedure  weighted-pairs  that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pair

Exercise 3.69.   Write a procedure  triples  that takes three infinite streams,  S ,  T , and  U , and produces the stream of triples ( S i , T j , U k ) such that  i   <   j   <   k . Use  triples  to generate the stream of all  Pythagorean triples of positive integers, i.e., the triples ( i , j , k ) such that  i   <   j  and  i 2  +  j 2  =  k 2 . SOLUTION The infinite streams S, T and U are represented as follows: S0 T0 U0 S1 T1 U1 S2 T2 U2 S3 T3 U3 S4 T4 U4 . . . . . . . . . All triples (Si, Tj, Uk) such that i < j < k can be produced by combining the following: 1. (S0, T1, U2) 2. S0 combined with all the pairs produced using the streams (T1, T2, T3, ...) and (U1, U2, U3, ...) such that for every pair (Tj, Uk), j < k. We need to exclude the  first element from this combined stream because the first element will be (S0, T1, U2) which is already accounted for. 3. triples called recursively on the streams

Exercise 3.68.   Louis Reasoner thinks that building a stream of pairs from three parts is unnecessarily complicated. Instead of separating the pair ( S 0 , T 0 ) from the rest of the pairs in the first row, he proposes to work with the whole first row, as follows: (define (pairs s t)   (interleave    (stream-map (lambda (x) (list (stream-car s) x))                t)    (pairs (stream-cdr s) (stream-cdr t)))) Does this work? Consider what happens if we evaluate  (pairs integers integers)  using Louis's definition of  pairs . SOLUTION Louis Reasoner's procedure will not work. It will run into an infinite loop. Not having  an outer 'stream-cons', there is no delayed operation to prevent the program from  getting into an infinite loop. When 'louis-reasoner-pairs' executes, 'interleave' needs to be run. But before that, it's  arguments need to be evaluated. The second argument is a call to louis-reasoner-pairs  again. This puts the program int

Exercise 3.67.   Modify the   pairs   procedure so that   (pairs integers integers)   will produce the stream of   all   pairs of integers ( i , j ) (without the condition   i   <   j ). Hint: You will need to mix in an additional stream. SOLUTION The code and tests are here .

Exercise 3.66.   Examine the stream  (pairs integers integers) . Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.) SOLUTION The pairs produced by (pairs integers integers) will look like this: (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, 7) (1, 8) (1, 9)  (1, 10)  (1, 11) (1, 12) ...          (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (2, 7) (2, 8) (2, 9)  (2, 10)  (2, 11) (2, 12) ...                   (3, 3) (3, 4) (3, 5) (3, 6) (3, 7) (3, 8) (3, 9)  (3, 10)  (3, 11) (3, 12) ...                            (4, 4) (4, 5) (4, 6) (4, 7) (4, 8) (4, 9)  (4, 10)  (4, 11) (4, 12) ...                                     (5, 5) (5, 6) (5, 7) (5, 8) (5, 9)  (5, 10)  (5, 11) (5, 12) ...    

Exercise 3.65.    Use the series to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for  . How rapidly do these sequences converge? SOLUTION As we can see from the results below, the rate of convergence increases dramatically  with Euler transforms and tableau. I ran multiple tests on the un-accelerated series.  Even with 10000 terms, the value of ln(2) computed was 0.6930971830599583 whereas  the desired value is 0.69314718056. The difference is 0.0000499975. Euler acceleration is much faster and gets very close to the desired value in 5000 steps. The value after combining 5000 terms is 0.6931471805589525. But by using tableau acceleration, we reach 0.6931471805599454 just 10 steps! The code and tests are here .

Exercise 3.64.   Write a procedure  stream-limit  that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements that differ in absolute value by less than the tolerance, and return the second of the two elements. Using this, we could compute square roots up to a given tolerance by (define (sqrt x tolerance)   (stream-limit (sqrt-stream x) tolerance)) SOLUTION The code and tests are here .

Exercise 3.63.   Louis Reasoner asks why the  sqrt-stream  procedure was not written in the following more straightforward way, without the local variable  guesses : (define (sqrt-stream x)   (cons-stream 1.0                (stream-map (lambda (guess)                              (sqrt-improve guess x))                            (sqrt-stream x)))) Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa's answer. Would the two versions still differ in efficiency if our implementation of  delay  used only  (lambda () < exp >)  without using the optimization provided by  memo-proc  (section  3.5.1 )? EXPLANATION If we do not use the local variable 'guesses', then every call to procedure sqrt-stream  creates a brand-new stream. In Louis Reasoner's implementation of 'sqrt-stream', a call to: (display-stream (sqrt-stream 100)) will result in generating the

Exercise 3.62.    Use the results of exercises  3.60  and  3.61  to define a procedure  div-series  that divides two power series.  Div-series  should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then  div-series  should signal an error.) Show how to use  div-series  together with the result of exercise  3.59  to generate  the power series for tangent. SOLUTION Note that the power series for tan(x) is: tan(x) = 1 * (x/1!) + 2 * ((x^3)/3!) + 16 * ((x^5)/5!) + 272 * ((x^7)/7!) + 7936 * ((x^9)/9!) + ... The code and tests are here .

Exercise 3.61.   Let  S  be a power series (exercise  3.59 ) whose constant term is 1. Suppose we want to find the power series 1/ S , that is, the series  X  such that  S  ·  X  = 1. Write  S  = 1 +  S R  where  S R  is the part of  S  after the constant term. Then we can solve for  X  as follows: In other words,  X  is the power series whose constant term is 1 and whose higher-order terms are given by the negative of  S R  times  X . Use this idea to write a procedure  invert-unit-series  that computes 1/ S  for a power series  S  with constant term 1. You will need to use  mul-series  from exercise  3.60 . SOLUTION The code and tests are here .