Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Continued fraction/Arithmetic/Construct from rational number (view source)
Revision as of 20:26, 28 February 2023
, 1 year ago→Using SRFI-41 streams (lazy lists)
Line 4,411:
Due to the use of a lazy list, the terms are memoized in a manner suitable for sequential access again and again.
(
<syntaxhighlight lang="scheme">
Line 4,540:
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>
===Using ''call-with-current-continuation'' to implement coroutines===
{{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''' egg.
This implementation employs coroutines. The '''r2cf''' procedure is passed not only a number to convert to a continued fraction, but also a "consumer" of the terms. In this case, the consumer is '''display-cf''', which prints the terms nicely.
(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 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 (return)
(call-with-values (lambda () (values return #f))
consumer)))
(let-values (((q r) (floor/ n d)))
(loop d r (call-with-current-continuation
(lambda (return)
(call-with-values (lambda ()
(values return q))
consumer)))))))))
(define (display-cf producer term)
(display "[")
(let loop ((producer producer)
(term term)
(separator ""))
(if term
(begin
(display separator)
(display term)
(let-values (((producer term)
(call-with-current-continuation producer)))
(loop producer term
(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)
</syntaxhighlight>
{{out}}
<pre>$ gosh continued-fraction-from-rational-callcc.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>
=={{header|Sidef}}==
| |||