I’ve started going through SICP to try to learn Clojure in a little more depth. I’m quickly realizing, though, that since some of the exercises are on the theme of “implement this mathematical equation”, it’s difficult to do so using TDD.
Exercise 1.8
Newton’s method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value
Use this formula to implement a cuberoot procedure analogous to the squareroot procedure.
Approach
goodenough?
Because this function provides approximations, not exact values, we first need to build a function to tell us a value is good enough. This will certainly be needed in the tests, as our function isn’t going to return exactly 2 when 8 is given. What’s interesting is we’ll also need it in the main code, to know if we’re close enough to stop.
Exact values will be easier to build, so we’ll start with the usual base case: 0
1 2 3 4 

That’s pretty braindead, so let’s add an assertion
1 2 3 4 5 

Now let’s get rid of that hardcoded true:
1 2 3 4 5 6 

We’re trying to find the cube root, not equality:
1 2 3 4 5 6 7 

And it usually won’t be an exact match:
1 2 3 4 5 6 7 8 

But the tolerance is faulty, anything less than the target will pass:
1 2 3 4 5 6 7 8 9 

nextguess
Here’s where we build the core of the algorithm, the logic to generate a new guess. The idea here is to build it up incrementally by making as much of the expression as possible go to 0.
We’ll start by making $\frac{x}{y^2}$ go to 0. Ideally, we would also like to make $2y$ go to 0, but that would cause a division by 0 error.
1 2 3 4 5 

Now another value to triangulate the functionality:
1 2 3 4 5 6 

Let’s start working on the next term. Notice that by keeping the denominator of this term to 1 we get to drive the numerator separately:
1 2 3 4 5 6 7 8 

Finally we can finish off the equation:
1 2 3 4 5 6 7 8 9 10 

cuberoot
Now that we have a reliable way to tell if our answer’s good enough, and a way to determine the next guess, we can start driving the main function:
1 2 3 4 5 

We’ll need a way to track our current guess, so this creates the need for an extra argument:
1 2 3 4 5 6 7 

Now we can refactor the duplication out of the two forms:
1 2 3 

The next test requires a little bit of algebraic manipulation. I don’t want to get the next guess and start recursing in the same step, so I need to figure out a guess that will require another step, but only one.
Plugging this into a polynomial solver yields 1/2, which will suit our purposes:
1 2 3 4 5 6 7 8 9 10 11 

Now we want to drive the recursion, so let’s test something that requires more than one guess:
1 2 3 4 5 6 7 8 9 10 11 12 
