Talk:Continued fraction convergents

From Rosetta Code

Clarify task

Where do a, b, m, n fit in with all this? (In particular you lost me at the word "since".) Please remember that continued fractions are an obscure mathematical curiosity from the 15th century that most normal people are not familiar with. The output for the golden ratio is not "the fibonacci series" but (I believe) it would instead be 1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, etc. Petelomax (talk) 07:29, 1 February 2024 (UTC)

Well I take a bit of an exception to "an obscure mathematical curiosity from the 15th century" I'll just quote from https://www.scirp.org/journal/paperinformation?paperid=114756 "Continued fractions constitute a very important subject in mathematics. Their importance lies in the fact that they have very interesting and beautiful applications in many fields in pure and applied sciences. This review article will reveal some of these applications and will reflect the beauty behind their uses in calculating roots of real numbers, getting solutions of algebraic Equations of the second degree, and their uses in solving special ordinary differential Equations such as Legendre, Hermite, and Laguerre Equations; moreover and most important, their use in physics in solving Schrodinger Equation for a certain potential. A comparison will also be given between the results obtained via continued fractions and those obtained through the use of well-known numerical methods. Advances in the subject will be discussed at the end of this review article". My main objection is that the task references continued fraction if I look at the F# output for that task for √2 it is:
1.40000000000000 < √2 < 1.50000000000000
1.40000000000000 < √2 < 1.41666666666667
1.41379310344828 < √2 < 1.41666666666667
1.41379310344828 < √2 < 1.41428571428571
1.41420118343195 < √2 < 1.41428571428571
1.41420118343195 < √2 < 1.41421568627451
1.41421319796954 < √2 < 1.41421568627451
1.41421319796954 < √2 < 1.41421362489487
1.41421355164605 < √2 < 1.41421362489487

1.50000000000000 is (3,2), 1.40000000000000 is (7,5), 1.41666666666667 is (17,12) or (17/12) as the representation changes halfway through the description. continued fraction uses floating point representation and does not specifically require that ever convergent is output, this is a duplicate task in the sense that all is required is to modify the code for continued fraction to a new output format--Nigel Galloway (talk) 13:19, 1 February 2024 (UTC)

Fair point, I'll concede they are very important to mathematicians, just not mere mortals. To the best of my recollection they were not mentioned at all during the ten or so years I attended maths lessons/lectures. It strikes me the continued fraction task can deal with several things that a,b,m,n cannot. As the task description stands, the best I could do would be to create an IEEE 754 float with all the inaccuracies that implies (even if I tell gmp to do 50,000 dp) and convert that to an approximate cf, which even to my limited understanding seems somewhat backwards. Should there be a more direct way to convert a,b,m,n to a continued fraction, I cannot find it, not even in the continued fraction task. --Petelomax (talk) 14:43, 1 February 2024 (UTC)
PS: this task also appears to be a pre-requisite for Sturmian word, at least for properly completed submissions (of which none yet are).
let Q = ((sqrt 5)-1)/2 (Q=0.6180339887498948) then 2Q+1=sqrt 5. Using continued fraction for sqrt 5
cfSqRt 5M |> Seq.take 10 |> Seq.pairwise |> Seq.iter(fun(n,g)->printfn "%1.14f < √5 < %1.14f" (min n g) (max n g))

produces

2.00000000000000 < √5 < 3.00000000000000
2.00000000000000 < √5 < 2.33333333333333
2.20000000000000 < √5 < 2.33333333333333
2.20000000000000 < √5 < 2.25000000000000
2.23076923076923 < √5 < 2.25000000000000
2.23076923076923 < √5 < 2.23809523809524
2.23529411764706 < √5 < 2.23809523809524
2.23529411764706 < √5 < 2.23636363636364
2.23595505617978 < √5 < 2.23636363636364

modifying to produce Q:

cfSqRt 5M |> Seq.take 10 |> Seq.pairwise |> Seq.iter(fun(n,g)->printfn "%1.14f < Q < %1.14f" (((min n g)-1.0M)/2.0M) (((max n g)-1.0M)/2.0M))

produces

0.50000000000000 < Q < 1.00000000000000
0.50000000000000 < Q < 0.66666666666667
0.60000000000000 < Q < 0.66666666666667
0.60000000000000 < Q < 0.62500000000000
0.61538461538462 < Q < 0.62500000000000
0.61538461538462 < Q < 0.61904761904762
0.61764705882353 < Q < 0.61904761904762
0.61764705882353 < Q < 0.61818181818182
0.61797752808989 < Q < 0.61818181818182

and in general (nQ-m)/b = sqrt a. Here Q is not the golden ratio (ϕ) which is ((sqrt 5)+1)/2 modifying to produce ϕ:

cfSqRt 5M |> Seq.take 10 |> Seq.pairwise |> Seq.iter(fun(n,g)->printfn "%1.14f < ϕ < %1.14f" (((min n g)+1.0M)/2.0M) (((max n g)+1.0M)/2.0M))

produces

1.50000000000000 < ϕ < 2.00000000000000
1.50000000000000 < ϕ < 1.66666666666667
1.60000000000000 < ϕ < 1.66666666666667
1.60000000000000 < ϕ < 1.62500000000000
1.61538461538462 < ϕ < 1.62500000000000
1.61538461538462 < ϕ < 1.61904761904762
1.61764705882353 < ϕ < 1.61904761904762
1.61764705882353 < ϕ < 1.61818181818182
1.61797752808989 < ϕ < 1.61818181818182

it is well known that the continued fraction for ϕ is [1;1,1,1,...] using continued fraction to calculate this:

let ()=fun _->1M
let ()=fun _->1M
cf2S (()) (()) |> Seq.take 10 |> Seq.pairwise |> Seq.iter(fun(n,g)->printfn "%1.14f < ϕ < %1.14f" (min n g) (max n g))

produces

1.50000000000000 < ϕ < 2.00000000000000
1.50000000000000 < ϕ < 1.66666666666667
1.60000000000000 < ϕ < 1.66666666666667
1.60000000000000 < ϕ < 1.62500000000000
1.61538461538462 < ϕ < 1.62500000000000
1.61538461538462 < ϕ < 1.61904761904762
1.61764705882353 < ϕ < 1.61904761904762
1.61764705882353 < ϕ < 1.61818181818182
1.61797752808989 < ϕ < 1.61818181818182

--Nigel Galloway (talk) 16:42, 2 February 2024 (UTC)

OK, the penny is slowly dropping. Not sure it is really worth saying this but only the F# (which I long gave up any hope of ever being able to read) and REXX (which is 1000 times easier, so still quite hard) have a generalised square root routine, and it started to make sense on the latter, specifically the cf for sqrt(5) is [2; 4, 4, 4, ...], which I obviously didn't know. The other 73 entries on that page do not have such a routine. Anyway, I'll just translate the Wren entry, remove the clarification tag now that we've got some actual examples, and won't bother to complain should this get trashed. Petelomax (talk) 05:49, 6 February 2024 (UTC)
Well F# and Rexx must be the only languages to go the extra millimetre. A generalised square root routine is not needed to complete the task. F# provides a function cf2S which takes 2 function returning the a and b values. If I want the sqrt of 127 for instance I could write:
<syntaxhighlight lang="fsharp">
let aπ()=126M
let bπ()=let mutable n=false in fun()->if n then 2M else (n<-true; 1M))
printfn "%f" (cf2S (aπ) (bπ()) |> Seq.item 60)
</syntaxhighlight>
which produces 11.26979217072510015046982059M. cfSqRt just invokes cf2S with the appropriate sequences. Nigel Galloway (talk) 18:44, 20 February 2024 (UTC)