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

{{trans|Python}}

[Int] r

L n2 != 0

print(r2cf(141421, 100000))

print(r2cf(1414214, 1000000))

{{out}}

The continued fraction expansion of -151/77 is sensitive to whether the language modulo operator follows the mathematical definition or the C definition.<br>

Algol 68's MOD operator uses the mathematical definition (rounds towards -infinity), so the results for -157//77 agree with the EDSAC, J and a few other sdamples. Most other samples calculate the remainder using the C definotion.

# Translated from the C sample #

# Uses code from the Arithmetic/Rational task #

show r2cf( "Running for pi :", pi )

END

{{out}}

<pre>

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

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>

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

{{works with|gforth|0.7.3}}

: .r2cf ( num den -- )

314285714 100000000 .r2cf

3141592653589793 1000000000000000 .r2cf ;

{{out}}

=={{header|FreeBASIC}}==

'with some other constants

data 1,2, 21,7, 21,-7, 7,21, -7,21

sleep

system

{{out}}

<pre>

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]

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

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

=={{header|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

ReadChar;

=={{header|Nim}}==

var (n1, n2) = (n1, n2)

while n2 != 0:

for pair in [(31,10), (314,100), (3142,1000), (31428,10000), (314285,100000),

(3142857,1000000), (31428571,10000000), (314285714,100000000)]:

{{out}}

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

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">r2cf</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">denom</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"for sqrt(2)"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sqrt2</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"for pi"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">)</span>

{{out}}

<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|Quackery}}==

[ $ "bigrat.qky" loadfile ] now!

dup echo

say " = "

{{out}}

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

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

{{works with|Chez Scheme}}

'''The Implementation'''

; Returns one term per call; returns #f when no more terms remaining.

(define make-continued-fraction-gen

(set! lst (append lst (list term)))

(loop (cf))))

'''The Task'''

<br />

Each continued fraction is displayed in both the conventional written form and as a list of terms.

(for-each

(lambda (rat)

(printf "~a : ~a~%" rat (rat->cf-list rat)))

'(31/10 314/100 3142/1000 31428/10000 314285/100000 3142857/1000000

{{out}}

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

{{libheader|Wren-rat}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

System.print()

i = i + 1

{{out}}

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