J-ottings 9: The Power Conjunction
Vector 12:4, page 27
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 27
This is the most powerful article yet in this series; I can say this with confidence because the starting theme is the power conjunction ^:.
The sequence "verb conjunction noun" as in +^:2 defines a new verb. A very simple example is that of finding the nth term of the series 1,3,7,15,31,63,... This can be obtained either using the power verb:
or by using the power conjunction:
A more sophisticated use of ^: is in standard algorithms for evaluating Fibonacci terms and series.
First the verb fa describes the essential Fibonacci operation, which transforms the number pair (a,b) into the pair (b,(a+b)):
The power conjunction can be used to execute it any required number of times:
If it is the whole series which is required, define
fb=.] , +/@(_2&{.) NB. Join sum of last 2 terms onto
the series
(fb^:15)0 1 NB. Add 15 terms to the series
which starts 0 1
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
These examples show clearly how strongly the power conjunction ^: is associated with iteration.
Now compare the above with a recursive approach. The Fibonacci problem is amenable to the technique which Hui and Iverson call "tail recursion", which they discuss extensively in [1], and which is also discussed in J-ottings 3. It is worth thinking initially about general techniques for converting iterative verbs to recursive ones, for which purpose return to step which is used below both iteratively and recursively.
step=.>:@+: NB. 2y. + 1
(step^:5)0 NB. Iteration using power
conjunction
31
(0:`(step@$:@<:)@.*)5 NB. Recursion using gerund and
agenda
31
This simple case can be used as a general prototype. For fb, if the left argument is the number of terms required, the stopping condition is determined by the hook ~:$. To obviate a rank error following agenda, a conversion from a 1-item vector to a scalar must be included, leading to the stopping function
and thence to the recursive form
In a similar way the recursive equivalent of fa can be obtained as:
Another illustration of the power conjunction is Sylvester’s algorithm, which takes a vulgar fraction in the range (0,1), and expresses it as a sum of best-fitting unit fractions. For example, 0.67296 is well approximated by
1/2 + 1/6 + 1/159 + 1/248438
The result of the algorithm can thus be expressed as a series of increasing integers, in general of indefinite length. In the above example, the series would be (2,6,159,248438, ...). In the realisations which follow, the result series has at its head the error term, that is, the remaining fraction which has to be decomposed, so that successive results are:
APL and J renderings of this algorithm were published by Donald McIntyre in the IBM Systems Journal APL Anniversary edition [2], and a further APL implementation of this algorithm is given in a Vector Technical Note [3]. An iterative approach in J using ^: is significantly different in style. Taking f as a fraction, first define a verb nig to mean "next integer greater than 1/f", so that, for example nig 0.333 is 4, and nig 0.334 is 3.
The next steps in the algorithm are to use the hook -% to derive x.-1/y., and to apply this following (atop) nig, which in turn is applied to the current error term. This leads to the verb
which is the core of the algorithm.
Finally adjust the result series to its standard form, ready to start all over again:
Thus the original problem is solved by
Here is the result of applying three Sylvester steps to the fractional part of pi:
z=.(o.1)-3 NB. Fractional part of pi
(syl^:3)z NB. Numerical error, 1st 3
Sylvester terms
7.77959e_9 8 61 5020
— and so 3 + 1/8 + 1/61 + 1/5020 gives pi correct to 7 decimal places.
The Technical Note [2] also describes a somewhat similar algorithm which reduces a decimal fraction to its equivalent in a different number base. Again the power conjunction suggests an iterative approach in J. The arithmetic required to find the fractional digits of 0.67296 in base 5 is:
At every step, the decimal fraction to the right of the vertical bar is multiplied by 5, and the integer and fractional parts of the result are written to the left and right of the bar on the following line. The required digits in base 5 emerge down the column to the left of the bar. Take the number base as left argument and as right argument the fraction to the right of the bar, joined to the series so far.
The actions left and right of the bar imply that two verbs are required to supply fractional and integer parts. These are 1&| and <. respectively which combine as a gerund following (atop) the multiplication:
The verb /. makes the gerund to its left executable, and can also be written :0.
For steps after the first, it is necessary to pick off the fractional part using {. (head), so define the fork
In order to complete the goal of carrying forward the digits as they are found, amend f to the final form
fdiv=.([ g {.@]),}.@] NB. apply g to fraction and
append digits so far
5(fdiv^:3)0.67296
0.12 4 1 3
5(fdiv^:5)0.67296
0 3 0 4 1 3
Conversion to recursive forms can readily be applied to both syl and fdiv to obtain
sylr=. ]`(p@(<:@$:]))@.(*@[) NB. Recursive syl; x.
is countdown parm
4 sylr 0.67296 NB. cf. (syl^:4)0.67296
8.10094e_12 2 6 159 248438
fd=.(({:@[)g {.@]),}.@ ] NB. Countdown parm
to left of x.
fdivr=.]`([fd-&1 0@[$:])@.(*@{.@[) NB. Recursive fdiv
3 5 fdivr 0.67296 NB. cf. 5(fdiv^:3)0.67296
0.12 4 1 3
In the illustrations above the verbs conjoined to ^: have all been monadic. Dyadic verbs raise some interesting questions, such as:
+is a commutative verb, that is(a+b)-:b+afor all numerica,b. Is+^:2a commutative verb?- Does
2(+^:2)3mean2+2+3or2+3+3?
The answers depend on the general property of dyadic verbs that the left argument "binds" more strongly than the right. This means that 2+3 means (2+)3, that is the noun left argument acts like an adverb and creates an intermediate verb "addtwo", say, which then works on the right argument. This device is known as "currying" after the American logician H.B. Curry, and it makes it easy to answer both the above questions:
- No, since "addtwo" applied twice to 3 is
3+2x2, which is not the same as "addthree" applied twice to 2, which is2+2x3. <2(+^:2)3means "addtwo" twice to 3, so the first of the two alternatives is correct.
References¶
[1] Representations of Recursion, Roger KW Hui & Kenneth E Iverson, Proceedings of APL95 Conference, pp.91-97
[2] Language as an Intellectual Tool: From hieroglyphics to APL, D.B.McIntyre, IBM Systems Journal, Vol.30 No.4, 1991, pp.562-563
[3] Technical Note: Fractions as Sequences of Integers, Norman Thomson, Vector Vol. 12, No. 3, pp. 130-131