Is there a way to optimise this program in Haskell?

Question

Hi I am doing project euler question 224. And whipped up this list comprehension in Haskell:

prob39 = length [ d | d <- [1..75000000], c <- [1..37500000], b <-[1..c], a <- [1..b], a+b+c == d, a^2 + b^2 == (c^2 -1)]

I compiled it with GHC and it has been running with above average kernel priority for over an hour without returning a result. What can I do to optimise this solution? It seems I am getting better at finding brute force solutions in a naive manner. Is there anything I can do about this?

EDIT: I am also unclear about the definition of 'integral length', does this just mean the side length has a magnitude which falls in the positive set of integers, i.e: 1,2,3,4,5... ?

Answer 1

My Haskell isn't amazing, but I think this is going to be n^5 as written.

It looks like you're saying for each n from 1 to 75 million, check every "barely obtuse" triangle with a perimiter less than or equal to 75 million to see if it has perimiter n.

Also I'm not certain if list comprehensions are smart enough to stop looking once the current value of c^2 -1 is greater than a^2 + b^2.

A simple refactor should be

prob39 = length [ (a, b, c) | c <- [1..37500000], b <-[1..c], a <- [1..b], a^2 + b^2 == (c^2 -1), (a + b + c) <= 75000000]

You can make it better, but that should literally be 75 million times faster.

Less certain about this refactoring, but it should also speed things up considerably:

prob39 = length [ (a, b, c) | a <- [1..25000000], b <-[a..(75000000 - 2*a)], c <- [b..(75000000 - a - b)], a^2 + b^2 == (c^2 -1)]

Syntax may not be 100% there. The idea is that a can only be 1 to 25 million (since a <= b <= c and a + b + c <= 75 million). b can only be between a and halfway from a to 75 million (since b <= c) and c can only be from b to 75 million - (a + b), otherwise the perimeter would be over 75 million.

Edit: updated code snippets, there were a couple of bugs in there.

Another quick suggestion, you can replace c <- [b..(75000000 - a - b)] with something along the lines of c <- [b..min((75000000 - a - b), sqrt(a*a + b*b) + 1)]. There's no need to bother checking any values of c greater than the ceiling of the square root of (a^2 + b^2). Can't remember if those are the correct min/sqrt function names in haskell though.

Getting OCD on this one, I have a couple more suggestions.

1) you can set the upper bound on b to be the min of the current upper bound and a^2 * 2 + 1. This is based on the principle that (x+1)^2 - x^2 = 2x + 1. b cannot be so much larger than a that we can guarantee that (a^2) + (b^2) < (b+1)^2.

2) set the lower bound of c to be max of b + 1 and floor(sqrt(a^2 + b^2) - 1). Just like the upper limit on C, no need to test values which couldn't possibly be correct.