[Jprogramming] arithmetic sequence

[Boyko Bantchev]

In a loop-based solution, the elements of the sequence S(i) may be
computed according to the recurrence relation, but working upwards,
from S(i) to S(i+1).  This guarantees completion in linear time
w.r.t. the length of the sequence.

In an array-based solution making use of the same relation, ideally,
each S(i), i=1,…,n would be computed independently of the others,
thus repeating the same computations over and over again, and
resulting in an amount of work as large as n²/2.

A closed formula approach may be attractive as it easily gives an
array-based solution with direct, non-incremental computation of
each item, which would seem to result in linear overall time.
However, the closed formula contains 5&^ which would not be
computed in constant time, so the overall performance would not
be linear.

All implementations suffer an additional slowdown when extended
arithmetic is involved, but the amount of that slowdown is hard to
estimate.

Following Roger's suggestion, I made some observations on the actual
times J takes to compute hr1x, hr2x, and la1x, depending on the length
of the sequence.  hr1x and hr2x

   hr1x =: 3 : 'y(0 3+*&5)@]^:(i.@[)1 0x'
   hr2x =: 3 : '(i.y)(5&(0 3+*))1 0x'

are clearly below the seeming n²/2 time required, so the J interpreter
apparently optimizes execution by utilizing previously computed values
of S(i).  However, la1x

   la1x =. 3 : '(],.3*4%~1-~])5x^i.y'

starting from below 1000, exhibits at least a cubic behaviour:
doubling the length of the computed sequence results in a ≥8x longer
execution time.  In this case, it seems that J is unable to optimize:
the powers of 5 must be computed independently of each other, and
perhaps also the verb in parentheses applies to the powers after they
are all computed first.  But this is really a wild guess.