Data structure kata: exact square roots

Many programming courses introduce the concept of data structures with complex numbers as a motivating example. Most commonly, these structures use floating-point values to represent the parts, e.g.:

// Real + Imag * i
public struct Complex
{
    public double Real;
    public double Imag;
}

This is fine for approximations, but what if we want to exactly represent the solutions to the equation x² + 50 = 0? That is, rather than ±7.0710678...*i, we want ±5*sqrt(2)*i — yes, that includes simplification of the value under the radical (making it square-free as a math professor would say).

It turns out that this is a nice little code kata — simple enough to express in a few sentences, but with many possible solutions and nearly endless potential for extension.

Here is my solution to the problem, using a C# struct called RootTerm to represent a possibly irrational and possibly imaginary quantity involving a square root: RootSample on GitHub.

A brief overview of my process:

• Start with a simple case, where the numbers are perfect squares (commit link)
• Extend this to support extracting factors of four, e.g. sqrt(8) = 2*sqrt(2) (commit link)
• Extract factors of nine (commit link)
• Extract factors of 25 (commit link)
• Add cases for irreducible composites, i.e. numbers like 15 which are already square-free (commit link)
• For good measure, add cases for prime numbers, which are always irreducible (commit link)
• At this point, we need to start supporting all possible positive Int32 values, so we need a huge table of prime numbers! (commit link)
• After a few refactorings, move on to tackle imaginary numbers by allowing the value to be negative (commit link)
• Ensure the string output is formatted correctly by adding a few more tests (commit link)
• The struct is mostly functional at this point so tests are added without much fanfare (commit link)
• Solve one final issue with the special case for int.MinValue (commit link)

As I mentioned, this solution can be extended to support many other features. For example, adding two RootTerms poses an interesting challenge, in that the answer may be some totally different type of number that we cannot yet represent like sqrt(2) + sqrt(3) (our friendly math professor would say that “RootTerm is not closed under addition”). Solving that would require another data structure. Stay tuned for further exploration of this and other problems.