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.
Constructor
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.
(canonicalize-lft-coefficients
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))
(integer
(etypecase b
(float (make-lft a (rational b) c d))
(integer
(etypecase c
(float (make-lft a b (rational c) d))
(integer
(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))))))
Printer
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>
Application
The most mundane way to use a LFT is to apply it to a number.
> (defvar *my-lft* (make-lft 3 2 4 3))
*MY-LFT*
> (funcall *my-lft* 1/5)
13/19
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) 3/4
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)) INFINITY
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)) *ADD-SEVEN* > (funcall *add-seven* 4) 11 > (funcall *add-seven* (make-lft 4 13 1 2)) #<LFT (11x + 27)/(x + 2)> > (funcall * ’infinity) 11
Conclusion
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 https://github.com/jrm-code-project/homographic/blob/main/lisp/lft.lisp
No comments:
Post a Comment