The Problem
The difference of squares problem is simply stated as determining the difference between the sum of squares and square of sums for a sequence of numbers from 1 to N.
An example:
The sum of squares for the first five natural numbers is:
(1^2 + 2^2 + 3^2 + 4^2 + 5^2) = 55
The square of sums for the first five natural numbers is:
(1+2+3+4+5)^2 = 225
With the difference between the two sequences being:
225 - 55 = 170
Solution #1
So the problem seems pretty easy, and in Haskell, it becomes almost trivial.
Let's take the first step as the sum of squares.
sumOfSquares :: Integral a => a -> a
sumOfSquares n = sum $ fmap (^2) [1..n]
We first generate a list of numbers from 1 to the input N. Then square each number in the sequence and sum the entire list. Simple
On to the square of sums.
squareOfSum :: Integral a => a -> a
squareOfSum n = (^2) $ sum [1..n]
Similarly here, we generate a list, but now sum it up, and the square the result.
The difference between the two hopefully is obvious:
difference :: Integral a => a -> a
difference n = squareOfSum n - sumOfSquares n
This solution is extremely trivial to implement, not only in Haskell but other languages as well. But, it is not exactly efficient. First, we are doing n+1 squares. Second, we are generating the same list multiple times. Even so, this performs pretty quickly on my machine up through ~ 1,000,000. After that, the operations start to slow down.
But we can do better surely, and do so in the next post.
