On Sat, 12 Jan 2008 23:36:43 +0100, Daniel Fischer <[EMAIL PROTECTED]> wrote: > > Am Samstag, 12. Januar 2008 22:48 schrieb Luke Palmer: > > On Jan 12, 2008 9:19 PM, Rafael Almeida <[EMAIL PROTECTED]> 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
