Baby steps towards test-driven development in my hobby projects

A year ago, I started to realize how useful automated testing of a computer program can be. Even a hobby project can benefit from testing besides just running the program and seeing if it works like you expect.

It was only more recently that I started to understand that writing tests before writing the intended program can be very freeing.

Back in February, I wrote about how I started doing unit testing in my biggest Java hobby project so far, a program that draws diagrams of prime numbers in certain domains of “imaginary” numbers.

Back then I was skeptical of test-driven development, but now that I’ve been doing it in classwork and a little bit in one of my hobby projects, I have come around to that way of thinking about programming.

I mentioned in that previous article that I wasn’t doing test-driven development, and that I might change to that paradigm if I got a job at a place where they work that way. That was a presumptuous thing for me to say.

Assuming a fair hiring scenario (a very big assumption), the fact is that back then I had no test-driven development experience, practical or academic. There is just no way I could have gotten a job at a test-driven shop back then.

I knew the dictionary definition, but I did not know how it works in the writing of an actual program, even if it’s just a toy program that merely duplicates the functionality of a widely available program.

I did not know the nuts and bolts, such as that the first thing to actually be written is a class stub, at least when working with an integrated development environment (IDE). Unless you like typing a bunch of red lines into your IDE.

The purest way to do test-driven development (not necessarily the most practical) is to start by writing the tests in a plain text editor, preferably one accessed from the command line.

You can run JUnit from the command line, right? Probably. But excessive purism probably diminishes the benefits of unit testing and test-driven development.

So yeah, in your favorite IDE, write the stubs first, then the tests, then go back to the stubs and flesh them out. Here’s an example of a stub for a class to be tested:

* (IDE-generated boilerplate for Javadoc)
public class Dashboard extends Screen implements Updateable {

In this example, it might be necessary to also write stubs for the functions Updateable requires Dashboard to implement, before going on to write DashboardTest in the test folder.

IntelliJ offers to create all those, and it helpfully puts in the @Override annotation and, when applicable, a return value generally useful for the purpose of getting a failing first test.

These are simple details, but they are details that were unknown to me just a few months ago.

Now I’m taking a course that fills in all those concepts missing from all the coding boot camps, even the good ones (like the former Iron Yard, which I was accepted to just before it went out of business).

One of those concepts which coding boot camp grads are just as clueless about as I was is test-driven development. The course I’m now taking is very dogmatic (but not purist) about test-driven development.

And it should be dogmatic but not purist. This is not counterpoint with Simon Sechter. By that I mean that there is no proscription against my continuing to work on my hobby projects for the duration of the course.

Nor am I required to use test-driven development principles in my hobby projects. But I can very well decide to start using those principles in my hobby projects gradually, in ways that make sense to me, and I have.

I suppose the purest way to switch over to test-driven development in my prime numbers diagram project would be to delete everything I have so far and start over with the tests.

It would still be quite radical to delete everything in the source folder and rewrite those from scratch but keep the tests I already wrote. I could actually do that, since I have the safety net of the whole project being backed up on GitHub.

What makes more sense to me, though, is to write tests for features of the program I haven’t implemented yet but have been thinking about.

Like some of the wish list features, such as the ability to drag a diagram around like you can drag a map on Google Maps. Or “under the hood” features that could make the source code cleaner and better encapsulated.

I can’t remember for how long I’ve been thinking the diagram program maybe needs to have the Legendre, Jacobi and Kronecker symbol functions. Those are mathematical functions that pertain to equations with squares of integers.

I’m going to try to keep the math stuff very simple, maybe to the point of oversimplification, so as to not get too sidetracked from the topic of unit testing.

The program definitely needs the Legendre symbol, so that I can move some number-theoretic aspects out of the RingWindowDisplay class, and have that be concerned mostly only with the drawing the diagrams.

For one thing, RingWindowDisplay.drawPoints() actually does some arithmetic to determine the colors of the primes, rather than shipping that logic off to NumberTheoreticFunctionsCalculator.

A diagram produced by Version 0.9 of my program. I added the numeric text in Photoshop Elements.

And I have to admit that some of these colors are not quite correct: maybe √−5 should be in cyan, not lime green like 5; 2 should be lime green like 5; and there should be some indication that 3, 7 and 23 are irreducible but not prime in this domain.

If the Kronecker and Legendre symbols were implemented in NumberTheoreticFunctionsCalculator and available for RingWindowDisplay to use, that would go a long way towards encapsulation.

The Legendre symbol is a function that tells you whether the equation x² = pm + a can be solved; p is an odd prime number like 7 or 19, a is some integer, like −6 or 35, and m is also an integer but we’re not too worried about its actual value (and in any case, if the equation has any solution at all, there are several values of m that will work — infinitely many, in fact).

For the sake of this article, I will notate it as Legendre(a, p), which very neatly corresponds to Legendre(int a, int p) in a computer programming language like Java or C++ (the notation mathematicians use has problems, but that’s a topic for another day).

Is there a solution to, say, x² = 7m − 6, which is the same thing as x² = 7m + 1? Yes, there is, but the Legendre symbol function Legendre(-6, 7) should tell us this not by returning true but by returning 1.

This is relevant to my prime diagrams program because then we know that although 7 is prime in Z (the familiar set of positive and negative integers, and 0) it’s not prime in Z[√−6], since (1 − √−6)(1 + √−6) = 7 (you can verify this on some online calculators with (1 - sqrt(-6))(1 + sqrt(-6))).

Compare this to Legendre(-6, 19) returning -1 to indicate that x² = 19m − 6 has no solutions. This tells us that 19 is prime in both Z and Z[√−6].

Likewise Legendre(35, 19) = 1 tells us x² = 19m + 35 (or 19m + 16) does have solutions, and, although 19 is prime in Z, it’s not prime in Z[√35], since (4 − √35)(4 + √35) = −19 (this one is easier to verify on a typical calculator).

By not tying this to the duality of the boolean return type, there is also the option to return 0. As in, for example, Legendre(-6, 3) returns 0 and Legendre(35, 7) also returns 0.

The formula for the Legendre symbol is simple: raise a to the power of half of p − 1, and repeatedly add or subtract p from that until getting −1, 0 or 1 (I’m deliberately avoiding congruence notation because it’s sometimes perceived as difficult or advanced).

For instance, to compute Legendre(−6, 7), we find that (−6)³ = −216, then repeatedly add 7 to that until we get 1.

The crucial line for the Legendre symbol function in our implementation might look something like this:

Easy, right? But there are several wrinkles here, with Java’s lack of an exponent operator being the least of our worries.

So at this point we know exactly what to expect from this function but we don’t know exactly how to make it give us what we expect. It’s a perfect case for test-driven development. So let’s write the test first…

No, actually, let’s write the function stub first. Warnings can be just as distracting as errors, but I generally find it easier to ignore warnings than to ignore errors.

Writing the function stub first makes it easier to concentrate, in my opinion. Besides, it’s better to have the first test failure happen because of an assertion failure rather than a compilation failure.

And it still counts as test-driven development, right? So long as we don’t write too much of the function at this early juncture.

To write the stub, we just need the relevant access modifier, return type, function name, parameter list and a line returning some obviously incorrect value.

Often −1 is used for this purpose, but in this instance it could lead to a test passing in a misleading manner. So then:

That should be enough so that when we write testLegendreSymbol() we only get meaningful errors and warnings (or mostly only — on another occasion I should write about the less helpful warnings in both NetBeans and IntelliJ).

Before actually writing the test, please bear with me as I go over a mathematical concept that will help us test our implementation of the Legendre symbol: the fact of quadratic reciprocity.

In the examples earlier, I was careful to choose composite a. But a can just as easily be a prime number, too. In that case it’s commonly notated as q rather than a.

Quadratic reciprocity tells us that if p and q are both odd primes, then Legendre(p, q) = Legendre(q, p) unless both p and q are primes of the form 4k − 1, in which case Legendre(p, q) = (−1)Legendre(q, p).

In the previous paragraph it is understood that p and q are both positive primes. I’m not going to talk about the subtleties with negative primes as I think it would be too much of a digression.

And of course I’m not going to give a proof of quadratic reciprocity here. Any elementary number theory textbook is likely to have a proof of it, under the title of “quadratic reciprocity law” (I prefer to call it a “fact” rather than a “law”).

So I’m just going to give a few examples before presenting the test. Let’s say p = 5 and q = 7. We do the calculations, we should get Legendre(5, 7) = −1 and Legendre(7, 5) = −1 also.

This means that x² = 5m + 7 (or 5m + 2) has no solutions, and x² = 7m + 5 (or 7m − 2) has no solutions either.

Compare this to Legendre(5, 19) = 1 and Legendre(19, 5) = 1 also. This means that both x² = 5m + 19 (or 5m + 4) and x² = 19m + 5 have solutions. We also see that (1 − 2√5)(1 + 2√5) = −19 and (9 − 2√19)(9 + 2√19) = 5.

The major contrast in these quadratic reciprocity examples is Legendre(7, 19) = 1 and Legendre(19, 7) = −1. There is no reciprocity because both 7 and 19 are of the form 4k − 1.

So x² = 19m + 7 has solutions but x² = 7m + 19 (or 7m + 5) does not. And (3 − 2√7)(3 + 2√7) = −19 but 7 is prime in Z[√19].

I think that’s enough information to write a good test. Let’s say the test suite setup already includes a list of a hundred consecutive primes or so in order, starting with 2 (which is why pindex will start at 1 rather than 0, to only iterate through odd primes).

Another property of the Legendre symbol we can use is that it is multiplicative: Legendre(ab, p) = Legendre(a, p) Legendre(b, p). Given that −6 times 35 is −210, it should be easy to verify from previous examples that Legendre(−210, 7) = 0 and Legendre(−210, 19) = −1.

I won’t quote the test for the multiplicative property here. You can either figure it out yourself or look in my GitHub repository linked earlier.

Actually, for the purpose of this article, I wrote a new one that uses Legendre((p + 1)q, p) = Legendre(p + 1, p) Legendre(q, p). There are of course many other possibilities.

In either case, the tests should probably be renamed, one to something like testLegendreSymbolWithQuadRecip() and the other to something like testLegendreSymbolWithMult().

I do admit this gives the impression that the tests in my project are a lot more granular than they actually are. Maybe later on I’ll break them up more or less like they’re broken up here.

There is a problem with these two tests so far, and that’s that they could both pass even if our implementation always gives the opposite result of the correct result when a and p are coprime (that is, always −1 when it should be 1, and vice-versa).

But that’s fixed easily enough by adding a test that checks a few specific pairs of arguments:

That should be a robust enough group of tests for our implementation of the Legendre symbol.

If, for example, our implementation were to give the wrong result for Legendre(5, 7) but the right result for all other Legendre(a, 7), probably neither the quadratic reciprocity test and the multiplicative test would catch that but the specific values test would.

Okay, now we should run the tests and verify that our function stub (the one that returns −2) does indeed cause our tests to fail with assertion failures.

That is the case: the reciprocity test fails because it expects Legendre(3, 7) to be 2 rather than −2; the multiplicative test fails because it expects Legendre(20, 3) to be 4 rather than −2; and the specific values test fails because it expects Legendre(19, 7) to be −1, not −2.

Now we’re ready to actually write symbolLegendre(int a, int p). Here’s the first try:

The three tests all fail, but it takes the computer a tiny bit longer to find the failing cases: the reciprocity test fails because it expects Legendre(3, 5) to be 2 rather than 4; the multiplicative test fails because it expects Legendre(1336, 7) to be 6 rather than 1; and the specific values test fails because it expects Legendre(19, 7) to be −1, not 6.

This time around, the specific values test was the most immediately informative. Since 6 − 7 = −1, it looks like our implementation just needs one more tweak:

A new run of the test shows there’s more work to do here: the reciprocity test fails because it expects Legendre(3, 41) to be −1 rather than 38; the multiplicative test fails because it expects Legendre(1336, 7) to be −1 rather than 1; and the specific values test fails because it expects Legendre(42, 19) to be 1, not 2.

For the erroneous return of 38 for Legendre(3, 41), you’re either scratching your head or you have already figured out that 3²⁰ = 3486784401 is greater than 2³¹ = 2147483648.

Then, when the double result of Math.pow(a, expo) is cast to an int, an overflow occurs.

We could change a and p to each be long rather than int. But that will probably only postpone the overflow problems. And to use BigInteger just to compute Legendre(5, 3) seems like overkill.

A better solution, I think, is either to get some kind of power mod from a library or implement it yourself. Then, if, for example, we have the power mod in the same class we might write:

This should be good for most of our purposes, though we might run into problems with, say, symbolLegendre(Integer.MAX_VALUE - 18, Integer.MAX_VALUE).

If you’re concerned about that specific use case, or similar use cases, you might want to add a line or two to the specific values test. Both 2³¹ − 1 and 2³¹ − 19 are prime, by the way.

Nothing in the tests presented here mandates what should happen if p is not an odd prime.

There are a couple of options: you could have symbolLegendre throw a runtime exception, like IllegalArgumentException, or you could have it quietly pass the arguments to symbolJacobi or symbolKronecker as needed.

Whatever you decide, it would be a good idea to write a test for it first. An expected exception rule annotation or the appropriate setting of expResult are two options that suggest themselves.

I won’t go over the Jacobi and Kronecker symbols here. Suffice it to say that I used −3 in the symbolJacobi(a, m) stub and −4 in the symbolKronecker(a, b) stub.

And also that I have written actual implementations for the Jacobi and Kronecker symbols as well that pass the tests, but I am always free to improve the algorithms.

Overall, test-driven development is very freeing because it gives you the freedom to try different things, knowing that you always have something to check it against, and that you don’t have to get it just right the very first time.

The first run of the test will fail, that’s just a given. The second run of the test might pass, but it might not be the most efficient algorithm. In this way, there is no pressure to get it exactly right the first time.

Also, by testing first, testing doesn’t feel like a chore. In Java: The Good Parts, Prof. Jim Waldo likens testing to flossing your teeth. This probably means he wasn’t testing first.

I’m not going to test first for every thing in this hobby project. It would be silly, for example, to first test PNGFileFilter, for example, because that’s a very simple thing I mostly just copied off the Internet, which is itself in turn obviously the result of following a standard Java API.

And I’m almost certainly not going to unit test the graphical user interface (GUI) components, that’s usually a major pain in the neck just for the sake of high coverage.

Maybe I’ll revise my opinion on this later, but for now it seems to me that unit testing GUI components doesn’t catch the problems you’d like to catch, leaving a lot for integration testing, quality assurance and end user testing to catch.

Almost everything else, yeah, I’m going to be unit testing it, and usually writing the unit tests before the actual implementations.

is a composer and photographer from Detroit, Michigan. He has been working on a Java program to display certain mathematical diagrams.