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

[Jean Lopes]

Yes, that would work, but this approach will exceeding the time limit of 5
seconds. Keep in mind that this program should process 100.000 numbers
which will range from 1 to 1.000.000.000 in under five seconds

My current implementation it won't succeed regarding the time factor, but I
did get some insights, I know where to look now (I guess)!

Just to illustrate what I am saying: for instance this function
> sum [3,6..9999999]
Takes ~1 second to return, and these are just the multiples of 3, to get
the real answer I would have to first sum the multiples of 5 and 15...

2015-01-27 23:09 GMT-02:00 Animesh Saxena <animeshsaxena at icloud.com>:

> why not just use infinite series. mathematically...
>
> series 1 = Mutiples of 3
> series 2 = Multiples of 5
> Apply filter and sum to get the answer
>
> -Animesh
>
> On Jan 27, 2015, at 04:43 PM, Jean Lopes <hawu.bnu at gmail.com> wrote:
>
> 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
>>
>>
> _______________________________________________
> 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/9f9cda85/attachment.html>