Continued fraction/Arithmetic/Construct from rational number: Difference between revisions

===Using a closure to generate terms===

===Using SRFI-41 streams (lazy lists)===

{{trans|Haskell}}

{{works with|Gauche Scheme|0.9.12}}

{{works with|Chibi Scheme|0.10.0}}

{{works with|CHICKEN Scheme|5.3.0}}

This is for R7RS Scheme. Modify as necessary, for your Scheme. For CHICKEN, you will need the '''r7rs''' and '''srfi-41''' eggs.

Due to the use of a lazy list, the terms are memoized in a manner suitable for sequential access again and again.

(Note that for -151/77 the solution here is for floor division. You will get a different solution if you round the fraction differently.)

<syntaxhighlight lang="scheme">

(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)

</syntaxhighlight>

{{out}}

<pre>$ gosh continued-fraction-from-rational-srfi41.scm

1/2 => [0;2]

3 => [3]

23/8 => [2;1,7]

13/11 => [1;5,2]

2 => [2]

-151/77 => [-2;25,1,2]

7071/5000 => [1;2,2,2,2,2,1,1,29]

141421/100000 => [1;2,2,2,2,2,2,3,1,1,3,1,7,2]

707107/500000 => [1;2,2,2,2,2,2,2,3,6,1,2,1,12]

1767767/1250000 => [1;2,2,2,2,2,2,2,2,2,6,1,2,4,1,1,2]

1414213562373095049/1000000000000000000 => [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,39,1,5,1,3,61,1,1,8,1,2,1,7,1,1,6]

141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,5,1,8,3,1,2,2,1,6,2,2,3,1,2,3,1,1,39,1,3,1,2,4,10,1,6,1,30,5,2,1,1,1,1,1,32,1,4,18,124,3,2,1,1,8,1,1,1,6,15,2,3,2,7,1,4,9,2,7,1,1,1,1,1,2,1,10,1,31,5,1,1,1,7,1,14,10,3,11,1,2,1,65,4,9,2,3,2,2,9,1,1,2,1,1,2]

31/10 => [3;10]

157/50 => [3;7,7]

1571/500 => [3;7,23,1,2]

7857/2500 => [3;7,357]

62857/20000 => [3;7,2857]

3142857/1000000 => [3;7,142857]

31428571/10000000 => [3;7,476190,3]

157142857/50000000 => [3;7,7142857]

3142857142857143/1000000000000000 => [3;6,1,142857142857142]

157079632679489661923132169163975144209858469968755291048747229615390820314310449931401741267105853399107/50000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [3;7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,2,1,1,15,3,13,1,4,2,6,6,99,1,2,2,6,3,5,1,1,6,8,1,7,1,2,3,7,1,2,1,1,12,1,1,1,3,1,1,8,1,1,2,1,6,1,1,5,2,2,3,1,2,4,4,16,1,161,45,1,22,1,2,2,1,4,1,2,24,1,2,1,3,1,2,1,1,10,2,8,2,1,4,1,1,2,3,6,8,1,1,1,7,1,1,1,1,21,1,2,1,2,1,1,21,1,6,1,2,2,1,1,2,5,2,3,2,9,3,3,2,2,1,1,3,7,3,1,8,36,20,6,17,15,1,2,5,1,4,9,6,26,1,1,1,7,1,79,4,1,1,10,4,5,1,1,55,8,1,4,4,10,5,3,1,2,6,1,2,1,1,2,1,20,3,1,1,2,3]</pre>