"Good Enough" Testing for Infinite Inputs

As of late, I have spent a decent amount of time focused on testing.  I released an updated version of my Coded UI Fluent Extensions.  These extensions are for testing UI so it is not really important to test all combinations of inputs since what you are really testing in the UI whether things are bound correctly and trigger events expected.

When unit testing, typically we want to test as many different inputs that have meaningful results as possible.  When the inputs are finite you could test all inputs.  What about inputs that are infinite; and is infinite really something real in programming?  Consider I have a function that takes an int and returns the square.  Well, we know that only the first (int)sqrt(int.MaxValue) will work even if integers are infinite.  What about a function that reads from a stream and computes a hash of the entire stream; but the stream never ends?

Let's consider an example where we want to test an improved implementation of an existing algorithm.  Common problems for testing would be the Bag Packing problem or Fibonacci Sequence.

In the case of Fibonacci Sequence, I could compute all numbers in the sequence that fit within UInt64 or whatever structure, but consider GoLang which supports infinitely sized numbers.  Because a function can be implemented in an infinite number of ways, there would be no way to ensure that it works for *all* inputs.  I would argue that a requirement to work with *all* inputs is rarely needed.  In such cases, proving the implementation works by actually looking at the implementation would probably be the only testing strategy.

In most cases, however, testing a finite input set is 'good enough'.  We can always add bad values to regression tests as they are found over time.  Most apps can handle this and the cost of dealing with these cases is way smaller than the cost of provably perfect code.

In these cases that can handle 'good enough' testing, I would say using a crude implementation to test against is the best approach.  These results can be stored if the computation is too expensive, but then the implementation would really be a look up table in most cases :)

Also, how often does a test need to be run against code that doesn't change?  Or, changes relatively slowly.  A slow test for slowly changing code seems reasonable when the coverage makes sense.

When I used to do coding challenges, I asked the students to implement the bag packing algorithm.  I had a set of objects which I would use to test their implementations.  Using the Test-All-Combinations approach to see which was best, I was able to generate all bags in just over 4 hours, but to write the code, I was done in about 20 minutes. Students were able to find bags in seconds, but not all were implemented correctly and I could prove my bags were correct.  Further, implementing the improved algorithm took hours and hours.

This is not possible to do against all inputs; there are an infinite number of items that can go into bags with infinitely different sizes, but against a set of inputs that could not be predicted by the implementer is a sufficient for 'good enough' testing.

Well, that's my 2c anyway!