On 12/01/2008, Hugh Perkins wrote:

On Jan 12, 2008 10:19 PM, Rafael Almeida wrote:

...

After some profiling I found out that about 94% of the execution time is spent in the ``isPerfectSquare'' function.

I guess that Haskell's referential transparence means the answers to the isPerfectSquare will be cached, ie automatically memoized? (not sure if is correct term?)

This isn't true unless calling isPerfectSquare reads the result out of a lazily generated array of responses or some other data structure at the top-level. There's no memoisation of functions by default because it would typically require ridiculous amounts of memory, however, you can usually rely on values bound to variables to only be computed once, barring those which are typeclass polymorphic. - Cale

You can do better than this, too, actually. It looks like you're using isPerfectSquare inside a filter, which is given a monotone sequence. That means we can do: -- finds the intersection of two monotone sequences intersectMonotone :: (Ord a) => [a] -> [a] -> [a] intersectMonotone (x:xs) (y:ys) = case x `compare` y of EQ -> x : intersectMonotone x y LT -> intersectMonotone xs (y:ys) GT -> intersectMonotone (x:xs) ys intersectMonotone _ _ = [] Then you can change (filter isPerfectSquare) to (intersectMonotone perfectSquares) and you should get a big speed boost. Luke On Jan 12, 2008 9:48 PM, Luke Palmer wrote:

On Jan 12, 2008 9:19 PM, Rafael Almeida wrote:

...

After some profiling I found out that about 94% of the execution time is spent in the ``isPerfectSquare'' function.

That function is quite inefficient for large numbers. You might try something like this:

isPerfectSquare n = searchSquare 0 n where searchSquare lo hi | lo == hi = False | otherwise = let mid = (lo + hi) `div` 2 in case mid^2 `compare` n of EQ -> True LT -> searchSquare mid hi GT -> searchSquare lo mid

Luke

On Sat, 12 Jan 2008 23:36:43 +0100, Daniel Fischer wrote:

Am Samstag, 12. Januar 2008 22:48 schrieb Luke Palmer:

...

On Jan 12, 2008 9:19 PM, Rafael Almeida wrote:

...

After some profiling I found out that about 94% of the execution time is spent in the ``isPerfectSquare'' function.

That function is quite inefficient for large numbers. You might try something like this:

isPerfectSquare n > where searchSquare lo hi

| lo = hi > | otherwise > let mid > case mid^2 `compare` n of EQ -> True LT -> searchSquare mid hi GT -> searchSquare lo mid

Luke

I don't want to be a spoil-sport, but that won't help much either. And although the logic of the programme is correct, the numbers involved are so large that I'd expect the running time to be rather years than days (it took a minute to solve for the smallest cathetus of 6 triangles, 128). Suppose the answer were 10^9 (it's much larger, actually). Then the limit for the other cathetus would be roughly 5*10^17 and for all these values it has to be checked whether n^2 + y^2 is a perfect square. If one check took a nanosecond, that would be roughly 5*10^8 seconds or nearly 16 years. Rafael, you have some good starts, but to get the answer in a reasonable time, you must employ some more algebra. Find a way to determine a cathetus of how many triangles a number is without actually constructing them is a good step.

Cheers, Daniel

Now you really conviced me that the algorithm isn't right. Although I already thought I needed to come up with a new algorithm when the GMP's perfect square function didn't help. I thank for all the feedback on how to make isPerfectSquare faster, though. It has been educational. I'm trying to come up with something other than constructing the triangles, but maybe I'm just not that strong at algebra. Thanks for de feedback, though.

On Sat, 12 Jan 2008, Achim Schneider wrote:

"Rafael Almeida" wrote:

...

perfectSquares :: [Integer] perfectSquares = zipWith (*) [1..] [1..]

...

isPerfectSquare :: Integer -> Bool isPerfectSquare x = (head $ dropWhile (

what about

module Main where

isPerfectSquare :: Integer -> Bool isPerfectSquare n = sqrrt == fromIntegral (truncate sqrrt) where sqrrt = sqrt $ fromIntegral n

? It's a hell alot faster, but I have no idea if some numerical property of square roots could make it give different results than your version, in rare cases.

The rare cases occur for big numbers. http://www.haskell.org/haskellwiki/Generic_number_type#isSquare

Achim Schneider wrote:

"Rafael Almeida" wrote:

...

perfectSquares :: [Integer] perfectSquares = zipWith (*) [1..] [1..]

...

isPerfectSquare :: Integer -> Bool isPerfectSquare x = (head $ dropWhile (

what about

module Main where

isPerfectSquare :: Integer -> Bool isPerfectSquare n = sqrrt == fromIntegral (truncate sqrrt) where sqrrt = sqrt $ fromIntegral n

? It's a hell alot faster, but I have no idea if some numerical property of square roots could make it give different results than your version, in rare cases.

Well, even if so, I bet calculating the square root by successive approximation using integers would still be faster, it's O(ld(n)) instead of O(n). -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.

On Jan 12, 2008 7:12 PM, Achim Schneider wrote:

what about

module Main where

isPerfectSquare :: Integer -> Bool isPerfectSquare n = sqrrt == fromIntegral (truncate sqrrt) where sqrrt = sqrt $ fromIntegral n

? It's a hell alot faster, but I have no idea if some numerical property of square roots could make it give different results than your version, in rare cases.

I did something similar: isSquare :: Integer -> Bool isSquare x = x == (sqx * sqx) where sqx = round $ sqrt $ fromInteger x perfectSquares :: [Integer] perfectSquares = zipWith (*) [1..] [1..] findSorted :: [Integer] -> Integer -> Bool findSorted xs x = h == x where h : _ = dropWhile ( test 100000 (True,False) -- []s, Andrei Formiga

Achim Schneider wrote:

the last one take a bit less than 20 secs on my pc. And 2^2^16 is a number that takes at least an hour to pronounce.

Which means that I'm an absolute genius when it comes to fucking up perfectly good algorithms. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.

On Sun, 13 Jan 2008 11:48:09 +0100, "Nicu Ionita" wrote:

Hi Rafael,

I have just two ideas, that could improve your strategy to reduce the computation time:

1. perhaps there is also a minimum (not only a maximul) for the values you should try

Yeah, that's a good one, the most I can narrow down the results the better. But if I can figure out the number of triangles without actually constructing them would be the real winner algorithm.

2. is the function howManyTriangles monotone? If yes, then you could try to solve:

howManyTriangles n = 47547

by finding an upper n, nmax, where howManyTriangles nmax > 47547, and than using Euler to reduce the interval (from 12 to nmax, then probably from (12 + nmax)/2 to nmax, a.s.o)

Then you will have ~ ln nmax computations of the function, which could be better than computing it from 1 to ...

I wish it was monotone, but it doesn't seem to be anything, I even plotted the relation cathetus size x number of triangles, but it didn't really show any pattern. It seems there are more likely results, but there are a few of them that looks just random. If you want to see the plotted graph: http://homepages.dcc.ufmg.br/~rafaelc/problem176.png