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)
(let ((term (head 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.
No comments:
Post a Comment