How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the Scheme programming language

Problem Statement
Step by Step Solution
Sourcecode

Problem Statement

The purpose of this task is to write a function

r 2 c f

(

i n t

{\displaystyle {\mathit {r2cf}}(\mathrm {int} }

i n t

{\displaystyle N_{1},\mathrm {int} }

)

{\displaystyle N_{2})}

, or

r 2 c f

(

F r a c t i o n

{\displaystyle {\mathit {r2cf}}(\mathrm {Fraction} }

N )

{\displaystyle N)}

, which will output a continued fraction assuming: The function should output its results one digit at a time each time it is called, in a manner sometimes described as lazy evaluation. To achieve this it must determine: the integer part; and remainder part, of

{\displaystyle N_{1}}

divided by

{\displaystyle N_{2}}

. It then sets

{\displaystyle N_{1}}

{\displaystyle N_{2}}

and

{\displaystyle N_{2}}

to the determined remainder part. It then outputs the determined integer part. It does this until

a b s

(

)

{\displaystyle \mathrm {abs} (N_{2})}

is zero. Demonstrate the function by outputing the continued fraction for:

{\displaystyle {\sqrt {2}}}

should approach

[ 1 ; 2 , 2 , 2 , 2 , … ]

{\displaystyle [1;2,2,2,2,\ldots ]}

try ever closer rational approximations until boredom gets the better of you: Try : Observe how this rational number behaves differently to

{\displaystyle {\sqrt {2}}}

and convince yourself that, in the same way as

3.7

{\displaystyle 3.7}

may be represented as

3.70

{\displaystyle 3.70}

when an extra decimal place is required,

[ 3 ; 7 ]

{\displaystyle [3;7]}

may be represented as

[ 3 ; 7 , ∞ ]

{\displaystyle [3;7,\infty ]}

when an extra term is required.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the Scheme programming language

Source code in the scheme programming language

; Create a terminating Continued Fraction generator for the given rational number.
; Returns one term per call; returns #f when no more terms remaining.
(define make-continued-fraction-gen
  (lambda (rat)
    (let ((num (numerator rat)) (den (denominator rat)))
      (lambda ()
        (if (= den 0)
          #f
          (let ((ret (quotient num den))
                (rem (modulo num den)))
            (set! num den)
            (set! den rem)
            ret))))))

; Return the continued fraction representation of a rational number as a string.
(define rat->cf-string
  (lambda (rat)
    (let* ((cf (make-continued-fraction-gen rat))
           (str (string-append "[" (format "~a" (cf))))
           (sep ";"))
      (let loop ((term (cf)))
        (when term
          (set! str (string-append str (format "~a ~a" sep term)))
          (set! sep ",")
          (loop (cf))))
      (string-append str "]"))))

; Return the continued fraction representation of a rational number as a list of terms.
(define rat->cf-list
  (lambda (rat)
    (let ((cf (make-continued-fraction-gen rat))
          (lst '()))
      (let loop ((term (cf)))
        (when term
          (set! lst (append lst (list term)))
          (loop (cf))))
      lst)))


(printf "~%Basic examples:~%")
(for-each
  (lambda (rat)
    (printf "~a = ~a~%" rat (rat->cf-string rat))
    (printf "~a : ~a~%" rat (rat->cf-list rat)))
  '(1/2 3 23/8 13/11 22/7 -151/77 0))

(printf "~%Root2 approximations:~%")
(for-each
  (lambda (rat)
    (printf "~a = ~a~%" rat (rat->cf-string rat))
    (printf "~a : ~a~%" rat (rat->cf-list rat)))
  '(14142/10000 141421/100000 1414214/1000000 14142136/10000000 141421356237/100000000000))

(printf "~%Pi approximations:~%")
(for-each
  (lambda (rat)
    (printf "~a = ~a~%" rat (rat->cf-string rat))
    (printf "~a : ~a~%" rat (rat->cf-list rat)))
  '(31/10 314/100 3142/1000 31428/10000 314285/100000 3142857/1000000
    31428571/10000000 314285714/100000000 31415926535898/10000000000000))


(cond-expand
  (r7rs)
  (chicken (import (r7rs))))

(import (scheme base))
(import (scheme case-lambda))
(import (scheme write))
(import (srfi 41))

;;;-------------------------------------------------------------------

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; The entirety of r2cf, two different ways ;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; r2cf-VERSION1 works with integers. (Any floating-point number is
;; first converted to exact rational.)
(define (r2cf-VERSION1 fraction)
  (define-stream (recurs n d)
    (if (zero? d)
        stream-null
        (let-values (((q r) (floor/ n d)))
          (stream-cons q (recurs d r)))))
  (let ((fraction (exact fraction)))
    (recurs (numerator fraction) (denominator fraction))))

;; r2cf-VERSION2 works directly with fractions. (Any floating-point
;; number is first converted to exact rational.)
(define (r2cf-VERSION2 fraction)
  (define-stream (recurs fraction)
    (let* ((quotient (floor fraction))
           (remainder (- fraction quotient)))
      (stream-cons quotient (if (zero? remainder)
                                stream-null
                                (recurs (/ remainder))))))
  (recurs (exact fraction)))

;;(define r2cf r2cf-VERSION1)
(define r2cf r2cf-VERSION2)

;;;-------------------------------------------------------------------

(define *max-terms* (make-parameter 20))

(define cf2string
  (case-lambda
    ((cf) (cf2string cf (*max-terms*)))
    ((cf max-terms)
     (let loop ((i 0)
                (s "[")
                (strm cf))
       (if (stream-null? strm)
           (string-append s "]")
           (let ((term (stream-car strm))
                 (tail (stream-cdr strm)))
             (if (= i max-terms)
                 (string-append s ",...]")
                 (let ((separator (case i
                                    ((0) "")
                                    ((1) ";")
                                    (else ",")))
                       (term-str (number->string term)))
                   (loop (+ i 1)
                         (string-append s separator term-str)
                         tail)))))))))

(define (show fraction)
  (parameterize ((*max-terms* 1000))
    (display fraction)
    (display " => ")
    (display (cf2string (r2cf fraction)))
    (newline)))

(show 1/2)
(show 3)
(show 23/8)
(show 13/11)
(show 22/11)
(show -151/77)
(show 14142/10000)
(show 141421/100000)
(show 1414214/1000000)
(show 14142136/10000000)
(show 1414213562373095049/1000000000000000000)

;; Decimal expansion of sqrt(2): see https://oeis.org/A002193
(show 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)

(show 31/10)
(show 314/100)
(show 3142/1000)
(show 31428/10000)
(show 314285/100000)
(show 3142857/1000000)
(show 31428571/10000000)
(show 314285714/100000000)
(show 3142857142857143/1000000000000000)

;; Decimal expansion of pi: see https://oeis.org/A000796
(show 314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)


(cond-expand
  (r7rs)
  (chicken (import (r7rs))))

(import (scheme base))
(import (scheme write))

;;;-------------------------------------------------------------------

(define (r2cf fraction consumer)
  (let* ((fraction (exact fraction)))
    (let loop ((n (numerator fraction))
               (d (denominator fraction))
               (consumer consumer))
      (if (zero? d)
          (call-with-current-continuation
           (lambda (kont) (consumer #f kont)))
          (let-values (((q r) (floor/ n d)))
            (loop d r (call-with-current-continuation
                       (lambda (kont) (consumer q kont)))))))))

(define (display-cf term producer)
  (display "[")
  (let loop ((term term)
             (producer producer)
             (separator ""))
    (if term
        (begin
          (display separator)
          (display term)
          (let-values (((term producer)
                        (call-with-current-continuation producer)))
            (loop term producer
                  (if (string=? separator "") ";" ","))))
        (begin
          (display "]")
          (call-with-current-continuation producer)))))

;;;-------------------------------------------------------------------

(define (show fraction)
  (display fraction)
  (display " => ")
  (r2cf fraction display-cf)
  (newline))

(show 1/2)
(show 3)
(show 23/8)
(show 13/11)
(show 22/11)
(show -151/77)
(show 14142/10000)
(show 141421/100000)
(show 1414214/1000000)
(show 14142136/10000000)
(show 1414213562373095049/1000000000000000000)

;; Decimal expansion of sqrt(2): see https://oeis.org/A002193
(show 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)

(show 31/10)
(show 314/100)
(show 3142/1000)
(show 31428/10000)
(show 314285/100000)
(show 3142857/1000000)
(show 31428571/10000000)
(show 314285714/100000000)
(show 3142857142857143/1000000000000000)

;; Decimal expansion of pi: see https://oeis.org/A000796
(show 314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)

You may also check:How to resolve the algorithm Character codes step by step in the R programming language
You may also check:How to resolve the algorithm Read a file character by character/UTF8 step by step in the Raku programming language
You may also check:How to resolve the algorithm Text processing/2 step by step in the REXX programming language
You may also check:How to resolve the algorithm Rename a file step by step in the NewLISP programming language
You may also check:How to resolve the algorithm XML/Input step by step in the Python programming language

How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the Scheme programming language

Table of Contents

Problem Statement

Step by Step solution about How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the Scheme programming language

Source code in the scheme programming language