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>

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

 

}

}

Output

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

 

=={{header|Clojure}}==

(if-not (= d 0) (cons (quot n d) (lazy-seq (r2cf d (rem n d))))))

 

(doseq [inputs demo

:let [outputs (r2cf (first inputs) (last inputs))]]

 

{{out}}

 

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

(lambda ()

(unless (zerop n2)

(31428571 10000000)

(314285714 100000000)

 

Output:

=={{header|D}}==

{{trans|Kotlin}}

import std.stdio;

 

frac.r2cf.iterate;

}

 

{{out}}

31428571 / 10000000 = 3 7 476190 3

314285714 / 100000000 = 3 7 7142857</pre>

 

=={{header|EDSAC order code}}==

Besides the assigned task, this program demonstrates a division subroutine

for 35-bit positive integers, returning quotient and remainder.

[Continued fractions from rationals.

EDSAC program, Initial Orders 2.]

E 13 Z [define entry point]

P F [acc = 0 on entry]

{{out}}

<pre>

314285714/100000000 = 3, 7, 7142857

</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; 2; 2; 6; 1; 2; 4; 1; 1; 2]</pre>

;A version for larger numerators and denominators.

let rec rI2cf n d =

if d = 0I then []

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

 

=={{header|Factor}}==

Note that the input values are stored as strings and converted to numbers before being fed to <code>r2cf</code>. This is because ratios automatically reduce themselves to the lowest-terms mixed number, which would make for confusing output in this instance.

sequences ;

IN: rosetta-code.cf-arithmetic

each ;

{{out}}

<pre>

314285714/100000000 -> { 3 7 7142857 }

</pre>

 

=={{header|Go}}==

 

File <code>cf.go</code>:

 

import (

}

}

File <code>rat.go</code>:

 

import "fmt"

// Rosetta Code task explicitly asked for this function,

// so here it is. We'll just use the types above instead.

File <code>rat_test.go</code>:

 

import (

// [… commented output used by go test omitted for

// Rosetta Code listing; it is the same as below …]

{{out}}

<pre>

{{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 (13 % 11)

, take 20 $ real2cf (sqrt 2)

{{Out}}

<pre>[1,5,2]

[1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]</pre>

 

=={{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|Java}}==

{{trans|Kotlin}}

{{works with|Java|9}}

import java.util.List;

import java.util.Map;

}

}

{{out}}

<pre> 1 / 2 = 0 2

{{works with|Julia|0.6}}

 

# Julia doesn't have Python'st yield, the closest to it is produce/consume calls with Julia tasks

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

 

println(collect(ContinuedFraction(13 // 11))) # => [1, 5, 2]

 

=={{header|Kotlin}}==

// compile with -Xcoroutines=enable flag from command line

 

iterate(r2cf(frac))

}

 

{{out}}

314285714 / 100000000 = 3 7 7142857

</pre>

 

=={{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|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

 

ReadChar;

 

=={{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>

 

=={{header|Phix}}==

{{out}}

<pre>

Running the examples :

 

Running for sqrt(2) :

 

Running for pi :

</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}}

(formerly Perl 6)

Straightforward implementation:

gather loop {

$x -= take $x.floor;

}

 

{{out}}

<pre>(0 2)

(1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2)</pre>

As a silly one-liner:

 

=={{header|REXX}}==

* &nbsp; Checks were included to verify that the arguments being passed to &nbsp; '''r2cf''' &nbsp; are indeed numeric and also not zero.

* &nbsp; This REXX version also handles negative numbers.

numeric digits 230 /*determines how many terms to be gened*/

say ' 1/2 ──► CF: ' r2cf( '1/2' )

do j=0 while h>9; m.j=h; h=h%2+1; end /*j*/

do k=j+5 to 0 by -1; numeric digits m.k; g=(g+x/g)*.5; end /*k*/

{{out|output|text=&nbsp; when using the default (internal) inputs:}}

<pre>

───────── an attempt at pi

pi ──► CF: 3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1 2 2 2 2 1 84 2 1 1 15 3 13 1 4 2 6 6 99 1 2 2 6 3 5 1 1 6 8 1 7 1 2 3 7 1 2 1 1 12 1 1 1 3 1 1 8 1 1 2 1 6 1 1 5 2 2 3 1 2 4 4 16 1 161 45 1 22 1 2 2 1 4 1 2 24 1 2 1 3 1 2 1 1 10 2 5 4 1 2 2 8 1 5 2 2 26 1 4 1 1 8 2 42 2 1 7 3 3 1 1 7 2 4 9 7 2 3 1 57 1 18 1 9 19 1 2 18 1 3 7 30 1 1 1 3 3 3 1 2 8 1 1 2 1 15 1 2 13 1 2 1 4 1 12 1 1 3 3 28 1 10 3 2 20 1 1 1 1 4 1 1 1 5 3 2 1 6 1 4 1 120 2 1 1 3 1 23 1 15 1 3 7 1 16 1 2 1 21 2 1 1 2 9 1 6 4

</pre>

 

=={{header|Ruby}}==

 

def r2cf(n1,n2)

yield t1

end

===Testing===

'''Test 1:'''

print "%10s : " % "#{n1} / #{n2}"

r2cf(n1,n2) {|n| print "#{n} "}

puts

{{out}}

<pre>

'''Test 2:'''

<math>\sqrt 2</math>

n2 = 10 ** (digit-1)

n1 = (Math.sqrt(2) * n2).round

r2cf(n1,n2) {|n| print "#{n} "}

puts

{{out}}

<pre>

</pre>

'''Test 3:'''

[314,100],

[3142,1000],

r2cf(n1,n2) {|n| print "#{n} "}

puts

{{out}}

<pre>

 

=={{header|Rust}}==

struct R2cf {

n1: i64,

printcf!(314_285_714, 100_000_000);

}

 

{{out}}

[3, 7, 476190, 3]

[3, 7, 7142857]

</pre>

 

=={{header|Sidef}}==

{{trans|Perl}}

func() {

den || return nil

seq.each { |r| showcf(r2cf(r.nude)) }

print "\n"

{{out}}

<pre>

{{trans|Ruby}}

===Direct translation===

 

proc r2cf {n1 {n2 1}} {

return -code break

}} $n1 $n2

Demonstrating:

puts -nonewline "$name -> "

while 1 {

} {

printcf "\[$n1;$n2\]" [r2cf $n1 $n2]

{{out}}

<pre>

</pre>

===Objectified version===

 

# General generator class based on coroutines

# Demonstrate parsing of input in forms other than a direct pair of decimals

printcf "1.5" [R2CF new 1.5]

{{out}}

<pre>

1.5 -> 1,2

23/7 -> 3,3,2

</pre>

 

=={{header|XPL0}}==

real Val;

 

RlOut(0, Val); CrLf(0);

I:= I+2];

{{out}}

<pre>

 

Light weight, explicit state:

Walker.tweak(fcn(state){

nom,dnom:=state;

n

}.fp(List(nom,dnom))) // partial application (light weight closure)

Heavy weight, implicit state:

Utils.Generator(fcn(nom,dnom){

while(dnom){

Void.Stop;

},nom,dnom)

Both of the above return an iterator so they function the same:

T(14142,10000), T(141421,100000), T(1414214,1000000),

T(14142136,10000000))){

r2cf(nom,dnom).walk(25).println(); // print up to 25 numbers

{{out}}

<pre>