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