Sunday, January 28, 2024

Exponentiating Functions

If we compose a function F(x) with itself, we get F(F(x)) or F∘F. If we compose it again, we get F(F(F(x))) or F∘F∘F. Rather than writing ‘F’ over and over again, we can abuse exponential notation and write (F∘F∘F) as F3, where the superscript indicates how many times we compose the function. F1 is, naturally, just F. F0 would be zero applications of F, which would be the function that leaves its argument unchanged, i.e. the identity function.

The analogy with exponentiation goes deeper. We can quickly exponentiate a number with a divide and conquer algorithm:

(defun my-expt (base exponent)
  (cond ((zerop exponent) 1)
        ((evenp exponent) (my-expt (* base base) (/ exponent 2)))
        (t (* base (my-expt base (- exponent 1))))))
The analagous algorithm will exponentiate a function:
(defun fexpt (f exponent)
  (cond ((zerop exponent) #'identity)
        ((evenp exponent) (fexpt (compose f f) (/ exponent 2)))
        (t (compose f (fexpt f (- exponent 1))))))

The function (lambda (x) (+ 1 (/ 1 x))) takes the reciprocal of its input and adds one to it. What happens if you compose it with itself? We can rewrite it as a linear fractional transformation (LFT) (make-lft 1 1 1 0) and try it out:

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

> (compose * (make-lft 1 1 1 0))
#<LFT (2x + 1)/(x + 1)>

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

> (compose * (make-lft 1 1 1 0))
#<LFT (5x + 3)/(3x + 2)>

> (compose * (make-lft 1 1 1 0))
#<LFT (8x + 5)/(5x + 3)>

> (compose * (make-lft 1 1 1 0))
#<LFT (13x + 8)/(8x + 5)>

> (compose * (make-lft 1 1 1 0))
#<LFT (21x + 13)/(13x + 8)>
Notice how the coefficients are Fibonacci numbers.

We can compute Fibonacci numbers efficiently by exponentiating the LFT 1 + 1/x.

> (fexpt (make-lft 1 1 1 0) 10)
#<LFT (89x + 55)/(55x + 34)>

> (fexpt (make-lft 1 1 1 0) 32)
#<LFT (3524578x + 2178309)/(2178309x + 1346269)>
Since we’re using a divide and conquer algorithm, raising to the 32nd power involves only five matrix multiplies.

Fixed points

If an input x maps to itself under function f, we say that x is a fixed point of f. So suppose we have a function f with a fixed point x. We consider the function f’ which ignores its argument and outputs x. If we compose f with f’, it won’t make difference that we run the result through f again, so f’ = f∘f’ = f. You can find a fixed point of a function by composing the function with its fixed point. Unfortunately, that only works in a lazy language, so you have two options: either choose a finite number of compositions up front, or compose on demand.

You can approximate the fixed point of a function by exponentiating the function to a large number.

(defun approx-fixed-point (f) 
  (funcall (fexpt f 100) 1))

> (float (approx-fixed-point (make-lft 1 1 1 0)))

> (float (funcall (make-lft 1 1 1 0) *))

Alternatively, we could incrementally compose f with itself as needed. To tell if we are done, we need to determine if we have reached a function that ignores its input and outputs the fixed point. If the function is a LFT, we need only check that the limits of the LFT are equal (up to the desired precision).

(defun fixed-point (lft)
  (let ((f0   (funcall lft 0))
        (finf (funcall lft ’infinity)))  
    (if (and (numberp f0)
             (numberp finf)
             (= (coerce f0 ’single-float) 
                (coerce finf ’single-float)))
        (coerce f0 ’single-float)
        (fixed-point (compose lft lft)))))

> (fixed-point (make-lft 1 1 1 0))

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