How do you write unit tests for code with difficult to predict results?

Question

I frequently work with very numeric / mathematical programs, where the exact result of a function is difficult to predict in advance.

In trying to apply TDD with this kind of code, I often find writing the code under test significantly easier than writing unit tests for that code, because the only way I know to find the expected result is to apply the algorithm itself (whether in my head, on paper, or by the computer). This feels wrong, because I am effectively using the code under test to verify my unit tests, instead of the other way around.

Are there known techniques for writing unit tests and applying TDD when the result of the code under test is difficult to predict?

A (real) example of code with difficult to predict results:

A function weightedTasksOnTime that, given an amount of work done per day workPerDay in range (0, 24], the current time initialTime > 0, and a list of tasks taskArray; each with a time to complete property time > 0, due date due, and importance value importance; returns a normalized value in range [0, 1] representing the importance of tasks that can be completed before their due date if each task if completed in the order given by taskArray, starting at initialTime.

The algorithm to implement this function is relatively straightforward: iterate over tasks in taskArray. For each task, add time to initialTime. If the new time < due, add importance to an accumulator. Time is adjusted by inverse workPerDay. Before returning the accumulator, divide by sum of task importances to normalize.

function weightedTasksOnTime(workPerDay, initialTime, taskArray) {
    let simulatedTime = initialTime
    let accumulator = 0;
    for (task in taskArray) {
        simulatedTime += task.time * (24 / workPerDay)
        if (simulatedTime < task.due) {
            accumulator += task.importance
        }
    }
    return accumulator / totalImportance(taskArray)
}

I believe the above problem can be simplified, while maintaining its core, by removing workPerDay and the normalization requirement, to give:

function weightedTasksOnTime(initialTime, taskArray) {
    let simulatedTime = initialTime
    let accumulator = 0;
    for (task in taskArray) {
        simulatedTime += task.time
        if (simulatedTime < task.due) {
            accumulator += task.importance
        }
    }
    return accumulator
}

This question addresses situations where the code under test is not a re-implementation of an existing algorithm. If code is a re-implementation, it intrinsically has easy to predict results, because existing trusted implementations of the algorithm act as a natural test oracle.

Answer 1

There are two things you can test in difficult-to-test code. First, the degenerate cases. What happens if you have no elements in your task array, or only one, or two but one is past the due date, etc. Anything that is simpler than your real problem, but still reasonable to calculate manually.

The second is the sanity checks. These are the checks you do where you don't know if an answer is right, but you definitely would know if it's wrong. These are things like time must move forward, values must be in a reasonable range, percentages must add up to 100, etc.

Yes, this isn't as good as a full test, but you'd be surprised how often you mess up on the sanity checks and degenerate cases, that reveals a problem in your full algorithm.

Answer 2

I used to write tests for scientific software with difficult-to-predict outputs. We made a lot of use of Metamorphic Relations. Essentially there are things you know about how your software should behave even if you don't know exact numerical outputs.

A possible example for your case: if you decrease the amount of work you can do each day then the total amount of work you can do will at best stay the same, but likely decrease. So run the function for a number of values of workPerDay and make sure the relation holds.

Answer 3

The other answers have good ideas for developing tests for edge or error case. For the others, using the algorithm itself is not ideal (obviously) but still useful.

It will detect if the algorithm (or data it depends on) has changed

If the change is an accident, you could roll back a commit. If the change was deliberate, you need to revisit the unit test.

Answer 4

The same way you write unit tests for any other kind of code:

1. Find some representative test cases, and test those.
2. Find edge cases, and test those.
3. Find error conditions, and test those.

Unless your code involves some random element or is not deterministic (i.e. it won't produce the same output given the same input), it is unit testable.

Avoid side-effects, or functions that are affected by outside forces. Pure functions are easier to test.

Answer 5

Update due to posted comments

The original answer was removed for brevity's sake - you can find it in the edit history.

PaintingInAir For context: as an entrepreneur and academic, most of the algorithms I design are not requested by anyone other than myself. The example given in the question is part of a derivative-free optimizer to maximize the quality of an ordering of tasks. In terms of how I described the need for the example function internally: "I need an objective function to maximize the importance of tasks that are completed on time". However, there still seems to be a large gap between this request and the implementation of unit tests.

First, a TL;DR to avoid an otherwise lengthy answer:

Think of it this way:
A customer enters McDonald's, and asks for a burger with lettuce, tomato and hand soap as toppings. This order is given to the cook, who makes the burger exactly as requested. The customer receives this burger, eats it, and then complains to the cook that this is not a tasty burger!

This is not the cook's fault - he's only doing what the customer explicitly asked. It's not the cook's job to check if the requested order is actually tasty. The cook simply creates that which the customer orders. It's the customer's responsibility of ordering something that they find tasty.

Similarly, it's not the developer's job to question the correctness of the algorithm. Their only job is to implement the algorithm as requested.
Unit testing is a developer's tool. It confirms that the burger matches the order (before it leaves the kitchen). It does not (and should not) try to confirm that the ordered burger is actually tasty.

Even if you are both the customer and the cook, there is still a meaningful distinction between:

• I did not prepare this meal properly, it was not tasty (= cook error). A burnt steak is never going to taste good, even if you like steak.
• I prepared the meal properly, but I don't like it (= customer error). If you don't like steak, you'll never like eating steak, even if you cooked it to perfection.

The main issue here is that you're not making a separation between the customer and the developer (and the analyst - though that role can be represented by a developer as well).

You need to distinguish between testing the code, and testing the business requirements.

For example, the customer wants it to work like [this]. However, the developer misunderstands, and he writes code that does [that].

The developer will therefore write unit tests that test if [that] works as expected. If he developed the application correctly, his unit tests will pass even though the application doesn't do [this], which the customer was expecting.

If you want to test the customer's expectations (the business requirements), that needs to be done in a separate (and later) step.

A simple development workflow to show you when these tests should be run:

• The customer explains the problem they want to solve.
• The analyst (or developer) writes this down in an analysis.
• The developer writes code that does what the analysis describes.
• The developer tests his code (unit tests) to see if he followed the analysis correctly
• If the unit tests fail, the developer goes back to developing. This loops indefinitely, until the unit tests all pass.
• Now having a tested (confirmed and passed) code base, the developer builds the application.
• The application is given to the customer.
• The customer now tests if the application he is given actually solves the problem that he sought to solve (QA tests).

You may wonder what the point is of doing two separate tests when the customer and developer are one and the same. Since there is no "hand off" from developer to customer, the tests are run one after the other, but they are still separate steps.

• Unit tests are a specialized tool that helps you verify whether your development stage is finished.
• QA tests are done by using the application.

If you want to test whether your algorithm itself is correct, that is not part of the developer's job. That is the customer's concern, and the customer will test this by using the application.

As an entrepreneur and academic, you might be missing an important distinction here, which highlights the different responsibilities.

• If the application doesn't adhere to what the customer had initially asked, then the subsequent changes to the code are usually done free of charge; since it's a developer error. The developer made a mistake and must pay the cost of rectifying it.
• If the application does what the customer had initially asked, but the customer has now changed his mind (e.g. you've decided to use a different and better algorithm), the changes to the code base are charged to the customer, since it's not the developer's fault that the customer asked for something different than what they now want. It's the customer's responsibility (cost) to change their mind and therefore have the developers spend more effort to develop something that was not previously agreed to.

Answer 6

Property Testing

Sometimes mathematical functions are better served by "Property Testing" than by traditional example-based unit testing. For example, imagine you're writing unit tests for something like an integer "multiply" function. While the function itself may seem very simple, if it's the only way to multiply, how do you test it thoroughly without the logic in the function itself? You could use giant tables with expected inputs/outputs, but this is limited and error-prone.

In these cases, you can test known properties of the function, instead of looking for specific expected results. For multiplication, you may know that multiplying a negative number and a positive number should result in a negative number, and that multiplying two negative numbers should result in a positive number, etc. Using randomized values and then checking that these properties are preserved for all test values is a good way to test such functions. You generally need to test for more than one property, but you can often identify a finite set of properties that together validate the correct behavior of a function without necessarily knowing the expected result for every case.

One of the best introductions to Property Testing that I've seen is this one in F#. Hopefully the syntax is not an obstruction to understanding the explanation of the technique.

Answer 7

It is tempting to write the code and then see if the result "looks right", but, as you rightly intuit, it's not a good idea.

When the algorithm is hard you can do a number of things to make the manual calculation of the result easier.

1. Use Excel. Set up a spreadsheet that does some or all of the calculation for you. Keep it simple enough so that you can see the steps.

2. Split your method up into smaller testable methods, each with their own tests. When you are sure the smaller parts work, use them to manually work through the next step.

3. Use aggregate properties to sanity-check. For example, say you have a probability calculator; you might not know what the individual results should be, but you know they all have to add up to 100%.

4. Brute force. Write a program that generates all possible results, and check that none are better than what your algorithm generates.

Answer 8

Other answers are good, so I'll try to hit on some points they've collectively missed so far.

I have written (and thoroughly tested) software to do image processing using Synthetic Aperture Radar (SAR). It's scientific/numerical in nature (there's a lot of geometry, physics, and math involved).

A couple of tips (for general scientific/numerical testing):

1) Use inverses. What's the fft of [1,2,3,4,5]? No idea. What's ifft(fft([1,2,3,4,5]))? Should be [1,2,3,4,5] (or close to it, floating point errors might come up). Same goes for the 2D case.

2) Use known asserts. If you write a determinant function, it might be hard to say what the determinant is of a random 100x100 matrix. But you do know that the determinant of the identity matrix is 1, even if it's 100x100. You also know that the function should return 0 on a non-invertible matrix (like a 100x100 full of all 0s).

3) Use rough asserts instead of exact asserts. I wrote some code for said SAR processing that would register two images by generating tie points that create a mapping between the images and then doing a warp between them to make them match. It could register at a sub-pixel level. A priori, it's hard to say anything about what the registration of two images might look like. How can you test it? Things like:

EXPECT_TRUE(register(img1, img2).size() < min(img1.size(), img2.size()))

since you can only register on overlapping parts, the registered image must be smaller or equal to your smallest image, and also:

scale = 255
EXPECT_PIXEL_EQ_WITH_TOLERANCE(reg(img, img), img, .05*scale)

since an image registered to itself should be CLOSE to itself, but you might experience a bit more than floating point errors due to the algorithm at hand, so just check each pixel is within +/- 5% of the range the pixels can take on (0-255 is greyscale, common in image processing). Result should at least be the same size as input.

You can even just smoke test (i.e. call it and make sure it doesn't crash). In general, this technique is better for larger tests where the end result can't be (easily) calculated a priori to running the test.

4) Use OR STORE a random number seed for your RNG.

Runs do need to be reproducible. It is false, however, that the only way to get a reproducible run is to provide a specific seed to a random number generator. Sometimes randomness testing is valuable. I've seen/heard about bugs in scientific code that crop up in degenerate cases that were randomly generated (in complicated algorithms it can be hard to see what the degenerate case even is). Instead of always calling your function with the same seed, generate a random seed, and then use that seed, and log the seed's value. That way every run has a different random seed, but if you get a crash, you can re-run the result by using the seed you've logged to debug. I've actually used this in practice and it squashed a bug, so I figured I'd mention it. Admittedly this has only happened once, and I'm positive it's not always worth doing, so use this technique with prudence. Random with the same seed is always safe, though. Downside (as opposed to just using the same seed all the time): You have to log your test runs. Upside: Correctness and bug nuking.

Your particular case

1) Test that an empty taskArray returns 0 (known assert).

2) Generate random input such that task.time > 0, task.due > 0, and task.importance > 0 for all tasks, and assert the result is greater than 0 (rough assert, random input). You don't need to go crazy and generate random seeds, your algorithm just isn't complex enough to warrant it. There's about 0 chance it would pay off: just keep the test simple.

3) Test if task.importance == 0 for all tasks, then result is 0 (known assert)

4) Other answers touched on this, but it might be important for your particular case: If you're making an API to be consumed by users outside of your team, you need to test the degenerate cases. For instance, if workPerDay == 0, make sure you throw a lovely error that tells the user that's invalid input. If you're not making an API, and it's just for you and your team, you can probably skip this step, and just refuse to call it with the degenerate case.

HTH.

Answer 9

TL;DR

Head to "comparative testing" section for advice that's not in other answers.

---

Beginnings

Start by testing the cases that should be rejected by the algorithm (zero or negative workPerDay, for example) and the cases that are trivial (e.g. empty tasks array).

After that, you want to test the simplest cases first. For the tasks input, we need to test different lengths; it should be sufficient to test 0, 1 and 2 elements (2 belongs to the category "many" for this test).

If you can find inputs that can be mentally calculated, that's a good start. A technique I sometimes use is to start from a desired result and work back (in the spec) to inputs that should produce that result.

Comparative testing

Sometimes the relation of the output to the input isn't obvious, but you have a predictable relationship between different outputs when one input is changed. If I've understood the example correctly, then adding a task (without changing other inputs) will never increase the proportion of work done on time, so we can create a test that calls the function twice - once with and once without the extra task - and asserts the inequality between the two results.

Fallbacks

Sometimes I've had to resort to a long comment showing a hand-computed result in steps corresponding to the spec (such a comment is usually longer than the test case). The worst case is when you have to maintain compatibility with an earlier implementation in a different language or for a different environment. Sometimes you just have to label the test data with something like /* derived from v2.6 implementation on ARM system */. That's not very satisfying, but may be acceptable as a fidelity test when porting, or as a short-term crutch.

Reminders

The most important attribute of a test is its readability - if the inputs and outputs are opaque to the reader, then the test has very low value, but if the reader is helped to understand the relationships between them, then the test serves two purposes.

Don't forget to use an appropriate "approximately-equals" for inexact results (e.g. floating-point).

Avoid over-testing - only add a test if it covers something (such as a boundary value) that's not reached by other tests.

Answer 10

There is nothing very special about this kind of hard-to-test function. The same applies for code that uses external interfaces (say, a REST API of a 3rd party application which is not under your control and certainly not up to be tested by your test suite; or using a 3rd party library where you are unsure of the exact byte format of return values).

It is a quite valid approach to simply run your algorithm for some sane input, see what it does, make sure that the result is correct, and encapsulate the input and the result as a test case. You can do this for a few cases and thus get several samples. Try to make the input parameters as different as possible. In the case of an external API call, you would do a few calls against the real system, trace them with some tool, and then mock them into your unit tests to see how your program reacts - which is the same as just picking a few runs of your task planning code, verifying them by hand, and then hardcoding the result in your tests.

Then, obviously, bring in edge cases like (in your example) an empty list of tasks; things like that.

Your test suite will maybe not be as great as for a method where you can easily predict results; but still 100% better than no test suite (or just a smoke test).

If your problem, though, is that you find it hard to decide whether a result is correct, then that is an altogether different problem. For example, say you have a method which detects whether an arbitrarily large number is prime. You can hardly throw any random number at it and then just "look" if the result is correct (assuming you cannot decide the prime-ness in your head or on a piece of paper). In this case, there is indeed little you can do - you'd need to either get known results (i.e., some large primes), or implement the functionality with a different algorithm (maybe even a different team - NASA seems to be fond of that) and hope that if either implementation is buggy, at least the bug does not lead to the same wrong results.

If this is a regular case for you, then you have to have a good hard talk with your requirements engineers. If they cannot formulate your requirements in a way that is easy (or at all possible) to check for you, then when do you know whether you are finished?

Answer 11

Incorporate assertion testing into your unit test suite for property-based testing of your algorithm. In addition to writing unit tests which check for specific output, write tests designed to fail by triggering assertion failures in the main code.

Many algorithms rely for their correctness proofs on maintaining certain properties throughout the stages of the algorithm. If you can sensibly check these properties by looking at the output of a function, unit testing alone is enough to test your properties. Otherwise, assertion-based testing lets you test that an implementation maintains a property every time the algorithm assumes it.

Assertion-based testing will expose algorithm flaws, coding bugs, and implementation failures due to issues such as numerical instability. Many languages have mechanisms strip assertions at compile time or prior to the code being interpreted so that when run in production mode the assertions do not incur a performance penalty. If your code passes unit tests but fails on a real-life case, you can turn the assertions back on as a debugging tool.

Answer 12

Some of the other answers here are very good:

• Test base, edge, and corner cases
• Perform sanity checks
• Perform comparative tests

... I'd add a few other tactics:

• Decompose the problem.
• Prove the algorithm outside of code.
• Test that the [externally proven] algorithm is implemented as-designed.

Decomposition allows you to ensure the components of your algorithm do what you expect them to do. And a "good" decomposition lets you also ensure they're glued together properly. A great decomposition generalizes and simplifies the algorithm to the extent that you can predict the results (of the simplified, generic algorithm(s)) by hand well enough to write thorough tests.

If you can't decompose to that extent, prove the algorithm outside of code by whatever means is sufficient to satisfy you and your peers, stakeholders, and customers. And then, just decompose enough to prove your implementation matches the design.

Answer 13

This might seem like somewhat of an idealistic answer but it helps to identify different kinds of testing.

If strict answers are important to the implementation then examples and expected answers really should be provided in the requirements that describes the algorithm. These requirements should be group reviewed and if you don't get the same results, the reason needs to be identified.

Even if you are playing the role of analyst as well as implementer you should actually create requirements and have them reviewed long before you are writing unit tests, so in this case you will know the expected results and can write your tests accordingly.

On the other hand, if this is a part you are implementing that either is not part of the business logic or supports a business logic answer then it should be fine to run the test to see what the results are and then modify the test to expect those results. The end results are already checked against your requirements so if they are correct then all the code feeding those end results must be numerically correct and at that point your unit tests are more to detect edge failure cases and future refactoring changes than to prove that a given algorithm produces correct results.

Answer 14

I think it's perfectly acceptable on occasions to follow the process:

• design a test case
• use your software to get the answer
• check the answer by hand
• write a regression test so future versions of the software will continue to give this answer.

This is a reasonable approach in any situation where checking the correctness of an answer by hand is easier than computing the answer by hand from first principles.

I know people who write software for rendering printed pages, and have tests that check that exactly the right pixels are set on the printed page. The only sane way to do that is to write the code to render the page, check by eye that it looks good, and then capture the result as a regression test for future releases.

Just because you read in a book that a particular methodology encourages writing the test cases first, doesn't mean you always have to do it that way. Rules are there to be broken.

Answer 15

Other answers answers already have techniques for what a test looks like when the specific result cannot be determined outside the tested function.

What I do additionally which I have not spotted in the other answers is to auto-generate tests in some way:

1. 'Random' inputs
2. Iteration across ranges of data
3. Construction of test cases from sets of boundaries
4. All the above.

For example, if the function takes three parameters each with allowed input range [-1,1], test all combinations of each parameter, {-2,-1.01,-1,-0.99, -0.5,-0.01, 0,0.01,0.5,0.99,1,1.01,2, some more random in (-1,1)}

In short: Sometimes poor quality can be subsidised by quantity.