Alessandro is concerned about the efficiency of the approaches that were
proposed to his problem. I make the assumption here that he wants the verb
to calculate all the values up to a specific integer in the formula.
Alessandro is worried that the approaches that are proposed may recalculate
the values S(0), S(1), S(2), over and over again, wasting processing time.
This is a typical concern of someone coming from a scalar language
background, when first confronted with matrix and recursive operations in
J. Also he worries that that these proposals may take up a considerable
amount of space during execution. He is asking if any of the solutions that
were proposed to his problem avoid this replication of the calculations.
The best way to answer his question is to program the problem using his
explicit looping approach, and compare that approach with the approaches
proposed by the various members of the forum.
Let's develop an explicit looping approach to solve the problem. Here's
Alessandro's problem coded in a typical explicit scalar looping style:
ac =: 3 : 0
n =. y
a =. 1 0
z =. a
next=.0 3+*&5
while. n > 0 do.
a =. next a
z =. z,a
n =. n-1
end.
(y, 2) $ z
)
Here are some of the other solutions proposed on the forum:
NB. Henry Rich's first proposal
next=:0 3+*&5
hr1 =: 3 : 'y next@]^:(i.@[) 1 0'
NB. Henry Rich's second proposal
next1=: 5&(0 3 + *)
hr2 =: 3 : '(i. y) next1 1 0'
NB. Linda Alford's proposal
la1=: 13 :'y ,.(3*(y-1)%4)'
ans =. la1 5^i. nn
NB. They all get the same answer
nn =. 20
(hr1 nn) -: hr2 nn
1
(hr1 nn) -: la1 5^i. nn
1
(hr1 nn) -: ac nn
1
NB. So lets see how much time and space they use
nn =. 20
ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn'
0.000143973 8128
5.27389e_5 7680
8.85397e_6 1984
0.000201332 3008
Alessandro's explicit loop approach uses about half the space of the worst
case, but takes about three times the processing time. However, Linda's
scheme is by far the best, as it uses less space and time than any other
approach.
Let's make the problem bigger
nn =. 400
ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn'
0.00121992 67456
0.00101282 67008
6.58273e_5 19264
0.00347769 10688
Now the explicit looping uses about one-seventh the space as the worst
case, but still takes three times as long to execute. Linda's approach is
still much better.
Let's go even bigger:
nn =. 5000
ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn'
0.0403787 938880
0.0389937 938432
0.00243484 295744
0.0200658 256384
Of course we know that, even though the calculations are being done, the
results are all the same after 442 iterations due to the 64-bit precision
limit. In any case, Linda's approach still wins in both categories
It's easy to convert all the verbs into extended precision by simply
putting an 'x' after the initial values in each verb. So we can see what
happens when we calculate some REALLY big numbers.
nn =. 5000x
(hr1x nn) -: hr2x nn
1
(hr1x nn) -: acx nn
1
(hr1x nn) -: la1 5^i.nn
1
ts&>'hr1x nn';'hr2x nn';'la1 5^i.nn';'acx nn'
0.0699063 2.64288e7
0.0628555 2.64615e7
7.75595 4.99236e7
2.60534 107328
To make sure:
_1{hr1x nn
1415962252209634578477123031738811510589509702067886271745966044709273451837957704713873234356418838981757946905127930678367641547976062918225219167148049544829280194391479467194986516585187823067009478259124536408143087115243914308334045872358803907166054...
_1{hr2x nn
1415962252209634578477123031738811510589509702067886271745966044709273451837957704713873234356418838981757946905127930678367641547976062918225219167148049544829280194391479467194986516585187823067009478259124536408143087115243914308334045872358803907166054...
_1{la1 5^i.nn
1415962252209634578477123031738811510589509702067886271745966044709273451837957704713873234356418838981757946905127930678367641547976062918225219167148049544829280194391479467194986516585187823067009478259124536408143087115243914308334045872358803907166054...
_1{acx nn
1415962252209634578477123031738811510589509702067886271745966044709273451837957704713873234356418838981757946905127930678367641547976062918225219167148049544829280194391479467194986516585187823067009478259124536408143087115243914308334045872358803907166054...
Well, now the explicit iterative solution wins the space battle by far.
Linda's approach looses the time battle by several orders of magnitude,
with Allessandro's verb not too far behind. . Both Henry's verbs are the
winners in the time battle using extended precision.
This shows why trying to optimize for time and space in a program can be
quite a challenge, and is often more trouble than it is worth. A
programmer's time is almost always much more valuable than a computer's
time or memory space, so getting quickly to the answer usually costs much
less than spending programming time to save computer processing time or
memory.
--
Skip Cave
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
