## Tuesday, September 15, 2015

### Integers and rationals

In an earlier post, I asked readers to implement the bijection `rational->integer` and `integer->rational`. John Cowan suggested the Calkin-Wilf tree as a starting point. The Calkin-Wilf tree is a rooted binary tree where the nodes (or vertices, if you like) are labeled with positive rational numbers. It is infinite and complete: every node has two children. The Calkin-Wilf tree is constructed so that every rational number is assigned a unique node. Every positive rational number appears once and exactly once in the tree. The path from the root node to any selected rational is unique and can be encoded (in binary) as an integer.
```1 ]=> (rational->integer 355/113)

;Value: 67107847

1 ]=> (integer->rational 67107847)

;Value: 355/113

1 ]=> (cwt/value *the-calkin-wilf-tree*)

;Value: 1

1 ]=> (cwt/value (cwt/left *the-calkin-wilf-tree*))

;Value: 1/2

1 ]=> (cwt/value (cwt/right *the-calkin-wilf-tree*))

;Value: 2

1 ]=> (cwt/value (cwt/left (cwt/right (cwt/left (cwt/left *the-calkin-wilf-tree*)))))

;Value: 4/7```
Ho hum. We've all seen this sort of thing before.

Here's the unusual part:
```1 ]=> cwt/left

;Value 1236: #[linear-fractional-transform 1236 x/(x + 1)]

1 ]=> cwt/right

;Value 1237: #[linear-fractional-transform 1237 (x + 1)]```
So I can write
```1 ]=> (cwt/value ((compose cwt/left cwt/right cwt/left cwt/left) *the-calkin-wilf-tree*))

;Value: 4/7

1 ]=> (lft/compose cwt/left cwt/right cwt/left cwt/left)

;Value 1260: #[linear-fractional-transform 1260 (3x + 1)/(5x + 2)]```
(See "Playing with Linear Fractional Transforms")

The dyadic fractions are those rational numbers whose denominator is a power of 2. Numbers like 1/4, 3/8, or 11/32. These are the divisions you'd find on a ruler (in the US). Floating point numbers are usually implemented as dyadic fractions.
You can put the dyadic fractions into a binary tree as follows:

```(define *the-dyadic-fraction-tree* 1)

(define (dft/left node)
(/ (- (* (numerator node) 2) 1)
(* (denominator node) 2)))

(define (dft/right node)
(/ (+ (* (numerator node) 2) 1)
(* (denominator node) 2)))

;Value: 1

This is Minkowski's `?` (question mark) function. It maps the rational numbers on the X axis to the dyadic fraction on the Y axis. It has a number of weird properties. For example, it is strictly increasing and continuous, but it is not absolutely continuous. The function does not have a derivative in the usual sense.