How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the ALGOL 68 programming language
How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the ALGOL 68 programming language
Table of Contents
Problem Statement
The purpose of this task is to write a function
r 2 c f
(
i n t
{\displaystyle {\mathit {r2cf}}(\mathrm {int} }
N
1
,
i n t
{\displaystyle N_{1},\mathrm {int} }
N
2
)
{\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
N
1
{\displaystyle N_{1}}
divided by
N
2
{\displaystyle N_{2}}
. It then sets
N
1
{\displaystyle N_{1}}
to
N
2
{\displaystyle N_{2}}
and
N
2
{\displaystyle N_{2}}
to the determined remainder part. It then outputs the determined integer part. It does this until
a b s
(
N
2
)
{\displaystyle \mathrm {abs} (N_{2})}
is zero. Demonstrate the function by outputing the continued fraction for:
2
{\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
2
{\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 ALGOL 68 programming language
Source code in the algol programming language
BEGIN # construct continued fraction representations of rational numbers #
# Translated from the C sample #
# Uses code from the Arithmetic/Rational task #
# Code from the Arithmetic/Rational task #
# ============================================================== #
MODE FRAC = STRUCT( INT num #erator#, den #ominator#);
PROC gcd = (INT a, b) INT: # greatest common divisor #
(a = 0 | b |: b = 0 | a |: ABS a > ABS b | gcd(b, a MOD b) | gcd(a, b MOD a));
PROC lcm = (INT a, b)INT: # least common multiple #
a OVER gcd(a, b) * b;
PRIO // = 9; # higher then the ** operator #
OP // = (INT num, den)FRAC: ( # initialise and normalise #
INT common = gcd(num, den);
IF den < 0 THEN
( -num OVER common, -den OVER common)
ELSE
( num OVER common, den OVER common)
FI
);
OP + = (FRAC a, b)FRAC: (
INT common = lcm(den OF a, den OF b);
FRAC result := ( common OVER den OF a * num OF a + common OVER den OF b * num OF b, common );
num OF result//den OF result
);
OP - = (FRAC a, b)FRAC: a + -b,
* = (FRAC a, b)FRAC: (
INT num = num OF a * num OF b,
den = den OF a * den OF b;
INT common = gcd(num, den);
(num OVER common) // (den OVER common)
);
OP - = (FRAC frac)FRAC: (-num OF frac, den OF frac);
# ============================================================== #
# end code from the Arithmetic/Rational task #
[]FRAC examples = ( 1//2, 3//1, 23//8, 13//11, 22//7, -151//77 );
[]FRAC sqrt2 = ( 14142//10000, 141421//100000, 1414214//1000000, 14142136//10000000 );
[]FRAC pi = ( 31//10, 314//100, 3142//1000, 31428//10000
, 314285//100000, 3142857//1000000, 31428571//10000000, 314285714//100000000
);
# returns the quotient of numerator over denominator and sets #
# numerator and denominator to the next values for #
# the continued fraction #
PROC r2cf = ( REF INT numerator, REF INT denominator )INT:
IF denominator = 0
THEN 0
ELSE INT quotient := numerator OVER denominator;
INT prev numerator = numerator;
numerator := denominator;
denominator := prev numerator MOD denominator;
quotient
FI # r2cf # ;
# shows the continued fractions for the elements of f seq #
PROC show r2cf = ( STRING legend, []FRAC f seq )VOID:
BEGIN
print( ( legend ) );
FOR i FROM LWB f seq TO UPB f seq DO
INT num := num OF f seq[ i ];
INT den := den OF f seq[ i ];
print( ( newline, "For N = ", whole( num , 0 ), ", D = ", whole( den , 0 ), " :" ) );
WHILE den /= 0 DO
print( ( " ", whole( r2cf( num, den ), 0 ) ) )
OD
OD
END # show r2cf # ;
BEGIN # task #
show r2cf( "Running the examples :", examples );
print( ( newline, newline ) );
show r2cf( "Running for root2 :", sqrt2 );
print( ( newline, newline ) );
show r2cf( "Running for pi :", pi )
END
END
You may also check:How to resolve the algorithm Substring step by step in the RPG programming language
You may also check:How to resolve the algorithm Execute a Markov algorithm step by step in the Swift programming language
You may also check:How to resolve the algorithm Sleep step by step in the Pixilang programming language
You may also check:How to resolve the algorithm Range extraction step by step in the Swift programming language
You may also check:How to resolve the algorithm A+B step by step in the AutoHotkey programming language