Programming Praxis – The Sum Of Two Squares

In today’s Programming Praxis exercise we have to find all the ways a given number can be written as the sum of the squares of two other numbers. Let’s get started.

All we really have to do is to convert the four cases of Dijkstra’s algorithm (listed on the second page of the exercise) from English to Haskell, which is trivial. To avoid repeating ourselves, we pattern match on the result of the comparison between x*x + y*y and n instead of recalculating it three times.

squareSum :: Integer -> [(Integer, Integer)]
squareSum n = b (ceiling . sqrt $ fromIntegral n) 0 where
    b x y = if x < y then [] else case compare (x*x + y*y) n of
                LT -> b x (y + 1)
                EQ -> (x, y) : b (x - 1) (y + 1)
                GT -> b (x - 1) y

A quick test shows us that everything’s working correctly.

main :: IO ()
main = do print $ squareSum 50
          print $ squareSum 48612265
          print $ squareSum 999
About these ads

Tags: , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: