Doc/Articles/Play132
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
12. Volutes
. By Eugene McDonnell. First published in Vector, 13, 2, (October 1996), 144-153.
This article describes an amazing algorithm that I learned from Joey Tuttle. It produces an integer volute. I call it amazing on good evidence, because I was amazed when he first showed it to me. I had written a function to produce such volutes many years ago [McDonnell, E. E., Spirals & Time, APL Quote Quad 7 4, Winter 1977], and thought I had done a fairly efficient job, but Tuttle's analysis was far superior.
An integer volute can be drawn in a variety of ways. All of the cases we'll consider place the integers in the cells of a rectangular, and usually square, table. Two kinds of volutes can be drawn in this manner: an involute and an evolute. In an involute the smallest integer appears in a corner of the table, and the integers increase as they get closer to the center. In an evolute the largest number appears in a corner of the table, and the integers decrease as they get closer to the center of the table.
0 1 2 3 4 24 23 22 21 20
15 16 17 18 5 9 8 7 6 19
14 23 24 19 6 10 1 0 5 18
13 22 21 20 7 11 2 3 4 17
12 11 10 9 8 12 13 14 15 16
involute evolute
In the involute above the numbers increase in a clockwise rotation. They could just as easily have increased in a counter-clockwise rotation. The number 0 appears in the top left corner of the table, but it could just as well have appeared in any of the other three corners. There are then eight possible ways of drawing the involute: with 0 appearing in any of four corners, and the numbers increasing in a clockwise or counter-clockwise rotation. Similar remarks apply to the evolute, mutatis mutandis. Furthermore, either form can be derived from the other by applying the verb 24&- to it. The least number is 0 in these volutes. A volute having 1 as the least number can be obtained from one of these by adding 1 to it.
Our verbs will take as argument the length of the side of the square table. For example, if e is our evolute verb,
e 3 8 7 6 1 0 5 2 3 4
I'll give six solutions to the problem, each one increasing in speed. The best is a variation of the marvelous technique shown me by Tuttle.
In the book Concrete Mathematics by Graham, Knuth, and Patashnik, Exercise 3.40 takes a scalar approach to the problem of constructing an evolute. It assumes an x,y coordinate system, with 0 at coordinates (0,0). It gives two ways of arriving at a solution, problems a and b. Both solutions produce a bottom right clockwise volute.
In problem a, it squares (*:) its argument, then produces the list of that many consecutive integers, beginning with 0. It finds the x and y coordinates of each number (GKPax,.GKPay), upgrades the resulting two-column table (/:), then reshapes ($) this upgrade list into a square (,~) table.
For example, for a square of side 3, problem a takes n=.i.*:3 and yields x and y, upgrades this, and reshapes the upgrade:
]n=.i.*:3 0 1 2 3 4 5 6 7 8 ]xy=.(GKPax,.GKPay) n 0 0 0 1 _1 1 _1 0 _1 _1 0 _1 1 _1 1 0 1 1 ]w=./:xy 4 3 2 5 0 1 6 7 8 (,~3)$w 4 3 2 5 0 1 6 7 8
In problem a the placement of each integer requires the evaluation of two functions, GKPax to give the x-coordinate, and GKPay to give the y coordinate. A function evGKPa to give a square evolute of a given order is:
GKPae =. 0:=2&| NB. GKPae y=1 if y is even GKPao =. 1:=2&| NB. GKPao y=1 if y is odd GKPaq =. <.@+:@%: NB. floor double sqrt GKPam =. <.@%: NB. m is floor sqrt GKPal =. >.@-:@GKPam NB. ceiling half m GKPar =. _1:^GKPam NB. parity (1 or _1) GKPat =. (*>:)@GKPam NB. m*(1+m) GKPax =. GKPar*((]-GKPat)*GKPae@GKPaq)+GKPal GKPay =. GKPar*((]-GKPat)*GKPao@GKPaq)-GKPal evGKPa =. ,~ $ /:@(GKPax ,. GKPay)@i.@*:
In problem b the table of x-y indices is used to produce the integers, one at a time.
GKPb0 =. +:@(>./"1)@:|
GKPb1 =. >@,@{@(;~)@(>.@-:@- + i.)
GKPb2 =. _1: ^ </"1
GKPb3 =. *:@[ + GKPb2@] * [ + +/"1@]
GKPb4 =. (GKPb0 GKPb3 ])@GKPb1
evGKPb =. ,~$GKPb4
GKPb1 produces the 2-column table of x, y coordinates. GKPb0 gives a list of the doubles (+:) of the maximum over (>./) the rows ("1) of the magnitudes (|) of the items in the table. GKPb2 produces a list where the items are _1 where in the corresponding row x is less than y, and 1 otherwise. GKPb3 squares its left argument, and adds this to the product of the _1 1 list with the sum of the left argument and the sum of the rows of the right argument. GKPb4 supplies the appropriate left and right arguments to GKPb3. The verb evGKPb reshapes this list, giving the same result as evGKPa.
For example:
]xy=.GKPb1 3 _1 _1 _1 0 _1 1 0 _1 0 0 0 1 1 _1 1 0 1 1 ]ns=.(GKPb0 GKPb3 ]) xy 4 3 2 5 0 1 6 7 8 (,~3) $ ns 4 3 2 5 0 1 6 7 8
In Vector 11 4, Keith Smillie gives a suite of functions to produce a square evolute (I've replaced his 'rows' function by #, made it 0-origin, and abbreviated his names QuarterTurn and Wind and Spiral). It produces its result by successive windings of new layers onto the beginning empty table. The function Wd is, you will note, recursive:
QT=. [ ,"2 |.@|:@]
Wd=. [`(((#@[{.]) QT [) Wd #@[}.])@.(0:<#@])
Sp=. (i. @ ((-/ @ ]) , 0:)) W i.@(*/)@]
evKS=. (i.@(0:,0:)) Wd i.@*:@]
Smillie's volute is top right clockwise and has the advantage of not being limited to square results. You can find the details of the algorithm in his Vector article.
In my 1977 article I give a function like Smillie's in achieving its result by winding, but iterative (^:) rather than recursive. The function evEEM0 below reverses and transposes (|:@|.) its argument (thus giving it a clockwise quarter turn), then appends as a new bottom row a vector of integers (i.) as long as the number of rows in the argument (#), with its first item the number of items in the argument (*/@$). This is initiated with an empty table (i.0 0), and is repeated double (+:) the argument times. It is bottom right counter-clockwise.
evEEM0=.|:@|. , */@$ + i.@# evEEM1=.[:i.0 0"_[] NB. constant empty table evEEM=.evEEM0^:(+:`evEEM1)
I sent an early draft of this paper to Roger Hui for comments, and he replied:
"Motivated by your comment on +/\^:_1, I arrived at the following solution after studying the results of
f=: +/\^:_1@evJKT
It is more direct but less concise than your solution; it takes less space, and is faster for n greater than about 200."
Here is the kind of thing Roger saw:
f 5 24 23 22 21 20 _15 _15 _15 _15 _1 1 _7 _7 _1 _1 1 1 3 _1 _1 1 11 11 11 _1 f 7 48 47 46 45 44 43 42 _23 _23 _23 _23 _23 _23 _1 1 _15 _15 _15 _15 _1 _1 1 1 _7 _7 _1 _1 _1 1 1 1 3 _1 _1 _1 1 1 11 11 11 _1 _1 1 19 19 19 19 19 _1 f 9 80 79 78 77 76 75 74 73 72 _31 _31 _31 _31 _31 _31 _31 _31 _1 1 _23 _23 _23 _23 _23 _23 _1 _1 1 1 _15 _15 _15 _15 _1 _1 _1 1 1 1 _7 _7 _1 _1 _1 _1 1 1 1 1 3 _1 _1 _1 _1 1 1 1 11 11 11 _1 _1 _1 1 1 19 19 19 19 19 _1 _1 1 27 27 27 27 27 27 27 _1
And here is his version:
even =: 0: = 2&| odd =: 1: = 2&| line0 =: *:@(-even) - odd + i. c3 =: 1: ,. ] ,. _1: top =: odd }."1 ((|.,.+: ,.|.) #"1 c3@( 1&+)@(_8&*))@:>:@i.@-:@(-~ >:@even) bot =: -@even }."1 ((|.,.<:@+:,.|.) #"1 c3@(_5&+)@( 8&*))@:>:@i.@-:@(-odd) evHUI=: [: +/\ line0 , top , bot evHUIf=: evHUI f.
Hui's volute is top left counter-clockwise. If you look at the timings in the table below you will see that by size 89 Hui's version is as fast as Tuttle's (the unrounded ratio of Hui's to Tuttle's for case 89 was 1.4:1).
Now we come to Joey Tuttle's masterpiece. I asked him recently how he had arrived at it, but he no longer remembered. He had only a dim recollection that it arose in connection with one of Martin Gardner's Scientific American columns. I conjecture that it may have been Gardner's column on Stanislas Ulam's spiral of primes (see Smillie's Vector article). So I don't know how it came to Joey, but I do know that until I went at the problem backwards from the conclusion, I had no idea how the function worked, so that's how I'll describe it to you. I should say that Joey's function produced an involute, that is, he gave the result:
0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
Now, we could get the result we desire by subtracting this from 24, but that would spoil my fun, so bear with me.
Let's begin with an evolute, and see if we can trace it back (we're reverse engineering) so that we can produce the function ourselves. In the course of doing this, we'll find it convenient to use J's ability to provide inverses for many primitive and derived verbs, using the power conjunction to the minus-1 power (^:_1):
evJKT 5 24 23 22 21 20 9 8 7 6 19 10 1 0 5 18 11 2 3 4 17 12 13 14 15 16
It seems to me that Joey must have had a series of insights. I assume that his first insight was to ravel this:
]q=.,evJKT 5 24 23 22 21 20 9 8 7 6 19 10 1 0 5 18 11 2 3 4 17 12 13 14 15 16
I think he then had the tremendous insight that this list came about as the result of an upgrade. We'll get p, the permutation inverse to q, easily:
]p=./:^:_1 q 12 11 16 17 18 13 8 7 6 5 10 15 20 21 22 23 24 19 14 9 4 3 2 1 0
(Since upgrade is self inverse, we could have got p from q even more easily by writing p=./:q -- but we're not assuming that all readers will know this fact about upgrade.)
Now the final stupendous insight was to assume that p was produced by a sum scan of some list d, that is
p=. +/\ d
We can determine what the d was that gave us p by applying the inverse of sum scan:
]d=.+/\^:_1 p 12 _1 5 1 1 _5 _5 _1 _1 _1 5 5 5 1 1 1 1 _5 _5 _5 _5 _1 _1 _1 _1
This is beginning to look promising. At this point we can write the overall function evJKT:
evJKT =. ,~ $ /: @ (+/\) @ evJKT2
This sumscans (+/\) the result of evJKT2, upgrades (/:) it, and reshapes ($) the upgrade into a square (,~) table.
All this is great art -- the rest is carpentry. Forget the leading 12 for the moment. If we do, we see that the other items all have the magnitude 1 or 5, and alternate in sign: first _1 and 5, then 1 and _5, and so on in alternation. There are nine groups of _1 5 1 _5, used cyclically. We note also that the groups increase in count: one each of _1 and 5, two each of 1 _5, three each of _1 and 5, then four each of 1 _5, and lastly an anomalous four of _1. We can generate the list of one each of the nine values easily:
evJKT1=.<:@+: $ _1: , ] , 1: , -
The phrase _1: , ] , 1: , - when applied to its argument gives us the right argument to the reshape verb:
(_1: , ] , 1: , -) 5 _1 5 1 _5
and the phrase <:@+: gives us the left argument:
(<:@+:) 5 9
so that the whole phrase gives us the list of values to be replicated:
(<:@+: $ _1: , ] , 1: , -) 5 _1 5 1 _5 _1 5 1 _5 _1
Now we need to specify how many times each of these is to be replicated:
evJKT0=.}:@(2: # >:@i.)
This verb begins by giving us a list of integers:
i. 5 0 1 2 3 4
adds one to this:
>:i.5 1 2 3 4 5
gives us two of each:
2 # 1 2 3 4 5 1 1 2 2 3 3 4 4 5 5
and curtails (}:) this list:
}: 2 # 1 2 3 4 5 1 1 2 2 3 3 4 4 5
The last item should be a 4, not a 5, but as you shall see, we'll find it useful to produce an extra item.
The verb evJKT0 encapsulates the whole:
evJKT0 5 1 1 2 2 3 3 4 4 5
Now we can write evJKT2:
evJKT2=._1&|.@(evJKT0 # evJKT1)
The expression in parenthesis does the main job:
(evJKT0 # evJKT1) 5 _1 5 1 1 _5 _5 _1 _1 _1 5 5 5 1 1 1 1 _5 _5 _5 _5 _1 _1 _1 _1 _1
There is an extra _1 at the end, but the next expression rotates this list one to the right, moving the extra _1 to the beginning of the list:
_1&|. (evJKT0 # evJKT1) 5 _1 _1 5 1 1 _5 _5 _1 _1 _1 5 5 5 1 1 1 1 _5 _5 _5 _5 _1 _1 _1 _1
Why is the last _1 rotated to become the leading item? A little thought will convince you that the value of the first item doesn't have to be 12; in fact its value is irrelevant -- it could be any number at all! It serves only to act as a base for the ensuing sumscan, which, in turn, serves as the argument to upgrade. The upgrade will give the same result no matter what the value of the first item is; only the relative values of the items are important. And, since we are going to discard the last item of the list and then prefix the list with an arbitrary value, it suffices to combine these operations by performing the _1 (right) rotate of the list.
The verb evJKT provides the finishing touches to the result of evJKT2:
evJKT=. (,~ $ /: @ (+/\) @ evJKT2)
It uses evJKT2 to produce the list which it then sumscans:
+/\ evJKT2 5 _1 _2 3 4 5 0 _5 _6 _7 _8 _3 2 7 8 9 10 11 6 1 _4 _9 _10 _11 _12 _13
Notice that the items of this list are distinct and include all 25 integers from _13 through 11.
The upgrade of this list is obtained:
(/:@(+/\)@evJKT2) 5 24 23 22 21 20 9 8 7 6 19 10 1 0 5 18 11 2 3 4 17 12 13 14 15 16
and, at last, this list is reshaped ($) into the desired square integer evolute:
(,~ $ /: @ (+/\) @ evJKT2) 5 24 23 22 21 20 9 8 7 6 19 10 1 0 5 18 11 2 3 4 17 12 13 14 15 16 evJKT 5 24 23 22 21 20 9 8 7 6 19 10 1 0 5 18 11 2 3 4 17 12 13 14 15 16
The relative timings of the GKPa, GKPb, KS, EEM, HUI, and JKT verbs are of interest. The column headings give the size of table generated and the row stubs indicate the verb used. The timings are relative to those of JKT set to 1.
verb\size 5 8 13 21 34 55 89 GKPa 12 23 85 110 200 224 244 GKPb 5 10 37 47 83 94 106 KS 6 8 20 23 33 167 _ EEM 2 4 10 9 12 13 16 HUI 3 3 5 3 3 2 1 JKT 1 1 1 1 1 1 1
The infinite (_) entry for row KS in the column headed 89 indicate that there wasn't enough memory to complete execution. This was probably due to the many levels of recursion required.
The timings show the superiority of array strategies (KS, EEM, HUI, and JKT) over scalar strategies (GKPa and GKPb), and the superiority of iteration (EEM) over recursion (KS) and the superiority of a strategy minimizing data movement (HUI and JKT) over strategies involving a great deal of data movement (KS and EEM).
I haven't discussed how the Tuttle algorithm can be modified to yield the other volute types. If you look back at the verb evJKT1, you'll see that the expression to the right of the reshape sign ($) is
_1: , ] , 1: , -
so that, given the argument 5, it yields
_1 5 1 _5
The key is that this consists of _1 5 followed by its negative, 1 _5. A little experimentation will convince you that the eight possible changes of sign and order of the list _1 5 will give you all eight types of evolute:
1 5 top right clockwise
1 _5 bottom right counter-clockwise
_1 5 top left counter-clockwise
_1 _5 bottom left clockwise
5 1 bottom left counter-clockwise
5 _1 bottom right clockwise
_5 1 top left clockwise
_5 _1 top right counter-clockwise
So that to obtain a top left clockwise volute, one would use:
_5 1 5 _1
instead of _1 5 1 _5.
A verb to yield involutes is somewhat simpler than the verb yielding evolutes. The greater simplicity arises because no attention has to be paid to the first and last items: as they are generated so they are usable:
ivJKT0 5 NB. just the reverse of evJKT0 5 5 4 4 3 3 2 2 1 1 ivJKT1 5 NB. essentially unchanged 1 5 _1 _5 1 5 _1 _5 1 ivJKT2 5 NB. different 1 1 1 1 1 5 5 5 5 _1 _1 _1 _1 _5 _5 _5 1 1 1 5 5 _1 _1 _5 1 +/\ivJKT2 5 NB. same sumscan 1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13 /:+/\ivJKT2 5 NB. same upgrade 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8 5 5$/:+/\ivJKT2 5 NB. same reshape 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
Vector Vol.13 No.2