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 inputx 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))) 1.618034 > (float (funcall (make-lft 1 1 1 0) *)) 1.618034
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))
1.618034