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

 

Observe how this rational number behaves differently to <math>\sqrt 2</math> and convince yourself that, in the same way as <math>3.7</math> may be represented as <math>3.70</math> when an extra decimal place is required, <math>[3;7]</math> may be represented as <math>[3;7,\infty]</math> when an extra term is required.

 

=={{header|C}}==

C does not implement Lazy evaluation and it is this particular feature which is the real challenge of this particular example. It can however be simulated. The following example uses pointers. It seems that the same data is being passed but since the function accepts pointers, the variables are being changed. One other way to simulate laziness would be to use global variables. Then although it would seem that the same values are being passed even as constants, the job is actually getting done. In my view, that would be plain cheating.

 

#include<stdio.h>

 

}

And the run gives :

<pre>

For N = 314285714, D = 100000000 : 3 7 7142857

</pre>

 

=={{header|C++}}==

/* Interface for all Continued Fractions

Nigel Galloway, February 9th., 2013.

const int nextTerm() {if (first) {first = false; return 1;} else return 2;}

const bool moreTerms() {return true;}

===Testing===

====1/2 3 23/8 13/11 22/7 -151/77====

for(r2cf n(1,2); n.moreTerms(); std::cout << n.nextTerm() << " ");

std::cout << std::endl;

std::cout << std::endl;

return 0;

{{out}}

<pre>

</pre>

====<math>\sqrt 2</math>====

int i = 0;

for(SQRT2 n; i++ < 20; std::cout << n.nextTerm() << " ");

std::cout << std::endl;

return 0;

{{out}}

<pre>

</pre>

====Real approximations of a rational number====

for(r2cf n(31,10); n.moreTerms(); std::cout << n.nextTerm() << " ");

std::cout << std::endl;

std::cout << std::endl;

return 0;

{{out}}

<pre>

</pre>

 

 

 

 

<pre>

 

=={{header|Common Lisp}}==

(lambda ()

(unless (zerop n2)

(31428571 10000000)

(314285714 100000000)

 

Output:

(R2CF 3141592653589793 1000000000000000) ; (3 7 15 1 292 1 1 1 2 1 3 1 14 4 2 3 1 12 5 1 5 20 1 11 1 1 1 2)

</pre>

=={{header|F_Sharp|F#}}==

if d = LanguagePrimitives.GenericZero then []

else let q = n / d in q :: (r2cf d (n - q * d))

printfn "%A" (r2cf 1414214 1000000)

printfn "%A" (r2cf 14142136 10000000)

Output

<pre>[0; 2]

[1; 2; 2; 2; 2; 2; 2; 2; 3; 6; 1; 2; 1; 12]

[1; 2; 2; 2; 2; 2; 2; 2; 2; 2; 6; 1; 2; 4; 1; 1; 2]</pre>

 

=={{header|Haskell}}==

{{trans|Python}}

This more general version generates a continued fraction from any real number (with rationals as a special case):

 

real2cf :: (RealFrac a, Integral b) => a -> [b]

real2cf x =

 

main :: IO ()

 

=={{header|J}}==

 

This version is a modification of an explicit version shown in http://www.jsoftware.com/jwiki/Essays/Continued%20Fractions to comply with the task specifications.

==== Examples ====

┌───┬─┬─────┬─────┬───┬─────────────────────────────────┬─────────┐

│0 2│3│2 1 7│1 5 2│3 7│1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2│_2 25 1 2│

┌────┬─────┬──────────┬───────┬────────┬──────────┬────────────┬───────────┐

│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│

This tacit version first produces the answer with a trailing ∞ (represented by _ in J) which is then removed by the last operation (_1 1 ,@}. ...). A continued fraction can be evaluated using the verb ((+%)/) and both representations produce equal results,

Incidentally, J and Tcl report a different representation for -151/77 versus the representation of some other implementations; however, both representations produce equal results.

 

===Tacit version 2===

Translation of python

 

 

Example use:

 

1/2: 0 2

3/1: 3

3142857/1000000: 3 7 142857

31428571/10000000: 3 7 476190 3

 

===Explicit versions===

==== version 1 ====

Implemented as a class, r2cf preserves state in a separate locale. I've used some contrivances to jam the examples onto one line.

coclass'cf'

create =: dyad def 'EMPTY [ N =: x , y'

│_151 77 │_2 25 1 2 │

└─────────────────┴─────────────────────────────────┘

==== version 2 ====

f =: 3 : 0

a =. {.y

┌───┬─┬─────┬─────┬───┬───────────────────────────────────┬─────────┐

│0 2│3│2 1 7│1 5 2│3 7│1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2 _│_2 25 1 2│

 

==== version 3 ====

translation of python:

 

'n1 n2'=. y

r=.''

r=.r,t1

end.

 

Example:

 

┌───┬─┬─────┬─────┬───┬─────────────────────────────────┬─────────┐

│0 2│3│2 1 7│1 5 2│3 7│1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2│_2 25 1 2│

 

=={{header|Julia}}==

# but for various reasons they don't work out for this task

# This solution works with two integers, a Julia rational or a real

 

end

 

 

end

 

 

# array slicing doesn't work as Julia crashes before the slicing due to our infinitely long array

end

 

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Mathematica has a build-in function ContinuedFraction.

ContinuedFraction[3]

ContinuedFraction[23/8]

ContinuedFraction[141421/100000]

ContinuedFraction[1414214/1000000]

{{Out}}

<pre>{0, 2}

{1, 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12}

{1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2}</pre>

 

=={{header|PARI/GP}}==

{{out}}

<pre>[[0, 2], [3], [2, 1, 7], [1, 5, 2], [3, 7], [-2, 25, 1, 2]]</pre>

=={{header|Perl}}==

To do output one digit at a time, we first turn off buffering to be pedantic, then use a closure that yields one term per call.

 

sub rc2f {

for ([14142,10000],[141421,100000],[1414214,1000000],[14142136,10000000]);

print "\n";

{{out}}

<pre>

</pre>

 

 

 

=={{header|Python}}==

{{trans|Ruby}}

while n2:

n1, (t1, n2) = n2, divmod(n1, n2)

print(list(r2cf(141421,100000))) # => [1, 2, 2, 2, 2, 2, 2, 3, 1, 1, 3, 1, 7, 2]

print(list(r2cf(1414214,1000000))) # => [1, 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12]

This version generates it from any real number (with rationals as a special case):

while True:

t1, f = divmod(x, 1)

 

print(list(real2cf(Fraction(13, 11)))) # => [1, 5, 2]

 

=={{header|Racket}}==

#lang racket

 

(real->cf (sqrt 2) 10)

(real->cf pi 10)

 

{{out}}

'(1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 1 3 8 9 1 20 1 2)

'(3 7 15 1 292 1 1 6 2 13 3 1 12 3)

</pre>

 

=={{header|REXX}}==

Programming notes: