3 ms·

APL: +/⍳1E9 Try it yourself, download NARS2000 (free) here: http://www.nars2000.org/ http://www.nars2000.org/ The "⍳" character is entered by typing ALT+i

APL: +/⍳1E9 Try it yourself, download NARS2000 (free) here: http://www.nars2000.org/ http://www.nars2000.org/ The "⍳" character is entered by typing ALT+i Explanation: 1E9 is 1,000,000,000 ⍳1E9 generates a vector containing integers from 1 to 1,000,000,000 (inclusive) +/ is the sum of the vector Any good APL interpreter will not actually generate a vector with a billion numbers but rather recognize the above expression and optimize the resulting operation for speed and minimal resource utilization. EDIT: Technically the "/" is the "reduction" operator acting along the last axis. In the case of a single dimensional array it acts along the only available axis. If, instead, it was acting on a matrix it would reduce along the columns. Here's a longer annotated example with output from the interpreter: Generate a vector from 1 to 10: ⍳10 1 2 3 4 5 6 7 8 9 10 Sum: +/⍳10 55 Generate a vector of ten one's and zero's, repeating until the end: 10⍴1 0 1 0 1 0 1 0 1 0 1 0 Now use that vector to reduce the original 1 to 10 vector, grabbing every other element starting with the first. The effective result is that you end up with all the odd numbers between 1 and 10: (10⍴1 0)/⍳10 1 3 5 7 9 Same things, now grabbing the even numbers by flipping the 1 0 sequence to 0 1: (10⍴0 1)/⍳10 2 4 6 8 10 Sum of all odd integers between 1 and 10: +/(10⍴1 0)/⍳10 25 Sum of all even integers between 1 and 10: +/(10⍴0 1)/⍳10 30 One could create a single vector with the odd integers between 1 and 10 followed by the even integers between 1 and ten by simply concatenating the generating expressions (APL executes from right to left): ((10⍴1 0)/⍳10),(10⍴0 1)/⍳10 1 3 5 7 9 2 4 6 8 10 And then you can reshape ("⍴") the result into a matrix: 2 5⍴((10⍴1 0)/⍳10),(10⍴0 1)/⍳10 1 3 5 7 9 2 4 6 8 10 Finally, use the scan operator again, now applied to a matrix, to sum along the columns and produce a result for each row. The effect is to output a two element vector with the sum of the odd integers between 1 and 10 as the first element and the sum of all the even integers between 1 and 10 as the second: +/2 5⍴((10⍴1 0)/⍳10),(10⍴0 1)/⍳10 25 30 If you want to try this type the lines immediately following my comments above right into the interpreter. The rho "⍴" or reshape operator is entered by typing ALT+r. Hope this helps make sense of it. Of course, there are other ways to accomplish the same thing. https://en.wikipedia.org/wiki/APL_syntax_and_symbols https://en.wikipedia.org/wiki/APL_syntax_and_symbols

swirepe 13y ago
Or J, if you're into that sort of thing +/i.1E9+1 You can get that here: http://www.jsoftware.com/stable.htm http://www.jsoftware.com/stable.htm
robomartin 13y ago
Seeing that some are adding timings to the posted solutions. The APL solution I posted above (+/⍳1E9) takes 56 microseconds to execute on my system (checked by solving it 100,000 times in a loop). The interpreter is obviously not doing a huge memory and clock-cycle sucking expansion of a one billion element vector. This highlights another advantage of a symbolic language: Idioms or patterns within code can be recognized replaced with equivalent highly-efficient, highly-tuned operations. The above example is obviously solved by having the interpreter swap it out for the well-understood mathematical solution. Because of this the programmer can focus on the problem space rather than having to dork around with figuring out optimizations. Granted, this is a simple one for anyone with a decent math background, but it can get far more complex. Have a look at the famous Finn APL idiom library: http://aplwiki.com/FinnAplIdiomLibrary http://aplwiki.com/FinnAplIdiomLibrary An interpreter designer might very well decide to detect a good number of these idioms and execute highly tuned code instead of the memory and CPU-cycle hogging expansions that might result from running the actual code as written. In many ways I equate this to what happens when using a language like Verilog to design FPGA circuits. You are designing hardware, not software. FPGA compilers have inference engines that recognize certain structures to mean specific circuit constructs. It's a contract. We agree that when I write this I mean to ask that you instantiate that and everyone is happy.

swirepe 13y ago

Or J, if you're into that sort of thing +/i.1E9+1 You can get that here: http://www.jsoftware.com/stable.htm http://www.jsoftware.com/stable.htm

robomartin 13y ago

Seeing that some are adding timings to the posted solutions. The APL solution I posted above (+/⍳1E9) takes 56 microseconds to execute on my system (checked by solving it 100,000 times in a loop). The interpreter is obviously not doing a huge memory and clock-cycle sucking expansion of a one billion element vector. This highlights another advantage of a symbolic language: Idioms or patterns within code can be recognized replaced with equivalent highly-efficient, highly-tuned operations. The above example is obviously solved by having the interpreter swap it out for the well-understood mathematical solution. Because of this the programmer can focus on the problem space rather than having to dork around with figuring out optimizations. Granted, this is a simple one for anyone with a decent math background, but it can get far more complex. Have a look at the famous Finn APL idiom library: http://aplwiki.com/FinnAplIdiomLibrary http://aplwiki.com/FinnAplIdiomLibrary An interpreter designer might very well decide to detect a good number of these idioms and execute highly tuned code instead of the memory and CPU-cycle hogging expansions that might result from running the actual code as written. In many ways I equate this to what happens when using a language like Verilog to design FPGA circuits. You are designing hardware, not software. FPGA compilers have inference engines that recognize certain structures to mean specific circuit constructs. It's a contract. We agree that when I write this I mean to ask that you instantiate that and everyone is happy.