J-ottings 34: Greed – Patterns for the Imminent Collapse of Western Capitalism
Vector 19:2, page 38
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 38
In a communication following J-ottings 33, Ken Iverson pointed out that \(\raise{0.6ex}{x}\!\big/(1 - x - x^2)\) is a generating function for the Fibonacci numbers which in J terms is
Rewriting the generating function as
the binomial theorem gives the series expansion
Write the coefficients of the various binomial coefficients as rows of a table :
Adding down the columns should make it clear how the Fibonacci coefficients arise. But why do all this work when J will do it for you using the t. adverb to give the best fitting polynomial of given degree, say the 13th. ?:
which is exactly equivalent to the expression in J-ottings 33 :
Yet another interesting Fibonacci fact is that every positive integer can be written as the sum of a series of non-consecutive Fibonacci numbers, non-consecutive because every sum of a consecutive pair can immediately be replaced by the next higher Fibonacci number – this is the fundamental Fibonacci property. To obtain such a sum, start with a general verb which transforms any given number into the "highest value below" in a numeric list :
Define
Both the 89 and the 11 are required, the first to be stored, and the second to be processed further, so define a verb which partitions an integer in this fashion:
Using & makes f into a pseudo-constant which would be changed only if a shorter or longer Fibonacci series was required. Also, the double computation of the verb hvb in Fgap is inherently displeasing – this can be circumvented by rewriting the slightly less transparent verb :
following which Fsum remembers the left hand part of the list and processes the gap on the right :
8 and 3 are both Fibonacci numbers, and so 100 = 89 + 8 + 3.
This process can be repeated as long as necessary using a recursive verb
which says in effect "go on reducing the gap until you reach a Fibonacci number".
100 (= 89 + 8 + 3) can also be expressed in a binary form
call such numbers Finary numbers, say – they will be revisited later.
A characteristic of the above algorithm is that at every step the Fibonacci number giving the smallest gap was grabbed, a characteristic of greedy behaviour as exemplified alike by small boys sharing cakes and fat-cat directors raiding their company takings.
The term greedy algorithm is used generically to describe a range of algorithms which share this general characteristic. It arises sufficiently often to merit description as a pattern, a word which has become a technical term in the vocabulary of Object Oriented programming to mean any common way of doing things – more general than an idiom or a phrase, but not large enough to be considered as a piece of software architecture.
"Patterns" seems a good way of describing general techniques which emerge intuitively in J programming through recurrent use and reinvention. For example, the greedy technique apparent in Fsumr above might also have emerged in programming a distance reducing route starting from a given town and visiting all other towns represented in a given distance table. To be specific suppose that a distance table for four towns is
The routing problem is not altered by subtracting 11 from all the non-zero entries in the table and making the objective maximization rather than minimization. So define m as
Starting at town 0, initial greed says find the route which gives the highest reward from town 0. This is the route to town 1, from which the next greedy step is to go from town 1 to town 3 since 5>4, and the route is completed by visiting 2, thereby adding another 1 to the reward, a total of 16.
To preserve indexing it is prudent not to reduce the distance table at each recursive step but rather to reduce the reward to 0 for steps which proceed to towns already visited. Thus if the "route so far" is 0 2 1, the next town is identified by its index as the one offering the highest reward in row 1 after avoiding revisits, which requires that items 0 and 2 in row 1 must first be amended to 0 by 0(0 2)}1{m. The index of the next town is generated greedily by
imax=.i.>./ NB. index of maximum value
ntg=.dyad define NB. next town in greedy chain
imax 0(}:x.)}({:x.){y.
)
0 2 1 ntg m
3
As with f above, a distance table would be unlikely to have frequent changes and so it makes sense to build it in as a pseudo-constant m :
ontg=.ntg&m NB. row index of optimum next town
ontg 0 2 1
3
ontgr=.]`($:@(],ontg))@.(4&~:@#)
ontgr 0
0 1 3 2
A note should be made that a change in the distance matrix might require a change in the constant 4.
There is an important distinction between these two manifestations of greed. In the first, the representation of a positive integer as a sum of Fibonacci numbers can be proved to be unique, and so any algorithmic pattern would produce the same result. This is not true in the second example for which the route 0 3 2 1 has the value of 17, demonstrating that greed is not always the best policy!
It should also be stressed that it is recursion in the presence of maximum which makes these patterns greedy, not recursion alone. Simple recursion is a generalisation of the greedy pattern. This can be illustrated by venturing even further into Fibo-land and constructing a Finary adder. First assume that an ordinary binary adder is available:
The main difference between binary and Finary numbers is that Finary numbers never contain consecutive 1s, and so if two consecutive 1s were ever to turn up in an intermediate calculation these would be immediately resolved into a single 1 at the level of the next higher digit. A verb to detect such a state of affairs is :
find11=.0&,@(2&(*./\)) NB. find sublist 1 1
b NB. representation of 148
1 0 1 0 1 1 0 1 0 1
find11 b
0 0 0 0 0 1 0 0 0 0
Simple binary addition of these two lists makes the necessary adjustment :
Having made one such replacement it is possible that, as in the case above, the new 1 produces a further pair of consecutive 1s, which in turn may generate a ripple effect through the whole Finary number. Adopting the recursive pattern again, define :
Enough is now in place for a verb to add 1 to a given Finary number :
To perform a general Finary addition, e.g. 1 0 1 0 Fplus 1 0 0 0 0 1, observe that the recursive pattern requires that the data is in the form of a single argument. One technique in the present case is to keep on applying Fadd1 to one of the summands until the value in a counter matches the other, hence a suitable data format for the above sum is
and a single step of the addition process is :
Fplus1=.Fadd1&.>@(2&{.),{: NB. Add 1 to each of 0,7
Fplus1 u
+-+---------+-----------+
|1|1 0 0 0 0|1 0 0 0 0 1| NB. Finary 1(cntr),8,14
+-+---------+-----------+
Applying the general recursive pattern yet again leads to
The problems above may in themselves be academic, but the use of patterns themselves is a highly practical programming matter. Using patterns is matter of design; in the examples described above, the generic pattern can be informally described as
fnr = fnr (fn), that is, a recursive verb defined as "itself applied to the result of a matching single step verb". Many, although certainly not all, programming problems at this level are susceptible to this design pattern. To use such a pattern, three questions must have clear answers:
- Can I describe a single step verb whose result is the input to the next step?
- How do I know when to stop the recursion?
- What do I want to happen when it does?
What happens below the level of fnr = fnr (fn), for example whether code is tacit, explicit or a mixture, is a matter of implementation. For example, in the last case, an iterative design might have led to an implementation something like
Fplus=.dyad define
s=.0 [ r=.y.
while.(-.s-:x.) do.
r=.Fadd1 r [ s=.Fadd1 s end.
1 0 1 0 Fplus 1 0 0 0 0 1 NB. 7 + 14
1 0 0 0 0 0 0
Finally for those of you whose sensible habit is always to skip to the end, thereby cutting out all the turgid stuff in the middle, this article has been all about Fibonacci, patterns and greed, but the greatest of these is … (reader to complete)