Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
No edit summary |
|||
Line 35: | Line 35: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
<lang cpp> |
<lang cpp> |
||
⚫ | |||
Contructor taking two intergers representing a rational number |
|||
int nextTerm returns the next term of the continued fraction |
|||
bool moreTerms returns true if ther are more terms |
|||
⚫ | |||
*/ |
|||
#include <iostream> |
#include <iostream> |
||
/* Interface for all Continued Fractions |
|||
⚫ | |||
*/ |
|||
class ContinuedFraction { |
class ContinuedFraction { |
||
private: |
private: |
||
⚫ | |||
public: |
public: |
||
virtual const int nextTerm(){}; |
|||
virtual const bool moreTerms(){}; |
|||
}; |
|||
/* Create a continued fraction from a rational number |
|||
Nigel Galloway, February 9th., 2013. |
|||
*/ |
|||
class r2cf : ContinuedFraction { |
|||
⚫ | |||
public: |
|||
r2cf(const int numerator, const int denominator) { |
|||
n1 = numerator; n2 = denominator; |
n1 = numerator; n2 = denominator; |
||
} |
} |
||
Line 56: | Line 59: | ||
return thisTerm; |
return thisTerm; |
||
} |
} |
||
const bool moreTerms() { |
const bool moreTerms() {return n2 > 0;} |
||
}; |
|||
return n2 > 0; |
|||
⚫ | |||
} |
|||
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> |
</lang> |
||
==Testing== |
===Testing=== |
||
===1/2 3 23/8 13/11 22/7=== |
====1/2 3 23/8 13/11 22/7==== |
||
<lang cpp> |
<lang cpp> |
||
int main() { |
int main() { |
||
for( |
for(r2cf n(1,2); n.moreTerms(); std::cout << n.nextTerm() << " "); |
||
std::cout << std::endl; |
std::cout << std::endl; |
||
for( |
for(r2cf n(3,1); n.moreTerms(); std::cout << n.nextTerm() << " "); |
||
std::cout << std::endl; |
std::cout << std::endl; |
||
for( |
for(r2cf n(23,8); n.moreTerms(); std::cout << n.nextTerm() << " "); |
||
std::cout << std::endl; |
std::cout << std::endl; |
||
for( |
for(r2cf n(13,11); n.moreTerms(); std::cout << n.nextTerm() << " "); |
||
std::cout << std::endl; |
std::cout << std::endl; |
||
for( |
for(r2cf n(22,7); n.moreTerms(); std::cout << n.nextTerm() << " "); |
||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
Line 79: | Line 89: | ||
</lang> |
</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
|||
⚫ | |||
0 2 |
|||
3 |
|||
2 1 7 |
|||
1 5 2 |
|||
3 7 |
|||
</pre> |
|||
⚫ | |||
<lang cpp> |
<lang cpp> |
||
int main() { |
int main() { |
||
int i = 0; |
|||
⚫ | |||
for(SQRT2 n; i++ < 20; std::cout << n.nextTerm() << " "); |
|||
std::cout << std::endl; |
std::cout << std::endl; |
||
for( |
for(r2cf n(14142,10000); n.moreTerms(); std::cout << n.nextTerm() << " "); |
||
std::cout << std::endl; |
|||
⚫ | |||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
Line 90: | Line 110: | ||
</lang> |
</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
|||
⚫ | |||
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 |
|||
</pre> |
|||
⚫ | |||
<lang cpp> |
<lang cpp> |
||
int main() { |
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> |
</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||
Straightforward implementation: |
Straightforward implementation: |
Revision as of 12:17, 9 February 2013
You are encouraged to solve this task according to the task description, using any language you may know.
To understand this task in context please see Continued fraction arithmetic
The purpose of this task is to write a function r2cf(int N1, int N2), or r2cf(Fraction N), which will output a continued fraction assuming:
- N1 is the numerator
- N2 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 N1 divided by N2. It then sets N1 to N2 and N2 to the determined remainder part. It then outputs the determined integer part. It does this until N2 is zero.
Demonstrate the function by outputing the continued fraction for:
- 1/2
- 3
- 23/8
- 13/11
- 22/7
should approach [1; 2, 2, 2, 2, ...] try ever closer rational approximations until bordom gets the better of you:
- 14142,10000
- 141421,100000
- 1414214,1000000
- 4142136,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 3.7 may be represented as 3.70 when an extra decimal place is required [3;7] may be represented as [3;7,] when an extra term is required.
C++
<lang cpp>
- include <iostream>
/* Interface for all Continued Fractions
Nigel Galloway, February 9th., 2013.
- /
class ContinuedFraction { private: public: virtual const int nextTerm(){}; virtual const bool moreTerms(){}; }; /* Create a continued fraction from a rational number
Nigel Galloway, February 9th., 2013.
- /
class r2cf : 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 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
<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; return 0; } </lang>
- Output:
0 2 3 2 1 7 1 5 2 3 7
<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
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>
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
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