Double square numbers

A number that is the sum of two perfect squares is called a double square. Notice that any perfect square number, since it could be expressed as the sum of its square root and zero squared, is a double square:

16 = 4**2 + 0**2

Beside the trivial case showed before, we could think of cases like 50, were more than one couple of integer could generate it:

50 = 1**2 + 7**2 = 5**2 + 5**2

We want to write a function that could check if any positive integer up to a couple of billion (so that we could store it in a signed 32 bit int) is such a number.

I have found this problem on CodeEval, under the name Double Squares however, they credit the Facebook Hacker Cup 2011 as their source. They suggest of not even thinking about a brute force approach, and trying to be smarter than that.

When working on this post, I found nicer to change slightly the requisites, asking the function to return the collection of couples that generates the number as double square. If the passed number is not such, the function would return an empty collection.

Here is a few test cases (GoogleTest for C++) that show what I want from this function:

typedef std::vector< std::pair<int, int> > Generators; // 1

Generators doubleSquares(int value); // 2

TEST(DoubleSquares, Sixteen) // 3
{
    Generators output = doubleSquares(16);

    ASSERT_EQ(1, output.size());
    EXPECT_EQ(0, output[0].first);
    EXPECT_EQ(4, output[0].second);
}

TEST(DoubleSquares, Fifty) // 4
{
    Generators output = doubleSquares(50);

    ASSERT_EQ(2, output.size());
    EXPECT_EQ(1, output[0].first);
    EXPECT_EQ(7, output[0].second);
    EXPECT_EQ(5, output[1].first);
    EXPECT_EQ(5, output[1].second);
}

TEST(DoubleSquares, BigOne) // 5
{
    Generators output = doubleSquares(5882353);

    ASSERT_EQ(1, output.size());
    EXPECT_EQ(588, output[0].first);
    EXPECT_EQ(2353, output[0].second);
}

1. As container for the generators I am going to use a vector of pairs.
2. My function prototype.
3. Passing 16 in, I expect as output a single pair, (0, 4).
4. Both (1, 7) and (5, 5) generates 50.
5. A (relative) big number, 5882353, generated by (588, 2353).

Here is how I have implemented the function:

Generators doubleSquares(int value)
{
    Generators result;
    for (int i = 0; i <= std::sqrt(value / 2); i++) // 1
    {
        double j = std::sqrt(value - std::pow(i, 2)); // 2
        if (std::floor(j) == j) // 3
            result.push_back( { i, static_cast<int>(j) } ); // 4
    }
    return result;
}

1. I am checking if value has a couple of generators. Each of them should be a non-negative integer, the biggest one can't be bigger than the square root of the half of value. To clarify this point think to a real case, 64 for instance. It is easy to see that 9 can't be among its generators.
2. Let's assume i is a generator for value, the other generator should concur with all the missing slice to reach the result. So I extract the square root from the difference between value and the square of i.
3. I am still not sure I can accept j as second generator for value, I should check it is an integer. This is probably the fastest way to do it. The standard math function floor() returns the nearest integer not greater than its input. We state that its returned value is exactly equals to the j original value.
4. I am using this very handy C++11 way to build a STL pair on the fly. If your compiler does not support it, I am sorry you have to fallback to the less immediate make_pair() function template. Notice also that I should say to the compiler that I am aware I am casting a double to an int. I am sure of what I am doing, thanks to the check on the previous line.

Go to the full post