Thursday, January 25, 2024

Roll Your Own Linear Fractional Transformations

Looking for a fun weekend project? Allow me to suggest linear fractional transformations.

A linear fractional transformation (LFT), also known as a Möbius transformation or a homographic function, is a function of the form

(lambda (x)
  (/ (+ (* A x) B)
     (+ (* C x) D)))
You could just close over the coefficients,
(defun make-lft (A B C D)
  (lambda (x)
    (/ (+ (* A x) B)
       (+ (* C x) D))))
but you’ll want access to A, B, C, and D. If you implement LFTs as funcallable CLOS instances, you can read out the coefficients from slot values.


The coefficients A, B, C, and D could in theory be any complex number, but we can restrict them to being integers and retain a lot of the functionality. If we multiply all the coefficients by the same factor, it doesn't change the output of the LFT. If you have a rational coefficient instead of an integer, you can multiply all the coefficients by the denominator of the rational. If there is a common divisor among the coefficients, you can divide it out to reduce to lowest form. (In practice, the common divisor will likely be 2 if anything, so if the coefficients are all even, divide them all by 2.) We can also canonicalize the sign of the coefficients by multiplying all the coefficients by -1 if necessary.

(defun canonicalize-lft-coefficients (a b
                                      c d receiver)
  (cond ((or (minusp c)
             (and (zerop c)
                  (minusp d)))
         ;; canonicalize sign
         (canonicalize-lft-coefficients (- a) (- b)
                                        (- c) (- d) receiver))
        ((and (evenp a)
              (evenp b)
              (evenp c)
              (evenp d))
         ;; reduce if possible
         (canonicalize-lft-coefficients (/ a 2) (/ b 2)
                                        (/ c 2) (/ d 2) receiver))
        (t (funcall receiver
                    a b
                    c d))))
(defun %make-lft (a b c d)
  ;; Constructor used when we know A, B, C, and D are integers.
   a b
   c d
   (lambda (a* b*
            c* d*)
     (make-instance 'lft
                    :a a* :b b*
                    :c c* :d d*))))

(defun make-lft (a b c d)
  (etypecase a
    (float (make-lft (rational a) b c d))
     (etypecase b
       (float (make-lft a (rational b) c d))
        (etypecase c
          (float (make-lft a b (rational c) d))
           (etypecase d
             (float (make-lft a b c (rational d)))
             (integer (%make-lft a b
                                 c d))
             (rational (make-lft (* a (denominator d)) (* b (denominator d))
                                 (* c (denominator d)) (numerator d)))))
          (rational (make-lft (* a (denominator c)) (* b (denominator c))
                              (numerator c)         (* d (denominator c))))))
       (rational (make-lft (* a (denominator b)) (numerator b)
                           (* c (denominator b)) (* d (denominator b))))))
    (rational (make-lft (numerator a)         (* b (denominator a))
                        (* c (denominator a)) (* d (denominator a))))))


One advantage of making LFTs be funcallable CLOS objects is that you can define a print-object method on them. For my LFTs, I defined print-object to print the LFT in algabraic form. This will take a couple of hours to write because of all the edge cases, but it enhances the use of LFTs.

> (make-lft 3 2 4 -3)
#<LFT (3x + 2)/(4x - 3)>

Cases where some of the coefficients are 1 or 0.

> (make-lft 1 0 3 -2)
#<LFT x/(3x - 2)>

> (make-lft 2 7 0 1)
#<LFT 2x + 7>

> (make-lft 3 1 1 0)
#<LFT 3 + 1/x>


The most mundane way to use a LFT is to apply it to a number.

> (defvar *my-lft* (make-lft 3 2 4 3))
> (funcall *my-lft* 1/5)

Dividing by zero

In general, LFTs approach the limit A/C as the input x grows without bound. We can make our funcallable CLOS instance behave this way when called on the special symbol ’infinity.

> (funcall *my-lft* ’infinity)

In general, LFTs have a pole when the value of x is -D/C, which makes the denominator of the LFT zero. Rather than throwing an error, we’ll make the LFT return ’infinity

> (funcall *my-lft* -3/4))

Inverse LFTs

Another advantage of using a funcallable CLOS instance is that we can find the inverse of a LFT. You can compute the inverse of a LFT by swapping A and D and toggling the signs of B and C.

(defun inverse-lft (lft)
  (make-lft (slot-value lft ’d)
            (- (slot-value lft ’b))
            (- (slot-value lft ’c))
            (slot-value lft ’a)))

Composing LFTs

LFTs are closed under functional composition — if you pipe the output of one LFT into the input of another, the composite function is equivalent to another LFT. The coefficients of the composite LFT are the matrix multiply of the coefficients of the separate terms.

> (compose (make-lft 2 3 5 7) (make-lft 11 13 17 19))
#<LFT (73x + 83)/(174x + 198)>

Using LFTs as linear functions

A LFT can obviously be used as the simple linear function it is. For instance, the “multiply by 3” function is (make-lft 3 0 0 1) and the “subtract 7” function is (make-lft 1 -7 0 1). (make-lft 0 1 1 0) takes the reciprocal of its argument, and (make-lft 1 0 0 1) is just the identity function.

Using LFTs as ranges

LFTs are monotonic except for the pole. If the pole of the LFT is non-positive, and the input is non-negative, then the output of the LFT is somewhere in the range [A/C, B/D]. We can use those LFTs with a non-positive pole to represent ranges of rational numbers. The limits of the range are the LFT evaluated at zero and ’infinity.

We can apply simple linear functions to ranges by composing the LFT that represents the linear function with the LFT that represents the range. The output will be a LFT that represents the modified range. For example, the LFT (make-lft 3 2 4 3) represents the range [2/3, 3/4]. We add 7 to this range by composing the LFT (make-lft 1 7 0 1).

> (compose (make-lft 1 7 0 1) (make-lft 3 2 4 3))
#<LFT (31x + 23)/(4x + 3)>

Application (redux)

It makes sense to define what it means to funcall a LFT on another LFT as being the composition of the LFTs.

> (defvar *add-seven* (make-lft 1 7 0 1))

> (funcall *add-seven* 4)

> (funcall *add-seven* (make-lft 4 13 1 2))
#<LFT (11x + 27)/(x + 2)>

> (funcall * ’infinity)


This should be enough information for you to implement LFTs in a couple of hours. If you don’t want to implement them yourself, just crib my code from

No comments: