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

[Arjun Comar]

The key to solving any Euler problem is to realize that you want an
analytic solution whenever possible. In this case, if you try to construct
and sum lists, you're going to hit the time boundaries every time. On the
other hand, you can do some basic algebra and come up with a fully analytic
solution that will run in constant (well, nearly, it depends on the number
of bits in the upper bound) time.

So for the problem at hand, you've already realized that you can compute 3
separate sums and combine them into your answer. When you want to sum
numbers from 1 to n, there's an analytic formula for the summation: n*(n+1)
/ 2. So rewrite your sums as summations from 1 to some number, insert the
analytic formula and algebraically reduce the resulting equation to a
couple of simple terms that are easy to compute. If you've never done this,
let me know, and I'll walk you through the steps more slowly.

Thanks,
Arjun

On Tue, Jan 27, 2015 at 8:09 PM, Animesh Saxena <animeshsaxena at icloud.com>
wrote:

> 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/1c8d9179/attachment-0001.html>