4 ms·
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 ==
by 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 agoWhat language is this?
- deleted 9y ago[deleted]
- farresito 9y agoHaskell
- brians 9y agoIt’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 agoRight. We don't actually know whether this Haskell code is less efficient - that depends entirely on the implementation.
- bunderbunder 9y agoCompared 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 agoI 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 agoHaskell 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 agoI'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 agoYou 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 agoand Python got this from....? (which language)
- kccqzy 9y agoWell 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 agoWell 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 agoI'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.