Fifty Shades of J/Chapter 37
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
In a communication following Fifty Ways to tell a fib, Ken Iverson pointed out that is a generating function for the Fibonacci numbers which in J terms is
fibfn=.0 1&p. % 1 _1 _1&p.
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 :
| x | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |
| 1 | ||||||||
| 1 | 1 | |||||||
| 1 | 2 | 1 | ||||||
| 1 | 3 | 3 | 1 | |||||
| 1 | 4 | 6 | 4 | 1 | ||||
| 1 | 5 | 10 | 10 | 5 | ||||
| ... |
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 as shown by this expression in Fifty Ways to tell a fib :
f=.(,+/@(_2&{.))^:12(0 1)
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 k into the ‘highest value below’ in a numeric list :
hvb=.>./ @(>:#]) NB. highest value below 100 hvb f 89
Define
gap=.-hvb&f gap 100 11
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 :
Fgap=.(hvb,[-hvb)&f NB. partition into fib+gap Fgap 100 89 11
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 :
Fptn=.{:@(>:#(],.-)) NB. Fibonacci partition
100 Fptn f
89 11
following which Fsum remembers the left hand part of the list and processes the gap on the right :
Fsum=.}:,Fptn&f@{: NB. single step process
Fsum 89 11
89 8 3
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
Fsumr=. ($:@Fsum)`]@.(e.&f@{:)
Fsumr 100
89 8 3
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 in which a 1 represents an integer in the reverse of the Fibonacci sequence
Fnum=.|.@(2&}.@(f&e.)@Fsumr) Fnum 100 0 0 1 0 0 0 0 1 0 1 0 0
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
0 1 5 3 1 0 7 6 5 7 0 10 3 6 10 0
The routing problem is not altered by subtracting all the non-zero entries in the table from 11 and making the objective maximization rather than minimization. So define m as
0 10 6 8 10 0 4 5 6 4 0 1 8 5 1 0 m=. 4 4$0 10 6 8 10 0 4 5 6 4 0 1 8 5 1 0
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
nextg=.dyad :’imax 0(}:x)}({:x){y’ NB. next town in greedy chain
0 2 1 nextg 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 :
optnextg=.nextg&m NB. row index of optimum next town optnextg 0 2 1 3 optnextgr=. ]`($:@(],optnextg))@.(4&~:@#) optnextgr 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 :
badd=.+&.#. NB. binary addition 1 0 1 badd 1 0 0 1 0 0 1
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 :
rep11=.badd find11 NB. replace with 1 0 0 rep11 b NB. representation of 148 1 0 1 1 0 0 0 1 0 1
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 :
rep11r=: ]`($:@rep11)@.(+./@find11) rep11r b NB. representation of 148 1 0 0 0 0 0 0 0 1 0 1
Enough is now in place for a verb to add 1 to a given Finary number :
Fadd1=.rep11r@(1&badd) Fadd1 1 0 1 0 1 NB. add 1 to Finary 12 1 0 0 0 0 0
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
u=.0;1 0 1 0;1 0 0 0 0 1 NB. Finary 0(cntr),7,14
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
Fplus=: ($:@Fplus1)`(>@(1&{))@.({.-:{:) NB. addn of Finary nos
Fplus u
1 0 0 0 0 0 0
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 programmer choice. For example, in the last case, an iterative design might have led to an implementation something like
Fplusi=.dyad :0 s=.0 [ r=.y while.(-.s-:x) do. r=.Fadd1 r [ s=.Fadd1 s end. 1 0 1 0 Fplusi 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 tedious stuff in the middle, this article has been all about Fibonacci, patterns and greed, but the greatest of these is … (reader to complete)
Code Summary
fibfn=: 0 1&p. % 1 _1 _1&p. NB. Fib nos by generating fn
f=: (,+/@(_2&{.))^:12(0 1) NB. ditto by direct method
Fnum=: |.@(2&}.@(f&e.)@Fsumr)
Fsumr=: ($:@Fsum)`]@.(e.&f@{:) NB. partitions integer into sum of Fibonacci numbers
Fsum=: }:,Fptn&f@{: NB. single step process
Fgap=: (hvb,[-hvb)&f
Fptn=: {:@(>:#(],.-)) NB. partition into fib+gap
hvb=: >./ @(>:#]) NB. highest value below
Fplus=: ($:@Fplus1)`(>@(1&{))@.({.-:{:) NB. addn of Finary nos
Fplus1=: Fadd1 each@(2&{.),{: NB. Add 1 to each Fadd1=:rep11r@(1&badd)
rep11r=: ]`($:@rep11)@.(+./@find11)
Fadd1=: rep11r@(1&badd)
rep11=: badd find11
badd=: +&.#. NB. binary addition
find11=: 0&,@(2&(*./\)) NB. find list 1 1
Greedy Algorithm applied to distance table
optnextgr=.]`($:@(],optnextg))@.(4&~:@#)
optnextg=.nextg&m NB. row index of optimum next town
nextg=.dyad :’imax 0(}:x)}({:x){y’ NB. next town in greedy chain
imax=.i.>./ NB. index of maximum value
Iterative design Fplus
Fplusi=:dyad :0 s=.0 [ r=.y while.(-.s-:x) do. r=.Fadd1 r [ s=.Fadd1 s end.