6 ms·

Ah, memories. Back in 2010 I whinged to colleagues who were using their fancy functional languages to solve problem 1 inefficiently in 2 lines of code... " Pro

Ah, memories. Back in 2010 I whinged to colleagues who were using their fancy functional languages to solve problem 1 inefficiently in 2 lines of code... " Project Euler problem 1 :- It helps to know the sum of (1 .. x) is 0.5 * n * (n+1). Multiples of 3 less than 1000 are (3 .. 999) == (1 .. 333) * 3 = 0.5 * 333 * 334 * 3 = 166833 Multiples of 5 less than 1000 are (5 .. 995) == (1 .. 199) * 5 = 0.5 * 199 * 200 * 5 = 99500 We must subtract common multiples (those of 15), so (15 .. 990) = (1 .. 66) * 15 = 0.5 * 66 * 67 * 15 = -33165 166833 + 99500 - 33165 = 233168 O(1) solution FTW :P Nice looking code is good, but a smart algorithm makes a big difference. " OK, I was a smug arsehole, but there's a point to be made y'know?

bunderbunder 9y ago
The best point to be made from this isn't that it's more computationally efficient. It's that, compared to something like sum [x | x <- [1..999], (mod x 3 == 0) || (mod x 5 == 0)] which is really just bluntly translating the question into a programming language and letting it take care of the rest, your approach involves some actual insight into the underlying math.
- aportnoy 9y ago
  What language is this?
  - deleted 9y ago
    [deleted]
  - farresito 9y ago
    Haskell
  - brians 9y ago
    It’s a Haskell list comprehension. You read it as: The sum of x for x from one to 999 where x mod three is zero or x mod five is zero. well, the bit in square brackets is a comprehension. `sum `is just ordinary function application.
  - deleted 9y ago
    [deleted]
- racer-v 9y ago
  Right. We don't actually know whether this Haskell code is less efficient - that depends entirely on the implementation.
  - bunderbunder 9y ago
    Compared to grandparent's method of calculation (9 multiplications, 3 additions, no comparisons, no iteration), the Haskell code is almost certainly less efficient. I can't imagine the Haskell maintainers would spend time on an optimization that is so impractically purpose-specific.
    - maksimum 9y ago
      I don't think it's unreasonable to expect it. E.g. clang -O1 (https://godbolt.org/g/7qzSF9 https://godbolt.org/g/7qzSF9 ) is able to use the closed form for a sum on a simple C++ loop. It's not unreasonable that a language with deeper introspection could identify more closed forms. I agree that I don't think the Haskell maintainers would put this specific example in, but I wonder whether they could build it up from simpler primitives.
      - AstralStorm 9y ago
        Haskell optimizer does not feature an arithmetic Oracle nor polynomial optimizer. It cannot even optimize Peano arithmetic much less a series. This might be fixed some time or never. There is little push for ultimate performance and actually identifying arithmetic forms in recursive loops in the front-end is hard. (Heck it sometimes fails to tail optimize.)
        racer-v 9y ago
        I'd be interested to see how this weighs out in 5-10 years. Since there's no I/O here, I don't see why a clever compiler writer couldn't optimize this whole expression away at compile time, generating an executable just prints a constant.
- kccqzy 9y ago
  You can do the same in Python, which steals Haskell’s list comprehension. By the way doesn’t the original problem say exclude multiples of 15? IMO Python’s generators and coroutines are one of its most useful yet least appreciated features. Being able to suspend a function, resume it, get values from it, send values or exceptions to it is a highly powerful feature. You can use them to implement user-space cooperative threads, write a scheduler for that, implement message-passing concurrency, and do highly efficient multiplexed I/O in the style of asyncio.
  - oldandtired 9y ago
    and Python got this from....? (which language)
    - kccqzy 9y ago
      Well Python got it from Haskell. I thought I made it clear enough. See https://docs.python.org/3/howto/functional.html https://docs.python.org/3/howto/functional.html
      - oldandtired 9y ago
        Well years ago, I saw a discussion that put this in the context of python's generators being inspired by what was in Icon.
        bunderbunder 9y ago
        I'm just now looking at Icon code for the first time, but, to me, Python's list comprehension syntax looks more similar to Haskell's than Icon's.
jackweirdy 9y ago
> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s a good place to start learning some of this stuff? By stuff I mean things related to algebra and whatever the black magic I quoted is
- jklehm 9y ago
  Discrete mathematics is the branch of math you're after. This looks like it has some ok examples: https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematical_induction.htm https://www.tutorialspoint.com/discrete_mathematics/discrete...
- pkaye 9y ago
  This would be a finite series. I think it is usually covered in calculus courses but some of the basics are discussed in earlier algebra courses. Here is a link to a brief summary on finite series. http://calculus.nipissingu.ca/tutorials/finiteseries.html http://calculus.nipissingu.ca/tutorials/finiteseries.html You can also start your way up from the basics in Khan's Academy.
- metahost 9y ago
  Any arithmetic book on Sequence and Series will provide you with the basic toolset to derive the above.
- feikname 9y ago
  I do not have an formal math education, but I'm fairly sure what you quote is part of the Arithmetic Progression concept (the sum formula more specifically), so taking a look at the arithmetic branch of math might be a good idea. Wikipedia[0], MathWords[1] and Brilliant[2] might be some good resources for you. [0] https://en.wikipedia.org/wiki/Lists_of_mathematics_topics https://en.wikipedia.org/wiki/Lists_of_mathematics_topics [1] http://www.mathwords.com/ http://www.mathwords.com/ [2] https://brilliant.org/ https://brilliant.org/
- toAnswerIt 9y ago
  to see it consider this: S = 1 + 2 + 3 + ... + n-1 + n + S = n + n-1 + n-2 + ...+ 2 + 1 = 2S = n+1 + n+1 + n+1 + ... + n+1 + n+1 every column sums to n+1
pkaye 9y ago
If you read the first paragraph of the website, "Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."
carapace 9y ago
Oh cool! I've been working with a continuation-pasing style variant of Joy (https://en.wikipedia.org/wiki/Joy_programming_language https://en.wikipedia.org/wiki/Joy_programming_language https://github.com/calroc/joypy https://github.com/calroc/joypy) and tried it on the Project Euler problem 1: https://github.com/calroc/joypy/blob/master/docs/3.%20Developing%20a%20Program.md https://github.com/calroc/joypy/blob/master/docs/3.%20Develo... I came up with a solution that generalizes to blocks of terms, but yours is much much nicer! Cheers! """ Between 0 and 990 inclusive there are sixty-six "blocks" of seven terms each, starting with: [3 5 6 9 10 12 15] And ending with: [978 980 981 984 985 987 990] If we reverse one of these two blocks and sum pairs... """ The Advent of Code 2017 includes a puzzle involving a "spiral" memory grid and I had a similar thing where I was able to figure out a simple mathematical way to solve the puzzle: https://github.com/calroc/joypy/blob/master/docs/Advent%20of%20Code%202017%20December%203rd.md https://github.com/calroc/joypy/blob/master/docs/Advent%20of... I'm not explaining it well 'cause I'm all excited to show it.

bunderbunder 9y ago

The best point to be made from this isn't that it's more computationally efficient. It's that, compared to something like sum [x | x <- [1..999], (mod x 3 == 0) || (mod x 5 == 0)] which is really just bluntly translating the question into a programming language and letting it take care of the rest, your approach involves some actual insight into the underlying math.

aportnoy 9y ago
What language is this?
- deleted 9y ago
  [deleted]
- farresito 9y ago
  Haskell
- brians 9y ago
  It’s a Haskell list comprehension. You read it as: The sum of x for x from one to 999 where x mod three is zero or x mod five is zero. well, the bit in square brackets is a comprehension. `sum `is just ordinary function application.
- deleted 9y ago
  [deleted]
racer-v 9y ago
Right. We don't actually know whether this Haskell code is less efficient - that depends entirely on the implementation.
- bunderbunder 9y ago
  Compared to grandparent's method of calculation (9 multiplications, 3 additions, no comparisons, no iteration), the Haskell code is almost certainly less efficient. I can't imagine the Haskell maintainers would spend time on an optimization that is so impractically purpose-specific.
  - maksimum 9y ago
    I don't think it's unreasonable to expect it. E.g. clang -O1 (https://godbolt.org/g/7qzSF9 https://godbolt.org/g/7qzSF9 ) is able to use the closed form for a sum on a simple C++ loop. It's not unreasonable that a language with deeper introspection could identify more closed forms. I agree that I don't think the Haskell maintainers would put this specific example in, but I wonder whether they could build it up from simpler primitives.
    - AstralStorm 9y ago
      Haskell optimizer does not feature an arithmetic Oracle nor polynomial optimizer. It cannot even optimize Peano arithmetic much less a series. This might be fixed some time or never. There is little push for ultimate performance and actually identifying arithmetic forms in recursive loops in the front-end is hard. (Heck it sometimes fails to tail optimize.)
      - racer-v 9y ago
        I'd be interested to see how this weighs out in 5-10 years. Since there's no I/O here, I don't see why a clever compiler writer couldn't optimize this whole expression away at compile time, generating an executable just prints a constant.
kccqzy 9y ago
You can do the same in Python, which steals Haskell’s list comprehension. By the way doesn’t the original problem say exclude multiples of 15? IMO Python’s generators and coroutines are one of its most useful yet least appreciated features. Being able to suspend a function, resume it, get values from it, send values or exceptions to it is a highly powerful feature. You can use them to implement user-space cooperative threads, write a scheduler for that, implement message-passing concurrency, and do highly efficient multiplexed I/O in the style of asyncio.
- oldandtired 9y ago
  and Python got this from....? (which language)
  - kccqzy 9y ago
    Well Python got it from Haskell. I thought I made it clear enough. See https://docs.python.org/3/howto/functional.html https://docs.python.org/3/howto/functional.html
    - oldandtired 9y ago
      Well years ago, I saw a discussion that put this in the context of python's generators being inspired by what was in Icon.
      - bunderbunder 9y ago
        I'm just now looking at Icon code for the first time, but, to me, Python's list comprehension syntax looks more similar to Haskell's than Icon's.

jackweirdy 9y ago

> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s a good place to start learning some of this stuff? By stuff I mean things related to algebra and whatever the black magic I quoted is

jklehm 9y ago
Discrete mathematics is the branch of math you're after. This looks like it has some ok examples: https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematical_induction.htm https://www.tutorialspoint.com/discrete_mathematics/discrete...
pkaye 9y ago
This would be a finite series. I think it is usually covered in calculus courses but some of the basics are discussed in earlier algebra courses. Here is a link to a brief summary on finite series. http://calculus.nipissingu.ca/tutorials/finiteseries.html http://calculus.nipissingu.ca/tutorials/finiteseries.html You can also start your way up from the basics in Khan's Academy.
metahost 9y ago
Any arithmetic book on Sequence and Series will provide you with the basic toolset to derive the above.
feikname 9y ago
I do not have an formal math education, but I'm fairly sure what you quote is part of the Arithmetic Progression concept (the sum formula more specifically), so taking a look at the arithmetic branch of math might be a good idea. Wikipedia[0], MathWords[1] and Brilliant[2] might be some good resources for you. [0] https://en.wikipedia.org/wiki/Lists_of_mathematics_topics https://en.wikipedia.org/wiki/Lists_of_mathematics_topics [1] http://www.mathwords.com/ http://www.mathwords.com/ [2] https://brilliant.org/ https://brilliant.org/
toAnswerIt 9y ago
to see it consider this: S = 1 + 2 + 3 + ... + n-1 + n + S = n + n-1 + n-2 + ...+ 2 + 1 = 2S = n+1 + n+1 + n+1 + ... + n+1 + n+1 every column sums to n+1

pkaye 9y ago

If you read the first paragraph of the website, "Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."

carapace 9y ago

Oh cool! I've been working with a continuation-pasing style variant of Joy (https://en.wikipedia.org/wiki/Joy_programming_language https://en.wikipedia.org/wiki/Joy_programming_language https://github.com/calroc/joypy https://github.com/calroc/joypy) and tried it on the Project Euler problem 1: https://github.com/calroc/joypy/blob/master/docs/3.%20Developing%20a%20Program.md https://github.com/calroc/joypy/blob/master/docs/3.%20Develo... I came up with a solution that generalizes to blocks of terms, but yours is much much nicer! Cheers! """ Between 0 and 990 inclusive there are sixty-six "blocks" of seven terms each, starting with: [3 5 6 9 10 12 15] And ending with: [978 980 981 984 985 987 990] If we reverse one of these two blocks and sum pairs... """ The Advent of Code 2017 includes a puzzle involving a "spiral" memory grid and I had a similar thing where I was able to figure out a simple mathematical way to solve the puzzle: https://github.com/calroc/joypy/blob/master/docs/Advent%20of%20Code%202017%20December%203rd.md https://github.com/calroc/joypy/blob/master/docs/Advent%20of... I'm not explaining it well 'cause I'm all excited to show it.