Re: [Bug-apl] Help using the power operator

[Kacper Gutowski]

On Fri, Oct 30, 2015 at 11:01 AM, Elias Mårtenson <address@hidden> wrote:
>
>       4×+/{(¯1*⍵+1)÷¯1+2×⍵}¨⍳1000000
>
> The above expression performs 1 million iterations, but is also allocates a
> 1 million element array to do so.

I don't know GNU APL internals well enough to speak about when and how
memory is allocated, but when I remove each (¨) from the above
expression (it's not needed there, this dfn is a scalar function)
then it runs many times faster but surprisingly seems to take even
more memory.

> Is there a simple and natural way to perform this computation in an
> iterative manner using the power operator (⍣)?

While you can use ⍣ to express any kind of iteration, it doesn't mean
you should.  This algorithm is a sum, intrinsically; trying to rewrite
it as an iterated function won't do any good, it can be neither simple
nor natural (and would also be a lot slower).  It's natural only for
algorithms that are written as f(f(f(...))).

Your code is good because it reads exactly like, and is immediately
recognizable as the arctangent formula you were trying to implement.
Optimizing interpreter could, however, recognize that this is a simple
sum of scalar function of iota, and that it could be computed in
constant space.


That being said, a straightforward translation to iterative form using
global variable for loop counter may look like this:

      i←0 ◊ 4×{⍵+(¯1*i+1)÷¯1+2×i←i+1}⍣1000000⊢0

In hopefully constant memory, but very slow and not as legible.
Attempting not to use global variables would make it even worse.

So if memory is scarce and must be optimized for, disregarding
legibility, I would try partitioning it into smaller ranges rather
than switching to iterative variant completely:

      4×+/{ +/{(¯1*⍵+1)÷¯1+2×⍵} (1000×⍵)+⍳1000 }¨ (⍳1000)-1

This at least saves some of the performance of the original.

-k