# An important aspect of test-driven development: What’s my motivation?

A month ago, Fagner Brack published “This Is The One Thing Nobody Told You About TDD.” As someone who is still relatively new on the test-driven development (TDD) bandwagon, I definitely want to know what is that one thing nobody has told me about this programming philosophy I’m trying to adopt.

“The tests give you hints of what to do next. They drive you to build the code.” — Fagner Brack

Well, maybe I was luckier than most to have had an instructor, specifically Samah Majadla, who explained this to me. She didn’t use these exact words, but I think she got the point across to my classmates and I.

The tests motivate the production code. You write a simple test. Then you write the bare minimum necessary to make that test pass. Then you write a slightly more complicated test. And then write what’s needed to pass that test. And so on and so forth.

At each step of the process, to the best of your ability, don’t let the production code be more complex than strictly required to pass the tests. Because… the test drives the source.

The refactoring step of the TDD cycle gets very little attention. If there really is something about TDD that no one has ever told me, it’s likelier to be in the refactoring step.

But the thing about refactoring, though, is that it’s about simplifying the production code. If during refactoring you think of an improvement that’s not about simplifying what you wrote to pass the test, don’t make that change yet: write a test first.

I think the greatest common divisor (GCD) function provides a nice, simple and to-the-point example of how to do TDD.

Quick math refresher: the greatest common divisor of two integers is the greatest positive integer that divides them both. For instance, gcd(−91, −98) = 7, because both −91 and −98 are divisible by 7.

Also I think it’s better to demonstrate TDD in a programming language with a commonly preferred testing framework, like Java with JUnit, or C# with xUnit.

Because of the naming convention, you might think that JsUnit is the commonly preferred testing framework for JavaScript. But that’s a can of worms I better leave to someone else to tackle.

I like to start by writing a stub that will obviously fail the test. It doesn’t matter much if you’re writing your source code in a plain text editor and compiling on the command line, but in an integrated development environment (IDE) like NetBeans or IntelliJ, stubs help the IDE give you more pertinent errors and warnings.

So here’s our GCD stub that should obviously fail the first test:

` public static int gcd(int a, int b) {`

return -1;

}

For the first test, you might already be thinking of a pair of distinct numbers, like −27 and 18. But we can go simpler than that for our first test: how about gcd(*n*, *n*), where *n* is a positive integer?

Then obviously gcd(*n*, *n*) = *n*. So our first test then looks like this:

` @Test`

public void testGCDOnSameNumber() {

int expected = 10;

int actual = gcd(expected, expected);

assertEquals(expected, actual);

}

At this point, there are two valid ways to amend `gcd()`

to pass the test. One way is:

` public static int gcd(int a, int b) {`

return a;

}

The other way is to return `b`

instead of `a`

. Either way, the test should pass now.

At this point it might be too much to test if `a == b`

, and it would certainly be too much to write a full-fledged implementation of an algorithm that derives lists of divisors from the prime factorizations of the integers and is equipped to handle the special case `gcd(Integer.MIN_VALUE, Integer.MIN_VALUE)`

with a very elegant and informative custom exception.

We’ll get to that, but only after writing the relevant tests. No refactoring is needed at this point, because all we did was substitute one character for two characters on a function that was just a simple stub.

Can we do a test for two distinct numbers now? We could, but I think there is one other simpler thing we can do first: test for gcd(*n*, *n*) with *n* a negative integer. Let’s not use the `MIN_VALUE`

of our numeric data type, though.

` @Test`

public void testGCDOnSameNegativeNumber() {

int expected = 10;

int actual = gcd(-expected, -expected);

assertEquals(expected, actual);

}

This should fail because it should give us −10 instead of +10. The fix to pass is easy.

` public static int gcd(int a, int b) {`

return Math.abs(a);

}

Or we could also use `Math.abs(b)`

, either way it’s enough to pass the tests so far.

Okay, now let’s write a test with distinct numbers. At this point, it should be only positive numbers though, we should probably hold off on a test with one positive and one negative number.

` @Test`

public void testGCD10501125() {

int expected = 75;

int actual = gcd(1050, 1125);

assertEquals(expected, actual);

}

Clearly this test will fail because the GCD is neither of the input numbers.

Now can we write the proper GCD implementation? We could, but it’s actually still quite easy to be a smart-aleck with this one. Notice that the GCD in this case is the difference of `a`

and `b`

. So…

` public static int gcd(int a, int b) {`

if (a == b) {

return Math.abs(a);

} else {

return Math.abs(a - b);

}

}

At this point you’re probably ready to actually write an actual GCD function, so here’s a test that will hopefully require that.

` @Test`

public void testGCDOnSortOfRandomNumbers() {

int psRanNum = (int) Math.floor(Math.random() * 200 + 1);

psRanNum = 6 * psRanNum + 1; // Ensure it's odd and not

// divisible by 3

int currPowRan = psRanNum;

int threshold = Integer.MAX_VALUE / 16;

int expResult, result, holderA, holderB;

int curr3Pow = 3;

while ((currPowRan > 0) && (currPowRan < threshold)) {

expResult = 1;

result = gcd(currPowRan, currPowRan + 1);

assertEquals(expResult, result);

expResult = psRanNum;

result = gcd(currPowRan, psRanNum);

assertEquals(expResult, result);

expResult *= 2;

holderA = 2 * currPowRan;

holderB = 2 * curr3Pow * psRanNum;

result = gcd(holderA, holderB);

assertEquals(expResult, result);

currPowRan *= psRanNum;

curr3Pow *= 3;

}

}

We’re trying to steer well clear of numbers above 2³⁰, so as to not deal with overflow issues yet.

I suppose it’s still possible at this point to write an implementation that will pass this test but fail other simple tests with likely inputs, like gcd(336, −864) or gcd(245, 343).

But now the complexity of detecting what the wanted result might be vastly outweighs the complexity of actually writing a proper GCD implementation that works for all but a few unlikely edge cases.

There are at least three distinct algorithms we could use to find the GCD of two integers. If you know one I don’t mention, please let me know about it in the comments.

One way is to obtain the prime factorizations of both numbers and multiply the factors that they have in common. For example, 1050 = 2 × 3 × 5² × 7 and 1125 = 3² × 5³, so 3 × 5² = 75, and indeed gcd(1050, 1125) = 75.

The problem with this is that we would need to either write a new prime factorization function (which we’ll have to test and develop) or find one from a third party library.

We also need something to find the elements in common of two sets (what mathematicians call “intersection”). With this algorithm, we’re going to get sidetracked.

To me the most obvious algorithm is to list the positive divisors of each number and then find the largest one of them.

Using the same example as before, we see that the positive divisors of 1050 are 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 25, 30, 35, 42, 50, 70, 75, 105, 150, 175, 210, 350, 525 and 1050 itself.

The positive divisors of 1125 are 1, 3, 5, 9, 15, 25, 45, 75, 125, 225, 375 and 1125 itself. The numbers in common to both sets are 1, 3, 5, 15, 25, 75, of which 75 is obviously the largest number, and thus the greatest common divisor.

In Scala this would be very easy to implement. Here is the example on the Scala REPL:

scala> (1 to 1050).filter(1050 % _ == 0)

res0: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 25, 30, 35, 42, 50, 70, 75, 105, 150, 175, 210, 350, 525, 1050)scala> (1 to 1125).filter(1125 % _ == 0)

res1: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 3, 5, 9, 15, 25, 45, 75, 125, 225, 375, 1125)scala> res0.intersect(res1)

res2: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 3, 5, 15, 25, 75)

This might not be the most elegant way to do this in Scala, but for some quick and dirty experiments on the REPL, it’s just fine.

In Java, we’d have to write these things from scratch, or find a third party library. Though in Scala it would still be good form to write tests for a list of divisors function.

Regardless, both of these algorithms have the potential to sidetrack us from the objective of writing the bare minimum implementation that will pass all the tests we’ve written so far.

In this GCD scenario, our motivation is to write the simplest implementation that will meet the requirements expressed by the tests we have written. No more, no less.

So the Euclidean GCD algorithm here is the simplest and most direct way to get at our goal. However, let us take a brief moment to reflect on the mathematical principles at work here.

To use the Euclidean GCD algorithm, we need a Euclidean function *f*(*n*) such that *f*(*n*) is always a positive integer, except for *f*(0) = 0, and such that whenever *d* is a divisor of *n*, the inequality *f*(*d*) ≤ *f*(*n*) is true.

Almost always the absolute value function is chosen for this purpose, so much so that it gets taken for granted. And since Java comes with `Math.abs()`

standard, we don’t have to reinvent the wheel on this one.

Then, to figure out gcd(*a*, *b*), if *f*(*b*) ≤ *f*(*a*) (swap *a* and *b* if necessary), we need to find numbers *q* and *r* such that *a* = *qb* + *r* and *f*(*r*) < *f*(*b*) (it must be less than, not less than or equal to).

If *r* = 0, we’re done, the gcd is *b*. If not, then we reset *a* to *b* and *b* to *r*, and go through the process of finding numbers *q* and *r* such that *a* = *qb* + *r* and *f*(*r*) < *f*(*b*) all over again.

To use the example gcd(1050, 1125) once more, we see that 1125 = 1 × 1050 + 75. Since our remainder is not 0, we go on to 1050 = 14 × 75 + 0. The remainder is now 0 and the GCD is 75.

I think this is enough information for you to implement a proper GCD function that passes the tests presented here so far, as well as other simple tests that you may devise.

It is a well known fact that the Euclidean GCD algorithm is the least efficient for consecutive Fibonacci numbers. Work out gcd(−144, 89) on paper, for example. By prime factorization it is much quicker to confirm your hunch that these two numbers are coprime.

However, computers are so fast that you won’t notice any performance penalty even for gcd(1134903170, 1836311903). You’d have to go well above the upper limits of `int`

and `long`

to notice any performance degradation.

If you do need to test for performance, I’d read up on timeouts in JUnit. The basic idea is that you allot a certain number of milliseconds for the test to run, and if it’s not done in that time, the test fails.

In Scala, we could implement `gcd()`

in such a way that it can take a custom Euclidean function at runtime, but uses `Math.abs()`

as the default Euclidean function if no Euclidean function is specified. It would go something like this:

` def gcd(a: Int, b: Int, eucFn: Int => Int = Math.abs _): Int = {`

// Euclidean algorithm goes here

currB // Or currA? Don't need "return" either way

}

Our TDD process would be the same as with Java, aside from superficial differences, and we could continue to use JUnit, at least for the time being.

Thanks to the implicit parameter (assuming I have the right syntax), we wouldn’t need to go back and add “`, Math.abs`

” to the `gcd()`

calls in the previous tests.

The crucial difference would be in testing that `gcd()`

actually uses a custom function that we pass it during a test.

The way we would do that might be to pass an invalid Euclidean function (like one that returns negative integers) and seeing if it throws an exception or if it just uses the absolute value function and returns the right result anyway.

At that point, our draft of `gcd()`

should be such that it uses `Math.abs()`

regardless of what function we pass it. Then, once we have a test fail because our custom function is ignored, we go ahead and rework `gcd()`

so that it does use the custom function.

Aside from these functional considerations, the TDD process in Scala is hardly different from the TDD process in Java.

Earlier I mentioned the case `gcd(Integer.MIN_VALUE, Integer.MIN_VALUE)`

, and that maybe this should cause a custom exception.

The GCD in that example is of course `Integer.MAX_VALUE + 1`

, which obviously can’t be properly represented in a signed 32-bit `int`

. We’d have much the same issue with `Long.MIN_VALUE`

if we were using `long`

instead of `int`

, but at the signed 64-bit threshold instead.

But why write a custom exception (which we’ll have to take through the TDD process as well) when we can just use an existing exception in the standard Java library?

I think `ArithmeticException`

makes sense for this purpose.

` @Test(expected = ArithmeticException.class)`

public void testGCDIntMinVal() {

gcd(Integer.MIN_VALUE, Integer.MIN_VALUE);

}

If you prefer the “old school” try-catch with fail, you can also have the test report the erroneous result (probably 0) if the exception is not triggered.

Once you have this test fail because `gcd()`

did not `throw new ArithmeticException`

for this edge case, you can go ahead and write where that actually happens.

Depending on how you actually implement `gcd()`

, it could be the case that `ArithmeticException`

arises for this edge case without your having to actually write a throw statement.

By writing the test first, you can then see if it really is necessary for you to make any changes to what you have so far. It might be, it might not be, the results of the test will tell you.

That’s the point of TDD: write the test, then, if necessary, write what’s needed to pass the test. Don’t write more than what is necessary, let the tests show you what is needed and what isn’t.

I hope someone has already told you this. I also hope my exposition here has made it clearer in your mind.