CODEWITHSUNDEEP
haskellinteger
Harry
Harry

Reputation: 33

sum of square integers haskell

I have this code to work out the sum of squares of integers in the range of m:n

sumsquares :: Integral a=> Int -> Int -> Int -> Int
sumsquares m n middle
 | m > n = error "First number cannot be bigger than second number"
 |m==n = m*m
 |otherwise = m*m + sumsquares (m+1)n

How would i redefine the function sumsquares for this purpose?

If there is more than one number in the range m:n, compute the middle of the range and add the sum of the squares of (m:middle) to sum of the squares (middle+1:n), otherwise there is only one number in the range m:n, so m = = n, and the solution is just the square of m. (Note that with this approach the recursion combines two half- solutions: each sub-problem is approximately half in size of the overall problem).

Upvotes: 0

Views: 1170

Answers (1)

Stefan Holdermans
Stefan Holdermans

Reputation: 8050

In your original function, the class constraint Integral a in the type signature is obsolete (a is not mentioned anywhere else in the signature, is it?). Furthermore, the third parameter of the function (middle) remains unused. Hence, you could have written it as

sumsquares :: Int -> Int -> Int 
sumsquares m n  
  | m > n     = error "First number cannot be bigger than second number"
  | m == n    = m * m
  | otherwise = m * m + sumsquares (m + 1) n

Rewriting it to move from a decrease-and-conquer scheme to a strict divide-and-conquer scheme then just involves adapting the recursive case accordingly:

sumsquares :: Int -> Int -> Int 
sumsquares m n  
  | m > n     = error "First number cannot be bigger than second number"
  | m == n    = m * m
  | otherwise = let middle = (m + n) `div` 2
                in  sumsquares m middle + sumsquares (middle + 1) n

The question remains, of course, why you would want to make this change. One reason could be that you are preparing your algorithm to be adapted for parallelisation: then, indeed, divide-and-conquer is often a better fit than decrease-and-conquer.

Upvotes: 3

Related Questions