Talk:NYCJUG/2019-05-14
"Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion.
No - those are bad ways to do this. [You don't say? Maybe Gaussian shortcut using APVs?"
So... reading this, I got to thinking about how to implement +/ in a way which satisfies the described constraints.
In other words, this, but not this:
+/2 3 5 7 11 28
First, let's do the for loop:
{{t=.0 for_f.y do.t=.t+f end.}} 2 3 5 7 11 28
The while loop is basically a for loop, but let's take a moment and do the recursive variant:
({.+$:@}.)`0:@.(0=#) 2 3 5 7 11 28
Now, conceptually, to do summation with a while loop, we might want to emulate a for loop or a recursive implementation. For example:
{{t=.0 while.#y do. (y=.}.y) ] t=.t+{.y end.}} 2 3 5 7 11 28
But, really the problem statement was to do the summation using a while loop. And, we an achieve some increased efficiency by optimizing our use of that loop:
{{while.t=.0 do.end.t++/y}} 2 3 5 7 11 28
Comparing these on a moderately large arbitrary list of numbers:
V=:?1e5#0 timespacex '{{t=.0 for_f.y do.t=.t+f end.}}V' 0.0076301 10304 timespacex '({.+$:@}.)`0:@.(0=#)V' |stack error: timespacex timespacex'{{t=.0 while.#y do. (y=.}.y) ] t=.t+{.y end.}}V' 20.376 2.09971e6 timespacex'{{while.t=.0 do.end.t++/y}}V' 7.13e_5 8256 timespacex'+/V' 5.01e_5 1088
The recursive implementation would require some sleight of hand to actually succeed -- tail recursion, for example, is a popular way of satisfying "requirements" for recursion while actually optimizing the recursion out of existence. And, similarly, we can actually do a pretty good job "with" a while loop, as long as we have optimized that while loop into irrelevance. So maybe we should use our recursion this way:
+/`$:@.0: 2 3 5 7 11 28 timespacex '+/`$:@.0:V' 9.23e_5 2880
--Raul Miller (talk) 21:54, 4 February 2022 (UTC)
- I was unclear about the ending comment there "No - those are bad ways to do this." This led me to speculate about how to do it some other way but I removed my speculation about "Gaussian sum on APVs" because the summation is on an arbitrary list of numbers, not just a sequence. By "Gaussian sum" I was referring to Gauss's famous shortcut of ([: */1r2, 0 1 + #) to sum the numbers from 1 to 100.
- --Devon McCormick (talk) 23:30, 4 February 2022 (UTC)
- Understood. There's an essential silliness in the original question which leaks into any plausible answer. (As an aside, I need to mention somewhere that the "signature and timestamp button" in the wiki editor (just right of the Italics button) generates --~~~~ which then gets turned into your username and timestamp when the page gets saved. It's an often overlooked feature which makes talk pages nicer to read.) --Raul Miller (talk) 01:25, 5 February 2022 (UTC)
Upon re-reading some of the answers, I think the comment about "bad ways" meant to push for using a built-in, like sum, in whatever language you are using.
- --Devon McCormick (talk) 19:32, 6 February 2022 (UTC)