How to use TDD correctly to implement a numerical method?

Question

I am trying to use Test Driven Development to implement my signal processing library. But I have a little doubt: Assume I am trying to implement a sine method (I'm not):

1. Write the test (pseudo-code)

   assertEqual(0, sine(0))
   

2. Write the first implementation

   function sine(radians)
       return 0
   

3. Second test

   assertEqual(1, sine(pi))
   

At this point, should I:

1. implement a smart code that will work for pi and other values, or
2. implement the dumbest code that will work only for 0 and pi?

If you choose the second option, when can I jump to the first option? I will have to do it eventually...

Answer 1

Strictly following TDD, you can first implement the dumbest code that will work. In order to jump to the first option (to implement the real code), add more tests:

assertEqual(tan(x), sin(x)/cos(x))

If you implement more than what is absolutely required by your tests, then your tests will not completely cover your implementation. For example, if you implemented the whole sin() function with just the two tests above, you could accidentally "break" it by returning a triangle function (that almost looks like a sine function) and your tests would not be able to detect the error.

The other thing you will have to worry about for numeric functions is the notion of "equality" and having to deal with the inherent loss of precision in floating point calculations. That's what I thought your question was going to be about after reading just the title. :)

Answer 2

I believe the step when you jump to the first option is when you see there are too many "ifs" in your code "just to pass the tests". That wouldn't be the case yet, just with 0 and pi.

You'll feel the code is beginning to smell, and will be willing to refactor it asap. I'm not sure if that's what pure TDD says, but IMHO you do it in the refactor phase (test fail, test pass, refactor cycle). I mean, unless your failing tests ask for a different implementation.

Answer 3

Note that (in NUnit) you can also do

Assert.That(2.1 + 1.2, Is.EqualTo(3.3).Within(0.0005);

when you're dealing with floating-point equality.

One piece of advice I remember reading was to try to refactor out the magic numbers from your implementations.

Answer 4

At this point, should I:

1. implement real code that will work outside the two simple tests?

2. implement more dumbest code that will work only for the two simple tests?

Neither. I'm not sure where you got the "write just one test at a time" approach from, but it sure is a slow way to go.

The point is to write clear tests and use that clear testing to design your program.

So, write enough tests to actually validate a sine function. Two tests are clearly inadequate.

In the case of a continuous function, you have to provide a table of known good values eventually. Why wait?

However, testing continuous functions has some problems. You can't follow a dumb TDD procedure.

You can't test all floating-point values between 0 and 2*pi. You can't test a few random values.

In the case of continuous functions, a "strict, unthinking TDD" doesn't work. The issue here is that you know your sine function implementation will be based on a bunch of symmetries. You have to test based on those symmetry rules you're using. Bugs hide in cracks and corners. Edge cases and corner cases are part of the implementation and if you unthinkingly follow TDD you can't test that.

However, for continuous functions, you must test the edge and corner cases of the implementation.

This doesn't mean TDD is broken or inadequate. It says that slavish devotion to a "test first" can't work without some thinking about what you real goal is.

Answer 5

In kind of the strict baby-step TDD, you might implement the dumb method to get back to green, and then refactor the duplication inherent in the dumb code (testing for the input value is a kind of duplication between the test and the code) by producing a real algorithm. The hard part about getting a feel for TDD with such an algorithm is that your acceptance tests are really sitting right next to you (the table S. Lott suggests), so you kind of keep an eye on them the whole time. In more typical TDD, the unit is divorced enough from the whole that the acceptance tests can't just be plugged in right there, so you don't start thinking about testing for all scenarios, because all scenarios are not obvious.

Typically, you might have a real algorithm after one or two cases. The important thing about TDD is that it is driving design, not the algorithm. Once you have enough cases to satisfy the design needs, the value in TDD drops significantly. Then the tests more convert into covering corner cases to ensure your algorithm is correct in all aspects you can think of. So, if you are confident in how to build the algorithm, go for it. The kinds of baby steps you are talking about are only appropriate when you are uncertain. By taking such baby steps you start to build out the boundaries of what your code has to cover, even though your implementation isn't actually real yet. But as I said, that is more for when you are uncertain about how to build the algorithm.

Answer 6

You should code up all your unit tests in one hit (in my opinion). While the idea of only creating tests specifically covering what has to be tested is correct, your particular specification calls for a functioning sine() function, not a sine() function that works for 0 and PI.

Find a source you trust enough (a mathematician friend, tables at the back of a math book or another program that already has the sine function implemented).

I opted for bash/bc because I'm too lazy to type it all in by hand :-). If it were a sine() function, I'd just run the following program and paste it into the test code. I'd also put a copy of this script in there as a comment as well so I can re-use it if something changes (such as the desired resolution if more than 20 degrees in this case, or the value of PI you want to use).

#!/bin/bash
d=0
while [[ ${d} -le 400 ]] ; do
    r=$(echo "3.141592653589 * ${d} / 180" | bc -l)
    s=$(echo "s(${r})" | bc -l)
    echo "assertNear(${s},sine(${r})); // ${d} deg."
    d=$(expr ${d} + 20)
done

This outputs:

assertNear(0,sine(0)); // 0 deg.
assertNear(.34202014332558591077,sine(.34906585039877777777)); // 20 deg.
assertNear(.64278760968640429167,sine(.69813170079755555555)); // 40 deg.
assertNear(.86602540378430644035,sine(1.04719755119633333333)); // 60 deg.
assertNear(.98480775301214683962,sine(1.39626340159511111111)); // 80 deg.
assertNear(.98480775301228458404,sine(1.74532925199388888888)); // 100 deg.
assertNear(.86602540378470305958,sine(2.09439510239266666666)); // 120 deg.
assertNear(.64278760968701194759,sine(2.44346095279144444444)); // 140 deg.
assertNear(.34202014332633131111,sine(2.79252680319022222222)); // 160 deg.
assertNear(.00000000000079323846,sine(3.14159265358900000000)); // 180 deg.
assertNear(-.34202014332484051044,sine(3.49065850398777777777)); // 200 deg.
assertNear(-.64278760968579663575,sine(3.83972435438655555555)); // 220 deg.
assertNear(-.86602540378390982112,sine(4.18879020478533333333)); // 240 deg.
assertNear(-.98480775301200909521,sine(4.53785605518411111111)); // 260 deg.
assertNear(-.98480775301242232845,sine(4.88692190558288888888)); // 280 deg.
assertNear(-.86602540378509967881,sine(5.23598775598166666666)); // 300 deg.
assertNear(-.64278760968761960351,sine(5.58505360638044444444)); // 320 deg.
assertNear(-.34202014332707671144,sine(5.93411945677922222222)); // 340 deg.
assertNear(-.00000000000158647692,sine(6.28318530717800000000)); // 360 deg.
assertNear(.34202014332409511011,sine(6.63225115757677777777)); // 380 deg.
assertNear(.64278760968518897983,sine(6.98131700797555555555)); // 400 deg.

Obviously you will need to map this answer to what your real function is meant to do. My point is that the test should fully validate the behavior of the code in this iteration. If this iteration was to produce a sine() function that only works for 0 and PI, then that's fine. But that would be a serious waste of an iteration in my opinion.

It may be that your function is so complex that it must be done over several iterations. Then your approach two is correct and the tests should be updated in the next iteration where you add the extra functionality. Otherwise, find a way to add all the tests for this iteration quickly, then you won't have to worry about switching between real code and test code frequently.

Answer 7

I don't know what language you are using, but when I am dealing with a numeric method, I typically write a simple test like yours first to make sure the outline is correct, and then I feed more values to cover cases where I suspect things might go wrong. In .NET, NUnit 2.5 has a nice feature for this, called [TestCase], where you can feed multiple input values to the same test like this:

[TestCase(1,2,Result=3)]
[TestCase(1,1,Result=2)]
public int CheckAddition(int a, int b)
{
return a+b;
}

Answer 8

Write tests that verify Identities.

For the sin(x) example, think about double-angle formula and half-angle formula.

Open a signal-processing textbook. Find the relevant chapters and implement every single one of those theorems/corollaries as test code applicable for your function. For most signal-processing functions there are identities that must be uphold for the inputs and the outputs. Write tests that verify those identities, regardless of what those inputs might be.

Then think about the inputs.

• Divide the implementation process into separate stages. Each stage should have a Goal. The tests for each stage would be to verify that Goal. (Note 1)
  1. The goal of the first stage is to be "roughly correct". For the sin(x) example, this would be like a naive implementation using binary search and some mathematical identities.
  2. The goal of the second stage is to be "accurate enough". You will try different ways of computing the same function and see which one gets better result.
  3. The goal of the third stage is to be "efficient".

(Note 1) Make it work, make it correct, make it fast, make it cheap. - attributed to Alan Kay