For Project Euler #1 isn't it more efficient to generate just the numbers you need? <Spoiler> - Haskell-Cafe - Haskell.org

newer
no time profiling on my...

For Project Euler #1 isn't it more efficient to generate just the numbers you need? <Spoiler>

older
Server hosting

caseyh＠istar.ca

6 May 2011 6 May '11

7:31 p.m.

-- Instead of this -- sumMultiples3or5 s = sum [x | x <- [3..s-1], x `mod` 3 == 0 || x `mod` 5 == 0] -- Isn't this faster sumMultiples3or5 s = sum ([x | x <- [3,6..s-1]] `merge` [x | x <- [5,10..s-1]]) merge xs [] = xs merge [] ys = ys merge txs@(x:xs) tys@(y:ys) | x < y = x : xs `merge` tys | x > y = y : txs `merge` ys | otherwise = x : xs `merge` ys

Reply

Sign in to reply online Use email software

Show replies by date

Lyndon Maydwell

7 May 7 May

1:10 a.m.

If you're looking for efficiency, I believe you can actually do #1 in constant time: On Sat, May 7, 2011 at 7:31 AM, wrote:

-- Instead of this -- sumMultiples3or5 s = sum [x | x <- [3..s-1], x `mod` 3 == 0 || x `mod` 5 == 0]

-- Isn't this faster

sumMultiples3or5 s = sum ([x | x <- [3,6..s-1]] `merge` [x | x <- [5,10..s-1]])

merge xs [] = xs merge [] ys = ys merge txs@(x:xs) tys@(y:ys) | x < y = x : xs `merge` tys | x > y = y : txs `merge` ys | otherwise = x : xs `merge` ys

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

KC

2:52 p.m.

Do you mean O(1) complexity? Don't you have to touch at least the multiples of 3 & 5 making it O(k) where is the number of multiples of 3 and the number of multiples of 5? On Fri, May 6, 2011 at 10:10 PM, Lyndon Maydwell wrote:

If you're looking for efficiency, I believe you can actually do #1 in constant time:

On Sat, May 7, 2011 at 7:31 AM, wrote:

...
-- Instead of this -- sumMultiples3or5 s = sum [x | x <- [3..s-1], x `mod` 3 == 0 || x `mod` 5 == 0]

-- Isn't this faster

sumMultiples3or5 s = sum ([x | x <- [3,6..s-1]] `merge` [x | x <- [5,10..s-1]])

merge xs [] = xs merge [] ys = ys merge txs@(x:xs) tys@(y:ys) | x < y = x : xs `merge` tys | x > y = y : txs `merge` ys | otherwise = x : xs `merge` ys

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- -- Regards, KC

Reply

Sign in to reply online Use email software

Eugene Kirpichov

2:56 p.m.

One doesn't have to touch them to compute their sum. 2011/5/7 KC :

Do you mean O(1) complexity?

Don't you have to touch at least the multiples of 3 & 5 making it O(k) where is the number of multiples of 3 and the number of multiples of 5?

On Fri, May 6, 2011 at 10:10 PM, Lyndon Maydwell wrote:

...
If you're looking for efficiency, I believe you can actually do #1 in constant time:

On Sat, May 7, 2011 at 7:31 AM, wrote:

...
-- Instead of this -- sumMultiples3or5 s = sum [x | x <- [3..s-1], x `mod` 3 == 0 || x `mod` 5 == 0]

-- Isn't this faster

sumMultiples3or5 s = sum ([x | x <- [3,6..s-1]] `merge` [x | x <- [5,10..s-1]])

merge xs [] = xs merge [] ys = ys merge txs@(x:xs) tys@(y:ys) | x < y = x : xs `merge` tys | x > y = y : txs `merge` ys | otherwise = x : xs `merge` ys

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- -- Regards, KC

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Principal Engineer, Mirantis Inc. http://www.mirantis.com/ Editor, http://fprog.ru/

Reply

Sign in to reply online Use email software

KC

4:42 p.m.

Got it. You mean use the formula for summing an arithmetic progression twice and take account of duplicates. Sheer genius! On Sat, May 7, 2011 at 11:56 AM, Eugene Kirpichov wrote:

One doesn't have to touch them to compute their sum.

2011/5/7 KC :

...
Do you mean O(1) complexity?

Don't you have to touch at least the multiples of 3 & 5 making it O(k) where is the number of multiples of 3 and the number of multiples of 5?

On Fri, May 6, 2011 at 10:10 PM, Lyndon Maydwell wrote:

...
If you're looking for efficiency, I believe you can actually do #1 in constant time:

On Sat, May 7, 2011 at 7:31 AM, wrote:

...
-- Instead of this -- sumMultiples3or5 s = sum [x | x <- [3..s-1], x `mod` 3 == 0 || x `mod` 5 == 0]

-- Isn't this faster

sumMultiples3or5 s = sum ([x | x <- [3,6..s-1]] `merge` [x | x <- [5,10..s-1]])

merge xs [] = xs merge [] ys = ys merge txs@(x:xs) tys@(y:ys) | x < y = x : xs `merge` tys | x > y = y : txs `merge` ys | otherwise = x : xs `merge` ys

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- -- Regards, KC

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Principal Engineer, Mirantis Inc. http://www.mirantis.com/ Editor, http://fprog.ru/

-- -- Regards, KC

Reply

Sign in to reply online Use email software

5129

Age (days ago)

5130

Last active (days ago)

Download

4 comments

4 participants

tags

participants (4)

caseyh＠istar.ca
Eugene Kirpichov
KC
Lyndon Maydwell