SICP-2nd-Edition-Exercise-1.31

From Boozled

Contents 1 Exercise 1.31 From SICP 2 Attempt 2.1 Part a 2.2 Part b 3 Scheme 4 Parent Course 5 Further Reading

Exercise 1.31 From SICP

Details from SICP are here

a. The (sum) procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.55 Write an analogous procedure called (product) that returns the product of the values of a function at points over a given range. Show how to define (factorial) in terms of (product). Also use (product) to compute approximations to Failed to parse (Cannot write to or create math temp directory): \pi

using the formula 52

Failed to parse (Cannot write to or create math temp directory): \frac{\pi}{4} = \frac{2\cdot4\cdot4\cdot6\cdot6\cdot8\ldots}{3\cdot3\cdot5\cdot5\cdot7\cdot7\ldots}

b. If your (product) procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Attempt

Part a

The mathematical notation for sum and product is as follows

Failed to parse (Cannot write to or create math temp directory): Sum = \sum_{k=1}^N k^2

Failed to parse (Cannot write to or create math temp directory): Product = \prod_{k=1}^N k^2

In both these expressions there are four things happening.

* Test
* Calculate
* Operate
* Step

Our Operate is either Sum or Product in the above examples. The fact that both expressions have four things happening means we could probably abstract further than the question has asked us to but I think some of the next exercises asks us to do that so I won't bother in this one.

We are asked to implement (factorial) in terms of (product) using this method. Have a look at SICP-2nd-Edition-Exercise-1.30. You can see all the expressions listed above. To implement (factorial) you need only change (+ result (calc a)) to (* result (calc a)) and change the name and you have it. All we done here was change from the Sum to the product operator.

Implementing the Wallis Product (at Wikipedia) algorithm appears quite straight forward but it requires careful handling. For instance if we want to calculate the Product up to 8 do we mean where 8 first appear in the denominator or last appears in the numerator etc. I am making the assumption that the product we are calculating always starts the same way as above otherwise we could try and use (define (walliscalcs n) (/ (square n) (square (+ n 1)))) and this method comes with its own set of headaches.

One way to look at the equation above is as follows.

Failed to parse (Cannot write to or create math temp directory): \frac{\pi}{4} = \frac{2\cdot4\cdot6\cdot8\ldots * 4\cdot6\cdot8\ldots}{3\cdot5\cdot7\cdot9\ldots * 3\cdot5\cdot7\cdot9\ldots}

If we go down this route we end up with something like.

This is a very bad method to calculate the product because it is dependent on an even input and the products get so large they become unwieldy on the computer (I eventually got NaN as things got really large). We could still use this method if we broke the numbers up a bit and done some intermediate calculations but that would be a PITA.

Another way to look at this is is as follows:

Failed to parse (Cannot write to or create math temp directory): \frac{\pi}{4} = \lim_{n \to \infty}\left[\frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} \ldots \frac{n}{n+1} \quad * \quad \frac{4}{3} \cdot \frac{6}{5} \cdot \frac{8}{7} \ldots \frac{n+1}{n}\right]

This is a better way than previous and gives us.

Note the two different calculations walliscalcp and walliscalcn. The equation assumes we are calculating out to infinity and when you run it you will see that it approaches Failed to parse (Cannot write to or create math temp directory): \pi

very slowly. Again we can do this using one walliscalc procedure if we calculate Failed to parse (Cannot write to or create math temp directory): \frac{\pi}{2}

. Please note I have not tried to make sure that the number of integers in the numerator match the denominator.

Part b

Please look in the book at the recursive sum algorithm.

Scheme

Parent Course

6.001_Structure_and_Interpretation_of_Computer_Programs

Further Reading

Strategy Pattern

First Class Functions