Jump to content

Continued fraction/Arithmetic/Construct from rational number: Difference between revisions

Continued fraction/Arithmetic/Construct from rational number (view source)

Revision as of 18:31, 27 February 2023

1,090 bytes removed ,  1 year ago
→‎{{header|ATS}}
Line 293:
=={{header|ATS}}==
 
===Using a non-linear closure===
I found the reference to "lazy evaluation" misleading, for it implies a special feature of a programming language. Haskell, for example, evaluates lists "lazily". ATS has the notation '''$delay''', and there are various "lazy list" implementations for Scheme. I considered using such methods, but decided against doing so.
 
In the first example solution, I demonstrate concretely that the method of integer division matters. I use 'Euclidean division' (see ACM Transactions on Programming Languages and Systems, Volume 14, Issue 2, pp 127–144. https://doi.org/10.1145/128861.128862) and show that you get a different continued fraction if you start with (-151)/77 than if you start with 151/(-77). I verified that both continued fractions do equal -(151/77).▼
What one is--I am certain--supposed to write is means for generating an arbitrary number of terms of a continued fraction, one term after another. It happens that, for a rational number, eventually all further terms are known to be swamped by an infinity, and so need not be computed. The significant (finite-valued) terms ''could'' be returned as a finite-length list. However, this will not be so when irrational numbers enter the picture. Therefore one needs a way to generate ''an indefinite number'' of terms. But this is something that requires no "lazy" features of a language. It could be done easily in standard C! The resulting code might, indeed, evaluate terms "lazily", but no special language features are required.
 
A closure is used to generate the next term (or '''None()''') each time it is called. The integer type is mostly arbitrary.
So I do not use '''$delay''' at all. I do use closures, which standard C does not have, but pairing a regular procedure with an environment could achieve the same effect in C. (Indeed, the ATS compiler implements closures by generating such C code.)
 
<hr/>
 
▲In the first example solution, I demonstrate concretely that the method of integer division matters. I use 'Euclidean division' (see ACM Transactions on Programming Languages and Systems, Volume 14, Issue 2, pp 127–144. https://doi.org/10.1145/128861.128862) and show that you get a different continued fraction if you start with (-151)/77 than if you start with 151/(-77). I verified that both continued fractions do equal -(151/77).
 
<syntaxhighlight lang="ats">
Line 495 ⟶ 491:
</pre>
 
=== Using a non-linear closure and multiple precision numbers ===
For this you need the [https://sourceforge.net/p/chemoelectric/ats2-xprelude '''ats2-xprelude'''] package. I start with octuple precision (IEEE binary256) approximations to the square root of 2 and 22/7.
 
Line 641 ⟶ 637:
</pre>
 
===Using a non-linear closure and memoizing in an array===
===A practical implementation===
 
This example solution was written specifically with the idea of providing a general representation of possibly infinitely long continued fractions. Terms can be obtained arbitrarily, by their indices. One obtains '''Some term''' if the term is finite, or '''None()''' if the term is infinite.
 
One drawback is that, because a continued fraction is memoized, and its terms are generated as needed, the data structure may need to be updated. Therefore it must be stored in a mutable location, such as a '''var''' or '''ref'''.
 
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
Chemoelectric
1,448

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/337730"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information