Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Continued fraction/Arithmetic/Construct from rational number (view source)
Revision as of 22:09, 26 August 2022
, 1 year agosyntax highlighting fixup automation
(Added a Scheme implementation.) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 37:
{{trans|Python}}
<
[Int] r
L n2 != 0
Line 53:
print(r2cf(141421, 100000))
print(r2cf(1414214, 1000000))
print(r2cf(14142136, 10000000))</
{{out}}
Line 73:
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 #
Line 155:
show r2cf( "Running for pi :", pi )
END
END</
{{out}}
<pre>
Line 186:
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.
<syntaxhighlight lang="c">
#include<stdio.h>
Line 257:
}
</
And the run gives :
<pre>
Line 286:
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 331:
}
}
</syntaxhighlight>
Output
<pre>
Line 357:
=={{header|C++}}==
<
/* Interface for all Continued Fractions
Nigel Galloway, February 9th., 2013.
Line 388:
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;
Line 405:
std::cout << std::endl;
return 0;
}</
{{out}}
<pre>
Line 416:
</pre>
====<math>\sqrt 2</math>====
<
int i = 0;
for(SQRT2 n; i++ < 20; std::cout << n.nextTerm() << " ");
Line 425:
std::cout << std::endl;
return 0;
}</
{{out}}
<pre>
Line 433:
</pre>
====Real approximations of a rational number====
<
for(r2cf n(31,10); n.moreTerms(); std::cout << n.nextTerm() << " ");
std::cout << std::endl;
Line 451:
std::cout << std::endl;
return 0;
}</
{{out}}
<pre>
Line 465:
=={{header|Clojure}}==
<
(if-not (= d 0) (cons (quot n d) (lazy-seq (r2cf d (rem n d))))))
Line 491:
(doseq [inputs demo
:let [outputs (r2cf (first inputs) (last inputs))]]
(println inputs ";" outputs))</
{{out}}
Line 517:
=={{header|Common Lisp}}==
<
(lambda ()
(unless (zerop n2)
Line 557:
(31428571 10000000)
(314285714 100000000)
(3141592653589793 1000000000000000)))</
Output:
Line 583:
=={{header|D}}==
{{trans|Kotlin}}
<
import std.stdio;
Line 654:
frac.r2cf.iterate;
}
}</
{{out}}
Line 683:
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.]
Line 924:
E 13 Z [define entry point]
P F [acc = 0 on entry]
</syntaxhighlight>
{{out}}
<pre>
Line 939:
=={{header|F_Sharp|F#}}==
<
if d = LanguagePrimitives.GenericZero then []
else let q = n / d in q :: (r2cf d (n - q * d))
Line 957:
printfn "%A" (r2cf 1414214 1000000)
printfn "%A" (r2cf 14142136 10000000)
0</
Output
<pre>[0; 2]
Line 972:
[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))
</syntaxhighlight>
=={{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
Line 1,012:
each ;
MAIN: main</
{{out}}
<pre>
Line 1,039:
{{works with|gforth|0.7.3}}
<
: .r2cf ( num den -- )
Line 1,067:
314285714 100000000 .r2cf
3141592653589793 1000000000000000 .r2cf ;
r2cf-demo</
{{out}}
Line 1,093:
=={{header|FreeBASIC}}==
<
'with some other constants
data 1,2, 21,7, 21,-7, 7,21, -7,21
Line 1,151:
sleep
system
</syntaxhighlight>
{{out}}
<pre>
Line 1,190:
File <code>cf.go</code>:
<
import (
Line 1,264:
}
}
}</
File <code>rat.go</code>:
<
import "fmt"
Line 1,296:
// Rosetta Code task explicitly asked for this function,
// so here it is. We'll just use the types above instead.
func r2cf(n1, n2 int64) ContinuedFraction { return Rat{n1, n2}.CFTerms }</
File <code>rat_test.go</code>:
<
import (
Line 1,344:
// [… commented output used by go test omitted for
// Rosetta Code listing; it is the same as below …]
}</
{{out}}
<pre>
Line 1,390:
{{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]
Line 1,406:
[ real2cf (13 % 11)
, take 20 $ real2cf (sqrt 2)
]</
{{Out}}
<pre>[1,5,2]
Line 1,417:
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│
Line 1,430:
┌────┬─────┬──────────┬───────┬────────┬──────────┬────────────┬───────────┐
│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,
<
1</
Incidentally, J and Tcl report a different representation for -151/77 versus the representation of some other implementations; however, both representations produce equal results.
<
1</
===Tacit version 2===
Line 1,442:
Translation of python
<
Example use:
<
1/2: 0 2
3/1: 3
Line 1,465:
3142857/1000000: 3 7 142857
31428571/10000000: 3 7 476190 3
314285714/100000000: 3 7 7142857 </
===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.
<syntaxhighlight lang="j">
coclass'cf'
create =: dyad def 'EMPTY [ N =: x , y'
Line 1,503:
│_151 77 │_2 25 1 2 │
└─────────────────┴─────────────────────────────────┘
)</
==== version 2 ====
<syntaxhighlight lang="j">
f =: 3 : 0
a =. {.y
Line 1,518:
┌───┬─┬─────┬─────┬───┬───────────────────────────────────┬─────────┐
│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 ====
Line 1,524:
translation of python:
<
'n1 n2'=. y
r=.''
Line 1,531:
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;
Line 1,619:
}
}
}</
{{out}}
<pre> 1 / 2 = 0 2
Line 1,648:
{{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
Line 1,702:
println(collect(ContinuedFraction(13 // 11))) # => [1, 5, 2]
println(collect(ContinuedFraction(√2), 20)) # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]</
=={{header|Kotlin}}==
<
// compile with -Xcoroutines=enable flag from command line
Line 1,749:
iterate(r2cf(frac))
}
}</
{{out}}
Line 1,779:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Mathematica has a build-in function ContinuedFraction.
<
ContinuedFraction[3]
ContinuedFraction[23/8]
Line 1,788:
ContinuedFraction[141421/100000]
ContinuedFraction[1414214/1000000]
ContinuedFraction[14142136/10000000]</
{{Out}}
<pre>{0, 2}
Line 1,802:
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,877:
ReadChar;
END ConstructFromrationalNumber.</
=={{header|Nim}}==
<
var (n1, n2) = (n1, n2)
while n2 != 0:
Line 1,903:
for pair in [(31,10), (314,100), (3142,1000), (31428,10000), (314285,100000),
(3142857,1000000), (31428571,10000000), (314285714,100000000)]:
echo pair, " -> ", toSeq(r2cf(pair[0], pair[1]))</
{{out}}
Line 1,928:
=={{header|PARI/GP}}==
<
{{out}}
<pre>[[0, 2], [3], [2, 1, 7], [1, 5, 2], [3, 7], [-2, 25, 1, 2]]</pre>
Line 1,934:
=={{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 {
Line 1,959:
for ([14142,10000],[141421,100000],[1414214,1000000],[14142136,10000000]);
print "\n";
rcshow(rc2f(314285714,100000000));</
{{out}}
<pre>
Line 1,978:
=={{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>
Line 2,015:
<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>
Line 2,046:
=={{header|Python}}==
{{trans|Ruby}}
<
while n2:
n1, (t1, n2) = n2, divmod(n1, n2)
Line 2,059:
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]
print(list(r2cf(14142136,10000000))) # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2]</
This version generates it from any real number (with rationals as a special case):
<
while True:
t1, f = divmod(x, 1)
Line 2,073:
print(list(real2cf(Fraction(13, 11)))) # => [1, 5, 2]
print(list(islice(real2cf(2 ** 0.5), 20))) # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]</
=={{header|Quackery}}==
<syntaxhighlight lang="quackery">
[ $ "bigrat.qky" loadfile ] now!
Line 2,110:
dup echo
say " = "
cf echo cr ]</
{{out}}
Line 2,135:
=={{header|Racket}}==
<
#lang racket
Line 2,158:
(real->cf (sqrt 2) 10)
(real->cf pi 10)
</syntaxhighlight>
{{out}}
Line 2,171:
(formerly Perl 6)
Straightforward implementation:
<syntaxhighlight lang="raku"
gather loop {
$x -= take $x.floor;
Line 2,179:
}
say r2cf(.Rat) for <1/2 3 23/8 13/11 22/7 1.41 1.4142136>;</
{{out}}
<pre>(0 2)
Line 2,189:
(1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2)</pre>
As a silly one-liner:
<syntaxhighlight lang="raku"
=={{header|REXX}}==
Line 2,198:
* Checks were included to verify that the arguments being passed to '''r2cf''' are indeed numeric and also not zero.
* This REXX version also handles negative numbers.
<
numeric digits 230 /*determines how many terms to be gened*/
say ' 1/2 ──► CF: ' r2cf( '1/2' )
Line 2,255:
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*/
numeric digits d; return g/1</
{{out|output|text= when using the default (internal) inputs:}}
<pre>
Line 2,281:
=={{header|Ruby}}==
<
def r2cf(n1,n2)
Line 2,288:
yield t1
end
end</
===Testing===
'''Test 1:'''
<
print "%10s : " % "#{n1} / #{n2}"
r2cf(n1,n2) {|n| print "#{n} "}
puts
end</
{{out}}
<pre>
Line 2,307:
'''Test 2:'''
<math>\sqrt 2</math>
<
n2 = 10 ** (digit-1)
n1 = (Math.sqrt(2) * n2).round
Line 2,313:
r2cf(n1,n2) {|n| print "#{n} "}
puts
end</
{{out}}
<pre>
Line 2,322:
</pre>
'''Test 3:'''
<
[314,100],
[3142,1000],
Line 2,335:
r2cf(n1,n2) {|n| print "#{n} "}
puts
end</
{{out}}
<pre>
Line 2,349:
=={{header|Rust}}==
<
struct R2cf {
n1: i64,
Line 2,404:
printcf!(314_285_714, 100_000_000);
}
</syntaxhighlight>
{{out}}
Line 2,430:
{{works with|Chez Scheme}}
'''The Implementation'''
<
; Returns one term per call; returns #f when no more terms remaining.
(define make-continued-fraction-gen
Line 2,466:
(set! lst (append lst (list term)))
(loop (cf))))
lst)))</
'''The Task'''
<br />
Each continued fraction is displayed in both the conventional written form and as a list of terms.
<
(for-each
(lambda (rat)
Line 2,490:
(printf "~a : ~a~%" rat (rat->cf-list rat)))
'(31/10 314/100 3142/1000 31428/10000 314285/100000 3142857/1000000
31428571/10000000 314285714/100000000 31415926535898/10000000000000))</
{{out}}
<pre>
Line 2,544:
=={{header|Sidef}}==
{{trans|Perl}}
<
func() {
den || return nil
Line 2,568:
seq.each { |r| showcf(r2cf(r.nude)) }
print "\n"
}</
{{out}}
<pre>
Line 2,590:
{{trans|Ruby}}
===Direct translation===
<
proc r2cf {n1 {n2 1}} {
Line 2,608:
return -code break
}} $n1 $n2
}</
Demonstrating:
<
puts -nonewline "$name -> "
while 1 {
Line 2,640:
} {
printcf "\[$n1;$n2\]" [r2cf $n1 $n2]
}</
{{out}}
<pre>
Line 2,664:
</pre>
===Objectified version===
<
# General generator class based on coroutines
Line 2,772:
# Demonstrate parsing of input in forms other than a direct pair of decimals
printcf "1.5" [R2CF new 1.5]
printcf "23/7" [R2CF new 23/7]</
{{out}}
<pre>
Line 2,801:
{{libheader|Wren-rat}}
{{libheader|Wren-fmt}}
<
import "/fmt" for Fmt
Line 2,840:
System.print()
i = i + 1
}</
{{out}}
Line 2,870:
=={{header|XPL0}}==
<
real Val;
Line 2,894:
RlOut(0, Val); CrLf(0);
I:= I+2];
]</
{{out}}
<pre>
Line 2,908:
Light weight, explicit state:
<
Walker.tweak(fcn(state){
nom,dnom:=state;
Line 2,916:
n
}.fp(List(nom,dnom))) // partial application (light weight closure)
}</
Heavy weight, implicit state:
<
Utils.Generator(fcn(nom,dnom){
while(dnom){
Line 2,926:
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>
|