Is there a way to optimize this program in Haskell?

Question

I am doing a draft question for Euler 224 . And weighed 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 using GHC and it worked with a higher kernel priority for over an hour without returning a result. What can I do to optimize this solution? I seem to be better at brute force decisions naively. Can I do anything about this?

EDIT: I also do not quite understand the definition of "integral length", does this simply mean that the length of the side has a value that falls into a positive set of integers, i.e. 1,2,3,4,5 ...?

Answer 1

My Haskell is not surprising, but I think it will be n ^ 5 as it is written.

It looks like you are talking for every n from 1 to 75 million, check each “barely dumb” triangle with a period less than or equal to 75 million to see if it has a perimeter n.

Also, I'm not sure that list comprehension is smart enough to stop looking as soon as the current value of c ^ 2 -1 is greater than a ^ 2 + b ^ 2.

Simple refactoring 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 do it better, but it should literally be 75 million times faster.

Less specific about this refactoring, but it should also significantly speed up the process:

 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)] 

The syntax may not be 100%. The idea is that a can only be from 1 to 25 million (since a <= b <= c and a + b + c <= 75 million). b can be only 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 will be more than 75 million.

Edit: updated code snippets, there were several errors.

Another quick suggestion, you can replace c <- [b .. (75000000 - a - b)] with something along the lines c <- [b..min ((75000000 - a - b), sqrt (aa + bb) + 1)]. There is no need to check any values ​​of c greater than the square root ceiling of (a ^ 2 + b ^ 2). I can’t remember if they are the correct min / sqrt function names in haskell.

Having got an OCD on this, I have a few more suggestions.

1) you can set the upper bound to b as 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 greater than a, that we can guarantee that (a ^ 2) + (b ^ 2) (b + 1) ^ 2.

2) set the lower bound c as max b + 1 and floor (sqrt (a ^ 2 + b ^ 2) - 1). Just like the upper limit on C, there is no need to check values ​​that cannot be correct.

Answer 2

Along with the suggestions given by @patros. I would like to share my observations on this issue.

If we print the values ​​of a, b, and c for a certain perimeter, say, 100,000, then we can observe that a and b always take even values, and c always take odd values. Thus, if we optimize our code with these restrictions, then almost half of the verification may be skipped.