Friday, September 5, 2014

Another stupid homographic function trick

In my last post I showed that if you take a homographic function and apply it to a fraction, you can partly apply the function to the integer part of the fraction and get a new homographic function. The new function can be applied to the non-integer part of the fraction to generate an answer equivalent to the original function applied to the original fraction.

It turns out that you can go in the other direction as well. You can partly evaluate a homographic function. For example, consider this homographic function:
((lambda (t)
   (/ (+ (* 70 t) 29)
      (+ (* 12 t)  5))) n)
Which we intend to apply to some positive number n. Even if all we know is that n is positive, we can deduce that the value of the homographic function is between 29/5 (when t is 0) and 70/12 (as t goes to infinity). The integer part of those values are the same, so we can factor that out:
(+ 5 (/ 1 ((lambda (t)
               (/ (+ (* 12 t) 5)
                  (+ (* 10 t) 4))) n)))
The partial answer has an integer value of 5 and a fractional part that contains a new homographic function applied to our original n. We can do it again:
(+ 5 (/ 1
        (+ 1 (/ 1
                ((lambda (t)
                   (/ (+ (* 10 t) 4)
                      (+ (* 2 t) 1))) n)))))
The fractional part of the answer can itself be factored into another integer and a new homographic function applied to our original n.

A generalized continued fraction is a number of the form:
If all the bi are 1, then it is a simple continued fraction. You can turn generalized continued fractions into a simple continued fraction by doing the algebra.

What happens if you partly apply a homographic function to a continued fraction? The algebra is tedious, but here's what happens:
((lambda (t)
   (/ (+ (* 2 t) 1)
      (+ (* 1 t) 3))) (+ 3 (/ 1 (+ 7 (/ 1 16)))))

;; after one step
((lambda (t)
   (/ (+ (* 7 t) 2)
      (+ (* 6 t) 1))) (+ 7 (/ 1 16)))

;; after two steps
((lambda (t)
   (/ (+ (* 51 t) 7)
      (+ (* 43 t) 6))) 16)
By partly apply a homographic function to a continued fraction, we can process the integer part separately and before the fractional part. By partly evaluating the application of a homographic function, we can often determine the integer part without fully evaluating the argument to the function. For example, after step one above, we could instead partially evaluate the application:
;; after one step
((lambda (t)
   (/ (+ (* 7 t) 2)
      (+ (* 6 t) 1))) (+ 7 (/ 1 16)))

;; Alternatively, partially evaluate first term
(+ 1 (/ 1
       ((lambda (t)
           (/ (+ (* 6 t) 1)
              (+ (* 1 t) 1))) (+ 7 (/ 1 16)))))