Continued fraction convergents: Difference between revisions
(Corrected the sequence for the golden ratio in the task description.) |
(Added Wren) |
||
Line 12: | Line 12: | ||
A simple check is to do this for the golden ratio <math>\frac{\sqrt{5}+1}{2}</math>, that is, <math>a=5, b=1, m = 1, n = 2 </math>, which should output <math>(1,1), (2,1), (3,2), (5,3), (8,5), \dots</math>. |
A simple check is to do this for the golden ratio <math>\frac{\sqrt{5}+1}{2}</math>, that is, <math>a=5, b=1, m = 1, n = 2 </math>, which should output <math>(1,1), (2,1), (3,2), (5,3), (8,5), \dots</math>. |
||
=={{header|Wren}}== |
|||
{{libheader|Wren-rat}} |
|||
Well, the task seems reasonably clear now to me. |
|||
The following is loosely based on the Python code [https://leancrew.com/all-this/2023/08/continued-fractions-in-python/ here]. If a large number of terms were required for quadratic real numbers, then one might need to use 'arbitrary precision' arithmetic to avoid round-off errors when converting between floats and rationals. |
|||
<syntaxhighlight lang="wren">import "./rat" for Rat |
|||
var cfcRat = Fn.new { |m, n| |
|||
var p = [0, 1] |
|||
var q = [1, 0] |
|||
var s = [] |
|||
var r = Rat.new(m, n) |
|||
var rem = r |
|||
while (true) { |
|||
var whole = rem.truncate |
|||
var frac = rem.fraction |
|||
var pn = whole * p[-1] + p[-2] |
|||
var qn = whole * q[-1] + q[-2] |
|||
var sn = pn / qn |
|||
p.add(pn) |
|||
q.add(qn) |
|||
s.add(sn) |
|||
if (r == sn) break |
|||
rem = frac.inverse |
|||
} |
|||
return s |
|||
} |
|||
var cfcQuad = Fn.new { |a, b, m, n, k| |
|||
var p = [0, 1] |
|||
var q = [1, 0] |
|||
var s = [] |
|||
var r = (a.sqrt * b + m) / n |
|||
var rem = r |
|||
for (i in 1..k) { |
|||
var whole = rem.truncate |
|||
var frac = rem.fraction |
|||
var pn = whole * p[-1] + p[-2] |
|||
var qn = whole * q[-1] + q[-2] |
|||
var sn = Rat.new(pn, qn) |
|||
p.add(pn) |
|||
q.add(qn) |
|||
s.add(sn) |
|||
rem = 1 / frac |
|||
} |
|||
return s |
|||
} |
|||
System.print("The continued fraction convergents for the following (maximum 8 terms) are:") |
|||
System.print("415/93 = %(cfcRat.call(415, 93))") |
|||
System.print("649/200 = %(cfcRat.call(649, 200))") |
|||
System.print("√2 = %(cfcQuad.call(2, 1, 0, 1, 8))") |
|||
System.print("√5 = %(cfcQuad.call(5, 1, 0, 1, 8))") |
|||
System.print("phi = %(cfcQuad.call(5, 1, 1, 2, 8))")</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The continued fraction convergents for the following (maximum 8 terms) are: |
|||
415/93 = [4/1, 9/2, 58/13, 415/93] |
|||
649/200 = [3/1, 13/4, 159/49, 649/200] |
|||
√2 = [1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408] |
|||
√5 = [2/1, 9/4, 38/17, 161/72, 682/305, 2889/1292, 12238/5473, 51841/23184] |
|||
phi = [1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21] |
|||
</pre> |
Revision as of 12:28, 5 February 2024
Given a positive real number, if we truncate its continued fraction representation at a certain depth, we obtain a rational approximation to the real number. The sequence of successively better such approximations is its convergent sequence.
Problem:
- Given a positive rational number , specified by two positive integers , output its entire sequence of convergents.
- Given a quadratic real number , specified by integers , where is not a perfect square, output the first convergents when given a positive number .
The output format can be whatever is necessary to represent rational numbers, but it probably should be a 2-tuple of integers.
For example, given , since
A simple check is to do this for the golden ratio , that is, , which should output .
Wren
Well, the task seems reasonably clear now to me.
The following is loosely based on the Python code here. If a large number of terms were required for quadratic real numbers, then one might need to use 'arbitrary precision' arithmetic to avoid round-off errors when converting between floats and rationals.
import "./rat" for Rat
var cfcRat = Fn.new { |m, n|
var p = [0, 1]
var q = [1, 0]
var s = []
var r = Rat.new(m, n)
var rem = r
while (true) {
var whole = rem.truncate
var frac = rem.fraction
var pn = whole * p[-1] + p[-2]
var qn = whole * q[-1] + q[-2]
var sn = pn / qn
p.add(pn)
q.add(qn)
s.add(sn)
if (r == sn) break
rem = frac.inverse
}
return s
}
var cfcQuad = Fn.new { |a, b, m, n, k|
var p = [0, 1]
var q = [1, 0]
var s = []
var r = (a.sqrt * b + m) / n
var rem = r
for (i in 1..k) {
var whole = rem.truncate
var frac = rem.fraction
var pn = whole * p[-1] + p[-2]
var qn = whole * q[-1] + q[-2]
var sn = Rat.new(pn, qn)
p.add(pn)
q.add(qn)
s.add(sn)
rem = 1 / frac
}
return s
}
System.print("The continued fraction convergents for the following (maximum 8 terms) are:")
System.print("415/93 = %(cfcRat.call(415, 93))")
System.print("649/200 = %(cfcRat.call(649, 200))")
System.print("√2 = %(cfcQuad.call(2, 1, 0, 1, 8))")
System.print("√5 = %(cfcQuad.call(5, 1, 0, 1, 8))")
System.print("phi = %(cfcQuad.call(5, 1, 1, 2, 8))")
- Output:
The continued fraction convergents for the following (maximum 8 terms) are: 415/93 = [4/1, 9/2, 58/13, 415/93] 649/200 = [3/1, 13/4, 159/49, 649/200] √2 = [1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408] √5 = [2/1, 9/4, 38/17, 161/72, 682/305, 2889/1292, 12238/5473, 51841/23184] phi = [1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21]