# SICP Goodness - Stream (8)

Expoloring the stream paradigm

Do you think Computer Science

equalsbuilding websites and mobile apps?Are you feeling that you are doing

repetitiveandnot so intelligentwork?Are you feeling a bit

sickaboutreading manualsandcopy-pastingcode and keeppoking arounduntil it worksall day long?Do you want to understand the

soulofComputer Science?If yes,

read SICP!!!

One more example from the book and one related exercise.

How to calculate PI.

PI can be approximated by:

PI/4 = 1 - ^{1}⁄_{3} + ^{1}⁄_{5} - ^{1}⁄_{7} + …

First, we construct the sequence:

1, -^{1}⁄_{3}, ^{1}⁄_{5}, -^{1}⁄_{7} …

```
(define (pi-summands n)
(cons-stream (/ 1.0 n)
(stream-map - (pi-summands (+ n 2)))))
```

Next, we construct the actual stream that approximate PI:

4X1, 4X(1 - ^{1}⁄_{3}), 4X(1 - ^{1}⁄_{3} + ^{1}⁄_{5}), 4X(1 - ^{1}⁄_{3} + ^{1}⁄_{5} - ^{1}⁄_{7})

```
(define pi-stream
(scale-stream (partial-sum (pi-summands 1)) 4))
(define (partial-sum s)
(cons-stream (stream-car s)
(add-streams (stream-cdr s)
(partial-sum s))))
```

If we print out the `pi-stream`

, we can see that it converges to PI very slowly.

We can use Euler transformation to speed up the process.

Suppose the original stream is

a1, a2, a3, a4 …

and the transformed stream will be

b1, b2, b3, b4 …

Then b_n can be calculated as:

`b_n = a_n+1 - (a_n+1 - a_n)^2 / (a_n-1 - 2 * a_n + a_n+1)`

when n >= 3

`b_n = a_n`

when n < 3

```
(define (euler-transform s)
(let ((s0 (stream-ref s 0))
(s1 (stream-ref s 1))
(s2 (stream-ref s 2)))
(cons-stream (- s2 (/ (square (- s2 s1))
(+ s0 (* -2 s1) s2)))
(euler-transform (stream-cdr s)))))
```

Display `(euler-transform pi-stream)`

shows that it works better.

But even better, we can recursively accelerate the accelerated stream.

This is becoming a bit hard to wrap your head around, so I will put more explanation here.

Suppose the original stream is

a: a1 a2 a3 a4 …

Apply the euler transform to it and we get

b: b1 b2 b3 b4 …

Note that b1 is calculated from a1, a2 and a3, b2 is calculated from a2, a3 and a4 and so on.

Then if we apply euler transform again we get

c: c1 c2 c3 c4 …

Note that c1 is calculated from b1, b2 and b3, and c2 is calculated from b2, b3 and b4 and so on.

We can create a stream of the above streams. This is called *tableau*.

```
(define (make-tableau transform s)
(cons-stream s
(make-tableau transform
(transform s))))
```

For example, `(make-tableau euler-transform a)`

will give back a stream of (a, b, c …), which looks like:

( (a1, a2, a3 ,a4 …) (b1, b2, b3, b4 …) (c1, c2, c3, c4 …) … )

And the accelerated sequence can be formed by taking the first element of each row of the tableau. For example, (a1, b1, c1 …)

```
(define (accelerated-sequence transform s)
(stream-map stream-car
(make-tableau transform s)))
```

Now the “super-acceleration” of PI sequence is now:

`(accelerated-sequence euler-transform pi-stream)`

**Now Exercise 3.65:**

Use the series

ln2 = 1 - ^{1}⁄_{2} + ^{1}⁄_{3} - ^{1}⁄_{4} + …

to compute the approximations to the natural log of 2.

```
(define (ln2-summands n)
(cons-stream (/ 1.0 n)
(stream-map - (ln2-summands (+ n 1)))))
(define ln2-stream
(partial-sum (ln2-summands 1)))
(accelerated-sequence euler-transform ln2-stream)
```

Love how things build up in these examples. I get huge satisfaction from this kind of thing. Much more then e.g. learning how to write React apps. What do you say?

## Share this post

Twitter

Google+

Facebook

Reddit

LinkedIn

StumbleUpon

Email