Exact square roots (continued)

Last week, I introduced a data structure kata involving exact square roots. At the time of that writing, I had implemented a RootTerm struct which could represent real and imaginary square roots. Today we’ll pick up where we left off by implementing addition and multiplication operations.

Multiplication turns out to be the easier operation since (barring overflow) the product of two values of the form C*sqrt(X) will always be of that same form. In other words, any RootTerm times any other RootTerm will still produce a RootTerm.

To get started, I added a failing test for products involving square roots of perfect squares (i.e. integers). Ultimately, this naïve implementation emerged:

public RootTerm Multiply(RootTerm other) => new RootTerm(this.c * other.c, this.x * other.x);

Obviously, this doesn’t work for most cases, so I added another set of failing examples whose products become integers after simplification (e.g. sqrt(3)*sqrt(27) = sqrt(81) = 9). To make these cases work, I changed the code thusly:

public RootTerm Multiply(RootTerm other)
{
    RootTerm r = Sqrt(this.x * other.x);
    return new RootTerm(this.c * other.c * r.c, r.x);
}

We’re getting closer, but imaginary numbers still don’t work (e.g. 2i * 3i = -6. Adding a test for this and changing the code accordingly results in this (surprisingly?) complete implementation:

public RootTerm Multiply(RootTerm other)
{
    int m = ((this.x < 0) && (other.x < 0)) ? -1 : 1;
    RootTerm r = Sqrt(this.x * other.x);
    return new RootTerm(m * this.c * other.c * r.c, r.x);
}

From here it was just about adding more and more “proofs by example” (unit tests). The only problem I encountered was in the formatting of the output in the ToString() method. It turns out I hadn’t needed to handle the case of a leading -1 up to that point, so I corrected the code to produce -sqrt(6) instead of the rather unsightly -1*sqrt(6).

For completeness, I implemented the multiply operator. It was quite literally one line of code:

public static RootTerm operator *(RootTerm a, RootTerm b) => a.Multiply(b);

Now, on to addition. The full implementation would require a new data structure, but I started with a case that could be represented by a plain RootTerm — simple integers:

public RootTerm Add(RootTerm other)
{
    if (this.c == 0)
    {
        return other;
    }

    return new RootTerm(this.c + other.c, this.x);
}

No sweat. A similar case with integral imaginary numbers (e.g. 2*i + 3*i = 5*i) doesn’t even need any code changes. The first counterexample I decided to approach was the combination of the two previous sets — integers plus whole quantities of i, e.g. 2+i. To prepare, I introduced the RootSum struct, which in essence looked like this:

public struct RootSum
{
    private readonly RootTerm a;
    private readonly RootTerm b;

    public RootSum(RootTerm a, RootTerm b)
    {
        this.a = a;
        this.b = b;
    }
}

This was sufficient since the sum of two RootTerm values would, at worst, need to be represented by two distinct and irreducible RootTerms. From this point on, I began to implement the addition logic, augmenting the code with various special cases to handle like terms (e.g. sqrt(3)+3*sqrt(3)=4*sqrt(3)) and to render the output in a reasonable manner.

The final Add logic found its home in the RootSum struct directly (this seemed to make the most sense, responsibility-wise):

public static RootSum Add(RootTerm x, RootTerm y)
{
    if (x.IsZero)
    {
        return new RootSum(y, RootTerm.Zero);
    }

    if (y.IsZero)
    {
        return new RootSum(x, RootTerm.Zero);
    }

    if (x.X == y.X)
    {
        return new RootSum((x.C + y.C) * RootTerm.Sqrt(x.X), RootTerm.Zero);
    }

    if (x.IsReal && y.IsReal)
    {
        if (x.X < y.X)
        {
            return new RootSum(x, y);
        }

        return new RootSum(y, x);
    }

    if (x.IsReal)
    {
        return new RootSum(x, y);
    }

    if (y.IsReal)
    {
        return new RootSum(y, x);
    }

    if (x.X > y.X)
    {
        return new RootSum(x, y);
    }

    return new RootSum(y, x);
}

The only reason for all the different conditions is to make sure that the sum output ends up in “nice” order, specifically integers followed by square roots in ascending order with imaginary numbers last.

One notable detour I took during this exercise was a “de-encapsulation” step to make the main RootTerm constructor public. The corresponding code was originally this part of the Add method, right when I first moved it to RootSum:

if (x.X == y.X)
{
    return new RootSum(new RootTerm(x.C + y.C, x.X), RootTerm.Zero);
}

I cringed a bit, feeling like I was spurning David Parnas himself. But it seemed necessary at the time, RootSum not being privy to RootTerm‘s private members (alas, there are no friends in C#).

Ultimately, Parnas was avenged when I discovered a compromise to keep more of RootTerm private:

    if (x.X == y.X)
    {
        return new RootSum((x.C + y.C) * RootTerm.Sqrt(x.X), RootTerm.Zero);
    }

To make this possible, I simply had to add a Multiply method/operator which permitted products of plain old Int32 and RootTerm values. This does have a minor performance implication (forcing the re-simplification of an already reduced radical) but I was more interested in exploring and solving the encapsulation problem. It just goes to show, you can always uncover something interesting while doing seemingly rote code exercises.

If you want to follow my coding journey step-by-step, you can view the full commit history here: RootSample on GitHub.