Continued fraction/Arithmetic/Construct from rational number
To understand this task in context please see Continued fraction arithmetic
You are encouraged to solve this task according to the task description, using any language you may know.
The purpose of this task is to write a function , or , which will output a continued fraction assuming:
- is the numerator
- is the denominator
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 divided by . It then sets to and to the determined remainder part. It then outputs the determined integer part. It does this until is zero.
Demonstrate the function by outputing the continued fraction for:
- 1/2
- 3
- 23/8
- 13/11
- 22/7
- -151/77
should approach try ever closer rational approximations until bordom gets the better of you:
- 14142,10000
- 141421,100000
- 1414214,1000000
- 14142136,10000000
Try :
- 31,10
- 314,100
- 3142,1000
- 31428,10000
- 314285,100000
- 3142857,1000000
- 31428571,10000000
- 314285714,100000000
Observe how this rational number behaves differently to and convince yourself that, in the same way as may be represented as when an extra decimal place is required, may be represented as when an extra term is required.
C++
<lang cpp>#include <iostream> /* Interface for all Continued Fractions
Nigel Galloway, February 9th., 2013.
- /
class ContinuedFraction { public: virtual const int nextTerm(){}; virtual const bool moreTerms(){}; }; /* Create a continued fraction from a rational number
Nigel Galloway, February 9th., 2013.
- /
class r2cf : public ContinuedFraction { private: int n1, n2; public: r2cf(const int numerator, const int denominator): n1(numerator), n2(denominator){} const int nextTerm() { const int thisTerm = n1/n2; const int t2 = n2; n2 = n1 - thisTerm * n2; n1 = t2; return thisTerm; } const bool moreTerms() {return fabs(n2) > 0;} }; /* Generate a continued fraction for sqrt of 2
Nigel Galloway, February 9th., 2013.
- /
class SQRT2 : public ContinuedFraction { private: bool first=true; public: const int nextTerm() {if (first) {first = false; return 1;} else return 2;} const bool moreTerms() {return true;} };</lang>
Testing
1/2 3 23/8 13/11 22/7 -151/77
<lang cpp>int main() { for(r2cf n(1,2); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(3,1); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(23,8); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(13,11); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(22,7); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf cf(-151,77); cf.moreTerms(); std::cout << cf.nextTerm() << " "); std::cout << std::endl; return 0; }</lang>
- Output:
0 2 3 2 1 7 1 5 2 3 7 -1 -1 -24 -1 -2
<lang cpp>int main() { int i = 0; for(SQRT2 n; i++ < 20; std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(14142,10000); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(14142136,10000000); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; return 0; }</lang>
- Output:
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 1 29 1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2
Real approximations of a rational number
<lang cpp>int main() {
for(r2cf n(31,10); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(314,100); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(3142,1000); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(31428,10000); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(314285,100000); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(3142857,1000000); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(31428571,10000000); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(314285714,100000000); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; return 0;
}</lang>
- Output:
3 10 3 7 7 3 7 23 1 2 3 7 357 3 7 2857 3 7 142857 3 7 476190 3 3 7 7142857
Mathematica
Mathematica has a build-in function ContinuedFraction. <lang mathematica>ContinuedFraction[1/2] ContinuedFraction[3] ContinuedFraction[23/8] ContinuedFraction[13/11] ContinuedFraction[22/7] ContinuedFraction[-151/77] ContinuedFraction[14142/10000] ContinuedFraction[141421/100000] ContinuedFraction[1414214/1000000] ContinuedFraction[14142136/10000000]</lang>
- Output:
{0, 2} {3} {2, 1, 7} {1, 5, 2} {3, 7} {-1, -1, -24, -1, -2} {1, 2, 2, 2, 2, 2, 1, 1, 29} {1, 2, 2, 2, 2, 2, 2, 3, 1, 1, 3, 1, 7, 2} {1, 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12} {1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2}
Perl 6
Straightforward implementation: <lang perl6>sub r2cf(Rat $x is copy) {
gather loop {
$x -= take $x.floor; last unless $x > 0; $x = 1 / $x;
}
}
say r2cf(.Rat) for <1/2 3 23/8 13/11 22/7 1.41 1.4142136>;</lang>
- Output:
0 2 3 2 1 7 1 5 2 3 7 1 2 2 3 1 1 2 1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2
As a silly one-liner: <lang perl6>sub r2cf(Rat $x is copy) { gather $x [R/]= 1 while ($x -= take $x.floor) > 0 }</lang>
Python
<lang python>def r2cf(n1,n2):
while n2: n1, (t1, n2) = n2, divmod(n1, n2) yield t1
print(list(r2cf(1,2))) # => [0, 2] print(list(r2cf(3,1))) # => [3] print(list(r2cf(23,8))) # => [2, 1, 7] print(list(r2cf(13,11))) # => [1, 5, 2] print(list(r2cf(22,7))) # => [3, 7] print(list(r2cf(14142,10000))) # => [1, 2, 2, 2, 2, 2, 1, 1, 29] print(list(r2cf(141421,100000))) # => [1, 2, 2, 2, 2, 2, 2, 3, 1, 1, 3, 1, 7, 2] print(list(r2cf(1414214,1000000))) # => [1, 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12] print(list(r2cf(14142136,10000000))) # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2]</lang> This version generates it from any real number (with rationals as a special case): <lang python>def real2cf(x):
while True: t1, f = divmod(x, 1) yield int(t1) if not f: break x = 1/f
from fractions import Fraction from itertools import islice
print(list(real2cf(Fraction(13, 11)))) # => [1, 5, 2] print(list(islice(real2cf(2 ** 0.5), 20))) # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]</lang>
REXX
Programming notes:
The numeric digits can be increased to a higher value to generate more terms. Two subroutines sqrt & pi were included here to demonstrate terms for √2 and π. The subroutine $maxfact was included and is only needed if the number used for r2cf is a decimal fraction. Checks were included to verify that the arguments being passed to r2cf are indeed numeric and also not zero. This version handles negative numbers. <lang rexx>/*REXX pgm converts decimal or rational fraction to a continued fraction*/ numeric digits 230 /*this determines how many terms */
/*can be generated for dec fracts*/
say ' 1/2 ──► CF: ' r2cf( '1/2' ) say ' 3 ──► CF: ' r2cf( 3 ) say ' 23/8 ──► CF: ' r2cf( '23/8' ) say ' 13/11 ──► CF: ' r2cf( '13/11' ) say ' 22/7 ──► CF: ' r2cf( '22/7 ' ) say say '───────── attempts at √2.' say '14142/1e4 ──► CF: ' r2cf( '14142/1e4 ' ) say '141421/1e5 ──► CF: ' r2cf( '141421/1e5 ' ) say '1414214/1e6 ──► CF: ' r2cf( '1414214/1e6 ' ) say '14142136/1e7 ──► CF: ' r2cf( '14142136/1e7 ' ) say '141421356/1e8 ──► CF: ' r2cf( '141421356/1e8 ' ) say '1414213562/1e9 ──► CF: ' r2cf( '1414213562/1e9 ' ) say '14142135624/1e10 ──► CF: ' r2cf( '14142135624/1e10 ' ) say '141421356237/1e11 ──► CF: ' r2cf( '141421356237/1e11 ' ) say '1414213562373/1e12 ──► CF: ' r2cf( '1414213562373/1e12 ' ) say '√2 ──► CF: ' r2cf( sqrt(2) ) say say '───────── an attempt at π' say 'π ──► CF: ' r2cf( pi() ) exit /*stick a fork in it, we're done.*/ /*────────────────────────────────R2CF subroutine───────────────────────*/ r2cf: procedure; parse arg g 1 s 2; $=; if s=='-' then g = substr(g,2)
else s =
if pos('.',g)\==0 then do
if \datatype(g,'N') then call serr 'not numeric:' g g = $maxfact(g) end
if pos('/',g)==0 then g = g"/"1 parse var g n '/' d if \datatype(n,'W') then call serr "a numerator isn't an integer:" n if \datatype(d,'W') then call serr "a denominator isn't an integer:" d n = abs(n) /*ensure numerator is positive. */ if d=0 then call serr 'a denominator is zero'
do while d\==0 /*where the rubber meets the road*/ $ = $ s || (n%d) /*append another number to list. */ _ = d d = n // d /* % is int div, // is modulus.*/ n = _ end /*while*/
return strip($) /*─────────────────────────────PI subroutine────────────────────────────*/ pi: return, /*a bit of overkill, but hey !! */ 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271
/* ··· should ≥ NUMERIC DIGITS */
/*─────────────────────────────SERR subroutine──────────────────────────*/ serr: say; say '***error!***'; say; say arg(1); say; exit /*─────────────────────────────SQRT subroutine──────────────────────────*/ sqrt: procedure; parse arg x; if x=0 then return 0; d=digits();numeric digits 11
g=.sqrtGuess(); do j=0 while p>9; m.j=p; p=p%2+1; end do k=j+5 to 0 by -1; if m.k>11 then numeric digits m.k; g=.5*(g+x/g); end numeric digits d; return g/1
.sqrtGuess: if x<0 then call sqrtErr; numeric form; m.=11; p=d+d%4+2
parse value format(x,2,1,,0) 'E0' with g 'E' _ .; return g*.5'E'_%2
/*─────────────────────────────MAXFACT subroutine───────────────────────*/ $maxFact: procedure; parse arg x 1 _x,y; y=10**(digits()-1); b=0; h=1 a=1; g=0; do while a<=y & g<=y; n=trunc(_x); _=a; a=n*a+b; b=_; _=g g=n*g+h; h=_; if n=_x | a/g=x then do; if a>y | g>y then iterate; b=a h=g; leave; end; _x=1/(_x-n); end; return b'/'h</lang>
- Output:
1/2 ──► CF: 0 2 3 ──► CF: 3 23/8 ──► CF: 2 1 7 13/11 ──► CF: 1 5 2 22/7 ──► CF: 3 7 ───────── attempts at √2. 14142/1e4 ──► CF: 1 2 2 2 2 2 1 1 29 141421/1e5 ──► CF: 1 2 2 2 2 2 2 3 1 1 3 1 7 2 1414214/1e6 ──► CF: 1 2 2 2 2 2 2 2 3 6 1 2 1 12 14142136/1e7 ──► CF: 1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2 141421356/1e8 ──► CF: 1 2 2 2 2 2 2 2 2 2 2 3 4 1 1 2 6 8 1414213562/1e9 ──► CF: 1 2 2 2 2 2 2 2 2 2 2 2 1 1 14 1 238 1 3 14142135624/1e10 ──► CF: 1 2 2 2 2 2 2 2 2 2 2 2 2 2 5 4 1 8 4 2 1 4 141421356237/1e11 ──► CF: 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 1 4 1 2 1 63 2 1 1 1 4 2 1414213562373/1e12 ──► CF: 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 1 11 2 3 2 1 1 1 25 1 2 3 √2 ──► CF: 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 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 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 3 ───────── an attempt at π π ──► CF: 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 5 4 1 2 2 8 1 5 2 2 26 1 4 1 1 8 2 42 2 1 7 3 3 1 1 7 2 4 9 7 2 3 1 57 1 18 1 9 19 1 2 18 1 3 7 30 1 1 1 3 3 3 1 2 8 1 1 2 1 15 1 2 13 1 2 1 4 1 12 1 1 3 3 28 1 10 3 2 20 1 1 1 1 4 1 1 1 5 3 2 1 6 1 4 1 120 2 1 1 3 1 23 1 15 1 3 7 1 16 1 2 1 21 2 1 1 2 9 1 6 4
Ruby
<lang ruby>=begin
Generate a continued fraction from a rational number
Nigel Galloway, February 4th., 2013
=end def r2cf(n1,n2)
while n2 > 0 t1 = n1/n2; t2 = n2; n2 = n1 - t1 * n2; n1 = t2; yield t1 end
end</lang>
Testing
1/2 <lang ruby>r2cf(1,2) {|n| print "#{n} "}</lang>
- Output:
0 2
3
<lang ruby>r2cf(3,1) {|n| print "#{n} "}</lang>
- Output:
3
23/8 <lang ruby>r2cf(23,8) {|n| print "#{n} "}</lang>
- Output:
2 1 7
13/11 <lang ruby>r2cf(13,11) {|n| print "#{n} "}</lang>
- Output:
1 5 2
22/7 <lang ruby>r2cf(22,7) {|n| print "#{n} "}</lang>
- Output:
3 7
1.4142 <lang ruby>r2cf(14142,10000) {|n| print "#{n} "}</lang>
- Output:
1 2 2 2 2 2 1 1 29
1.4142 <lang ruby>r2cf(141421,100000) {|n| print "#{n} "}</lang>
- Output:
1 2 2 2 2 2 2 3 1 1 3 1 7 2
1.414214 <lang ruby>r2cf(1414214,1000000) {|n| print "#{n} "}</lang>
- Output:
1 2 2 2 2 2 2 2 3 6 1 2 1 12
1.4142136 <lang ruby>r2cf(14142136,10000000) {|n| print "#{n} "}</lang>
- Output:
1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2
Tcl
<lang tcl>package require Tcl 8.6
proc r2cf {n1 {n2 1}} {
if {$n1 != int($n1) && [regexp {\.(\d+)} $n1 -> suffix]} {
set pow [string length $suffix] set n1 [expr {int($n1 * 10**$pow)}] set n2 [expr {$n2 * 10**$pow}]
} coroutine cf#[incr ::cfcounter] apply {{n1 n2} {
yield [info coroutine] while {$n2 > 0} { yield [expr {$n1 / $n2}] set n2 [expr {$n1 % [set n1 $n2]}] } return -code break
}} $n1 $n2
}</lang> Demonstrating: <lang tcl>foreach {n1 n2} {
1 2 3 1 23 8 13 11 22 7 -151 77 14142 10000 141421 100000 1414214 1000000 14142136 10000000 31 10 314 100 3142 1000 31428 10000 314285 100000 3142857 1000000 31428571 10000000 314285714 100000000 3141592653589793 1000000000000000
} {
puts -nonewline "\[$n1;$n2\] -> " set cf [r2cf $n1 $n2] while 1 {puts -nonewline [$cf],};puts "\b "
}</lang>
- Output:
[1;2] -> 0,2 [3;1] -> 3 [23;8] -> 2,1,7 [13;11] -> 1,5,2 [22;7] -> 3,7 [-151;77] -> -2,25,1,2 [14142;10000] -> 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 [1414214;1000000] -> 1,2,2,2,2,2,2,2,3,6,1,2,1,12 [14142136;10000000] -> 1,2,2,2,2,2,2,2,2,2,6,1,2,4,1,1,2 [31;10] -> 3,10 [314;100] -> 3,7,7 [3142;1000] -> 3,7,23,1,2 [31428;10000] -> 3,7,357 [314285;100000] -> 3,7,2857 [3142857;1000000] -> 3,7,142857 [31428571;10000000] -> 3,7,476190,3 [314285714;100000000] -> 3,7,7142857 [3141592653589793;1000000000000000] -> 3,7,15,1,292,1,1,1,2,1,3,1,14,4,2,3,1,12,5,1,5,20,1,11,1,1,1,2
XPL0
<lang XPL0>include c:\cxpl\codes; real Val;
proc R2CF(N1, N2, Lev); \Output continued fraction for N1/N2 int N1, N2, Lev; int Quot, Rem; [if Lev=0 then Val:= 0.0; Quot:= N1/N2; Rem:= rem(0); IntOut(0, Quot); if Rem then [ChOut(0, if Lev then ^, else ^;); R2CF(N2, Rem, Lev+1)]; Val:= Val + float(Quot); \generate value from continued fraction if Lev then Val:= 1.0/Val; ];
int I, Data; [Data:= [1,2, 3,1, 23,8, 13,11, 22,7, 0]; Format(0, 15); I:= 0; while Data(I) do
[IntOut(0, Data(I)); ChOut(0, ^/); IntOut(0, Data(I+1)); ChOut(0, 9\tab\); ChOut(0, ^[); R2CF(Data(I), Data(I+1), 0); ChOut(0, ^]); ChOut(0, 9\tab\); RlOut(0, Val); CrLf(0); I:= I+2];
]</lang>
- Output:
1/2 [0;2] 5.000000000000000E-001 3/1 [3] 3.000000000000000E+000 23/8 [2;1,7] 2.875000000000000E+000 13/11 [1;5,2] 1.181818181818180E+000 22/7 [3;7] 3.142857142857140E+000