[Haskell-beginners] Project Euler #01 on HackerRank, Performance issue‏

[Jean Lopes]

Your solution runs really quick! I'll study it. Thank you

2015-01-27 22:25 GMT-02:00 Lyndon Maydwell <maydwell at gmail.com>:

> Ah sorry, I didn't notice that you were doing that. The effectiveness of
> the trick really only comes into play though if you use an analytic
> solution for finding the sum of the multiples of 3, etc.
>
> I haven't tested this code in a while, but here's what I wrote some time
> ago:
>
>
> sum2 :: Integer -> Integer -> Integer -> Integer
> sum2 a b ceiling = aX + bX - abX
> where
> aX  = sum1 a ceiling
> bX  = sum1 b ceiling
> abX = sum1 (a * b) ceiling
>
> sum1 :: Integer -> Integer -> Integer
> sum1 x ceiling = sum1' (even times) times x
> where
> times = ceiling `div` x
>
> sum1' :: Bool -> Integer -> Integer -> Integer
> sum1' True times x = area
> where
> area = (times + 1) * (times * x) `div` 2
>
> sum1' False times x = max + area'
> where
> max   = times * x
> area' = sum1' True (times - 1) x
>
>
> Please excuse the poor Haskell style as it is quite possibly the first
> Haskell program I ever wrote.
>
>
>
> On Wed, Jan 28, 2015 at 11:15 AM, Jean Lopes <hawu.bnu at gmail.com> wrote:
>
>> Thats actually what I did...
>>
>> 2015-01-27 22:11 GMT-02:00 Lyndon Maydwell <maydwell at gmail.com>:
>>
>> I remember that when I had a look at Euler 1 I found that there's a fun
>>> solution that should run in "constant" time.
>>>
>>> You can find the sum of the multiples of 3, add the multiples of 5, and
>>> then subtract the multiples of 3*5.
>>>
>>> Is that the kind of thing you're looking for?
>>>
>>>  - Lyndon
>>>
>>>
>>> On Wed, Jan 28, 2015 at 10:57 AM, Jean Lopes <hawu.bnu at gmail.com> wrote:
>>>
>>>> I'm not really good at math, maybe I am missing something obvious ?
>>>> Maybe some pointers as of where to start studying math in order to
>>>> avoid this brute force attempts, at least to help in this particular problem
>>>>
>>>> 2015-01-27 21:38 GMT-02:00 Brandon Allbery <allbery.b at gmail.com>:
>>>>
>>>>> On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes <hawu.bnu at gmail.com>
>>>>> wrote:
>>>>>
>>>>>> The problem to be solved:
>>>>>> https://www.hackerrank.com/contests/projecteuler/challenges/euler001
>>>>>
>>>>>
>>>>> It's worth remembering that the Euler problems are all about math
>>>>> understanding; often they are designed such that brute force solutions will
>>>>> time out or otherwise fail.
>>>>>
>>>>> --
>>>>> brandon s allbery kf8nh                               sine nomine
>>>>> associates
>>>>> allbery.b at gmail.com
>>>>> ballbery at sinenomine.net
>>>>> unix, openafs, kerberos, infrastructure, xmonad
>>>>> http://sinenomine.net
>>>>>
>>>>> _______________________________________________
>>>>> Beginners mailing list
>>>>> Beginners at haskell.org
>>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> Beginners at haskell.org
>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>
>>>>
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> Beginners at haskell.org
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20150127/d25c4eb6/attachment-0001.html>