# 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 )