Fifty Shades of J/Chapter 25
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- ^: (power conjunction) (infix adverb) {: (tail) upper triangular matrices, Stern-Brocot trees, Farey series, closest rational approximations
ajb and arb
J has two ways of representing pairs of numbers as a single atomic entity, viz. ajb and arb 0.5 = 1r2. It is customary to associate ajb with complex numbers 0j1 = %: _1, and indeed If you think J is complex try j deals with the associated arithmetic in some detail. However there are other situations where it is convenient to deal with number pairs as single entities; j complex? you bet! illustrated how the ajb representation could be used in the context of betting and odds. Representing all rational numbers systematically is another such context in which, rather surprisingly, the ajb representation is more helpful than the arb one. The starting point is the so-called Stern-Brocot tree which is described below in a combination of words and J, with emphasis on those J features which are particularly useful. On first sight this may seem a rather ‘pure’ mathematical concept, but as the article goes on to show it has a practical usefulness in finding rational approximations to irrational numbers.
The Stern-Brocot Tree
The totality of rational fractions can be systematically generated by a binary tree named after the two mathematicians (German and French respectively) who first proposed it. Starting with the fractions 0j1 and 1j0, at every step a new fraction is inserted between every pair of fractions currently in the list, the new fraction consisting of the sums of the neighbouring numerators and denominators.
x=: 0j1 1j0 step=: dyad : 'x,(x+y)'
Since items are to be processed in overlapping pairs, use the dyadic infix adverb \ with step/ as its verb. The final tail ({: ) is because the last item in the argument must be carried forward :
SB=: monad : '(;2 step/\y),{:y'
SB x
0j1 1j1 1
The power conjunction (^:) is used to generate increasingly long Stern-Brocot tree lists :
SB^:4 x 0j1 1j4 1j3 2j5 1j2 3j5 2j3 3j4 1j1 4j3 3j2 5j3 2j1 5j2 3j1 4j1 1
To see the sense in which this is a binary tree display the successive powers of SB adding explicitly the branches which connect upwards from the final line :
Farey Series
The Farey series is a way of systematically representing all fractions. These appear as the left hand half of Stern-Brocot trees. Use the auxiliary verb ut (upper triangular)
ut=.<:/~@i. ut 5 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 t=.1 2 3 4 5 f=.t,each/t NB. square of all possible pairs
j./ converts each 2-list into the corresponding ajb form. ut confines items to regular fractions :
|:(ut 5)*each j./each f ┌───┬───┬───┬───┬───┐ │1j1│0 │0 │0 │0 │ ├───┼───┼───┼───┼───┤ │1j2│2j2│0 │0 │0 │ ├───┼───┼───┼───┼───┤ │1j3│2j3│3j3│0 │0 │ ├───┼───┼───┼───┼───┤ │1j4│2j4│3j4│4j4│0 │ ├───┼───┼───┼───┼───┤ │1j5│2j5│3j5│4j5│5j5│ └───┴───┴───┴───┴───┘
This representation is not a tree form on account of the multiple representations of e.g. 1j2 as 2j4, 3j6, etc. Another way of presenting the Farey series uses the arb representation, but this time cancellation to lowest rational form occurs :
|:(ut 5)*x:t%/t=.>:i.5 1 0 0 0 0 1r2 1 0 0 0 1r3 2r3 1 0 0 1r4 1r2 3r4 1 0 1r5 2r5 3r5 4r5 1
Finding closest approximations
A practical use of Stern-Brocot trees is to find close rational approximations to irrational numbers. First the value of a fraction ajb is given by
value=: (%/ @ +.)every value 2j3 0.666667
using the fact that +. transforms ajb into the 2-list a b. The values in an Stern-Brocot tree list which bound a given value x below and above are then
clapp=: dyad :'(_1 0++/x>y){y=.value y'
z=. SB^:(4)0j1 1j0
0.35 clapp z
0.3333 0.4
It is not necessary to use 0j1 and 1j0 as start values. For example pi is approximated using the power 10 list by
z=. SB^:(10)3j1 22j7 (o.1) clapp z 3.140625 3.141667
A small modification gives the bounding values in fraction form :
clappf=: dyad :'(_1 0++/x>value y){y'
z=. SB^:(16)3j1 22j7
(o.1) clappf z
333j106 355j113
If there is a requirement is for a rational approximation correct within a given tolerance, construct an iterative verb such as
approx=: dyad : 0
r=. y NB. initial upper and lower bounds
while. ({:x)<<./t=.|({.x)-({.x) clapp r do.
r=. SB r end. NB. do further Stern-Brocot step
(t=<./t)#({.x)clappf r NB. choose closest value of two
)
pi=: 1p1
(pi,0.00001) approx 3j1 22j7
355j113
Here are rational approximations to e :
z=. SB^:(16)27j10 28j10 (^1) clappf z 2528j930 7285j2680
Code Summary
SB=: monad : '(;2 step/\y),{:y' NB. Stern-Brocot list
step=: dyad : 'x,(x+y)'
x=: 0j1 1j0 NB. argument for SB
f=: t,each/t=. >:i.5
ut=: <:/~@i. NB. upper triangular matrix
|:(ut 5)*each j./each f NB. Farey series
The verbs clapp and clappf return closest Stern-Brocot approximation intervals in decimal and fractional form respectively
clapp=: dyad : '(_1 0++/x>y){y=. value y'
value=: (%/@+.)every
clappf=: dyad : '(_1 0++/x>value y){y'
approx=: dyad :0
r=. y NB. initial upper and lower bounds
while.({:x)<<./t=. |({.x)-({.x) clapp r do.
r=. SB r end. NB. do further Stern-Brocot step
(t=<./t)#({.x)clappf r NB. choose closest value of two
)