Useful functions for working with continued fractions

continued-fractions.rkt

#lang racket

(define (continued-fraction p q)
  (letrec ([cf (lambda (p q)
                 (cond [(= p 1) (list q)]
                       [(< p q)
                        (cons (quotient q p)
                              (cf (remainder q p) p))]
                       [else
                        (cons (quotient p q)
                              (cf (remainder p q) q))]))])
    (let* ([g (gcd p q)]
           [n (/ p g)]
           [d (/ q g)])
      (cond [(= d 1) (list n)]
            [(< n d) (cons 0 (cf n d))]
            [else (cf n d)]))))

(define (fraction cf)
  (foldr (lambda (a b) (if (= b 0) a (+ a (/ 1 b)))) 0 cf))

(provide/contract
 ;; converts a fraction to a continued fraction
 [continued-fraction (-> exact-nonnegative-integer?
                         exact-positive-integer?
                         (listof exact-nonnegative-integer?))]
 ;; converts a continued fraction to a fraction
 [fraction (-> (listof exact-nonnegative-integer?)
               rational?)])

;; References:
;; * Continued Fractions - An Introduction
;;   http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html

;; Unit tests

(require rackunit)

(check-equal? (continued-fraction 0 1) '(0))
(check-equal? (continued-fraction 0 2) '(0))
(check-equal? (continued-fraction 1 1) '(1))
(check-equal? (continued-fraction 1 2) '(0 2))
(check-equal? (continued-fraction 2 2) '(1))
(check-equal? (continued-fraction 2 4) '(0 2))
(check-equal? (continued-fraction 4 2) '(2))
(check-equal? (continued-fraction 45 16) '(2 1 4 3))
(check-equal? (continued-fraction 16 45) '(0 2 1 4 3))
(check-equal? (continued-fraction 41 13) '(3 6 2))
(check-equal? (continued-fraction 125 37) '(3 2 1 1 1 4))
(check-equal? (continued-fraction 5 12) '(0 2 2 2))

(check-equal? (fraction (continued-fraction 0 1)) 0)
(check-equal? (fraction (continued-fraction 0 2)) 0)
(check-equal? (fraction (continued-fraction 1 1)) 1)
(check-equal? (fraction (continued-fraction 1 2)) (/ 1 2))
(check-equal? (fraction (continued-fraction 2 2)) 1)
(check-equal? (fraction (continued-fraction 2 4)) (/ 2 4))
(check-equal? (fraction (continued-fraction 4 2)) 2)
(check-equal? (fraction (continued-fraction 45 16)) (/ 45 16))
(check-equal? (fraction (continued-fraction 16 45)) (/ 16 45))
(check-equal? (fraction (continued-fraction 41 13)) (/ 41 13))
(check-equal? (fraction (continued-fraction 125 37)) (/ 125 37))
(check-equal? (fraction (continued-fraction 5 12)) (/ 5 12))