## Thursday, September 18, 2014

### A useful, if somewhat pointless, trick with homographic functions

In my previous posts I showed that if you are applying a homographic function to a continued fraction, you can partly evaluate the answer before you completely apply the function. Instead of representing homographic functions as lambda expressions, I'll represent them as a list of the coefficients `a`, `b`, `c`, and `d` in `(lambda (t) (/ (+ (* a t) b) (+ (* c t) d)))`. I'll represent a simple continued fraction as a stream of the integer terms in the denominators.
Here is how you partly apply a homographic function to a continued fraction:
```(define (partly-apply hf cf)
(let ((a (first  hf))
(b (second hf))
(c (third  hf))
(d (fourth hf)))
(if (empty-stream? cf)
(values (list a a
c c)
cf)
(values (list (+ (* a term) b) a
(+ (* c term) d) c)
(tail cf))))))```
Partly evaluating a homographic function involves looking at the limits of the function as `t` starts at 1 and goes to infinity:
```(define (partly-evaluate hf)
(let ((a (first hf))
(b (second hf))
(c (third hf))
(d (fourth hf)))

(if (and (same-sign? c (+ c d))
(let ((limit1 (quotient      a       c))
(limit2 (quotient (+ a b) (+ c d))))
(= limit1 limit2)))
(let ((term (quotient a c)))
(let ((new-c (- a (* c term)))
(new-d (- b (* d term))))
(values term (list c d new-c new-d))))
(values #f #f))))
```
We can combine these two steps and make something useful. For example, we can print the value of applying a homographic function to a continued fraction incrementally, printing the most significant digits before computing further digits.
```(define (print-hf-cf hf cf)
(call-with-values (lambda () (partly-evaluate hf))
(lambda (term hf*)
(if (not term)
(call-with-values (lambda () (partly-apply hf cf))
print-hf-cf)
(begin
(display term)
;; take reciprocal and multiply by 10
(let ((a (first hf*))
(b (second hf*))
(c (third hf*))
(d (fourth hf*)))
(print-hf-cf (list (* c 10) (* d 10)
a        b)
cf)))))))```
But how often are you going to apply a homographic function to a continued fraction? Fortunately, the identity function is homographic (coefficients are 1 0 0 1), so applying it to a continued fraction doesn't change the value. The square root of 2 is a simple continued fraction with coefficients [1 2 2 2 ...] where the 2s repeat forever. We apply the identity homographic function to it and print the results:
```(printcf (list 1 0 0 1) sqrt-two)
14142135623730950488016887242096980785696718^G
; Quit!```
As you can see, we start printing the square root of two and we don't stop printing digits until the user interrupts.

A fancier version could truncate the output and print a decimal point after the first iteration.