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

Content added Content deleted
(→‎{{header|Go}}: Add Go solution)
(→‎{{header|Go}}: Update Go to match other (upcoming) Continued_fraction/* tasks.)
Line 568: Line 568:


=={{header|Go}}==
=={{header|Go}}==
File <code>cf.go</code>:
<lang Go>package main
<lang Go>package cf


import (
import (
"fmt"
"fmt"
"math"
"strings"
"strings"
)
)


// ContinuedFraction is a regular continued fraction.
type NextFn func() (term int64, more bool)
type ContinuedFraction func() NextFn
type ContinuedFraction func() NextFn


// NextFn is a function/closure that can return
// a posibly infinite sequence of values.
type NextFn func() (term int64, ok bool)

// String implements fmt.Stringer.
// It formats a maximum of 20 values, ending the
// sequence with ", ..." if the sequence is longer.
func (cf ContinuedFraction) String() string {
func (cf ContinuedFraction) String() string {
var buf strings.Builder
var buf strings.Builder
buf.WriteByte('[')
next := cf()
t, more := next()
fmt.Fprintf(&buf, "[%d", t)
sep := "; "
sep := "; "
const maxTerms = 20
const maxTerms = 20
for n := 0; more; n++ {
next := cf()
if n > maxTerms {
for n := 0; ; n++ {
t, ok := next()
fmt.Fprint(&buf, ", ...")
if !ok {
break
break
}
}
t, more = next()
if n > 0 {
buf.WriteString(sep)
fmt.Fprintf(&buf, "%s%d", sep, t)
sep = ", "
sep = ", "
}
if n >= maxTerms {
buf.WriteString("...")
break
}
fmt.Fprint(&buf, t)
}
}
buf.WriteByte(']')
fmt.Fprint(&buf, "]")
return buf.String()
return buf.String()
}
}


// Sqrt2 is the continued fraction for √2, [1; 2, 2, 2, ...].
func Sqrt2() NextFn {
first := true
return func() (int64, bool) {
if first {
first = false
return 1, true
}
return 2, true
}
}

// Phi is the continued fraction for ϕ, [1; 1, 1, 1, ...].
func Phi() NextFn {
return func() (int64, bool) { return 1, true }
}

// E is the continued fraction for e,
// [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, ...].
func E() NextFn {
var i int
return func() (int64, bool) {
i++
switch {
case i == 1:
return 2, true
case i%3 == 0:
return int64(i/3) * 2, true
default:
return 1, true
}
}
}</lang>
File <code>rat.go</code>:
<lang Go>package cf

import "fmt"

// A Rat represents a quotient N/D.
type Rat struct {
type Rat struct {
N, D int64
N, D int64
}
}


// String implements fmt.Stringer and returns a string
// representation of `r` in the form "N/D" (even if D == 1).
func (r Rat) String() string {
func (r Rat) String() string {
return fmt.Sprintf("%d/%d", r.N, r.D)
return fmt.Sprintf("%d/%d", r.N, r.D)
}
}


// As ContinuedFraction returns a contined fraction representation of `r`.
func (r Rat) AsContinuedFraction() ContinuedFraction { return r.CFTerms }
func (r Rat) AsContinuedFraction() ContinuedFraction { return r.CFTerms }
func (r Rat) CFTerms() NextFn {
func (r Rat) CFTerms() NextFn {
n, d := r.N, r.D
return func() (int64, bool) {
return func() (int64, bool) {
q := n / d
if r.D == 0 {
n, d = d, n-q*d
return 0, false
return q, d != 0
}
}

func Phi() NextFn {
return func() (int64, bool) { return 1, true }
}

func Sqrt2() NextFn {
first := true
return func() (int64, bool) {
if first {
first = false
return 1, true
}
}
q := r.N / r.D
return 2, true
r.N, r.D = r.D, r.N-q*r.D
return q, true
}
}
}
}


// Rosetta Code task explicitly asked for this function.
// Rosetta Code task explicitly asked for this function,
// We'll just use the types above instead.
// so here it is. We'll just use the types above instead.
func r2cf(n1, n2 int64) ContinuedFraction { return Rat{n1, n2}.CFTerms }
func r2cf(n1, n2 int64) ContinuedFraction { return Rat{n1, n2}.CFTerms }</lang>
File <code>rat_test.go</code>:
<lang Go>package cf

import (
"fmt"
"math"
)


func main() {
func Example_ConstructFromRational() {
cases := [...]Rat{
cases := [...]Rat{
{1, 2},
{1, 2},
Line 653: Line 701:
approx float64
approx float64
cf ContinuedFraction
cf ContinuedFraction
d1, d2 int64
}{
}{
{"√2", math.Sqrt2, Sqrt2},
{"√2", math.Sqrt2, Sqrt2, 1e4, 1e8},
{"π", math.Pi, nil},
{"π", math.Pi, nil, 10, 1e10},
{"ϕ", math.Phi, Phi},
{"ϕ", math.Phi, Phi, 10, 1e5},
{"e", math.E, E, 1e5, 1e9},
} {
} {
fmt.Printf("\nApproximating %s ≅ %v:\n", tc.name, tc.approx)
fmt.Printf("\nApproximating %s ≅ %v:\n", tc.name, tc.approx)
for d := int64(10); d < 1e12; d *= 10 {
for d := tc.d1; d < tc.d2; d *= 10 {
n := int64(math.Floor(tc.approx * float64(d)))
n := int64(math.Round(tc.approx * float64(d)))
r := Rat{n, d}
r := Rat{n, d}
fmt.Println(r, "=", r.AsContinuedFraction())
fmt.Println(r, "=", r.AsContinuedFraction())
}
}
if tc.cf != nil {
if tc.cf != nil {
wid := int(math.Log10(float64(tc.d2)))*2 + 2 // ick
fmt.Println("Actual:", tc.cf)
fmt.Printf("%*s: %v\n", wid, "Actual", tc.cf)
}
}
}
}

// Output:
// [… commented output used by go test omitted for
// Rosetta Code listing; it is the same as below …]
}</lang>
}</lang>
{{out}}
{{out}}
Line 679: Line 734:


Approximating √2 ≅ 1.4142135623730951:
Approximating √2 ≅ 1.4142135623730951:
14/10 = [1; 2, 2]
141/100 = [1; 2, 2, 3, 1, 1, 2]
1414/1000 = [1; 2, 2, 2, 2, 5, 3]
14142/10000 = [1; 2, 2, 2, 2, 2, 1, 1, 29]
14142/10000 = [1; 2, 2, 2, 2, 2, 1, 1, 29]
141421/100000 = [1; 2, 2, 2, 2, 2, 2, 3, 1, 1, 3, 1, 7, 2]
141421/100000 = [1; 2, 2, 2, 2, 2, 2, 3, 1, 1, 3, 1, 7, 2]
1414213/1000000 = [1; 2, 2, 2, 2, 2, 2, 2, 1, 1, 4, 1, 1, 1, 1, 1, 2, 1, 6]
1414214/1000000 = [1; 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12]
14142135/10000000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 594]
14142136/10000000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2]
141421356/100000000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 1, 1, 2, 6, 8]
Actual: [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...]
1414213562/1000000000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 14, 1, 238, 1, 3]
14142135623/10000000000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 1, 3, 8, 9, 1, 20, 1, ...]
141421356237/100000000000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 1, 4, 1, 2, 1, 63, ...]
Actual: [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...]


Approximating π ≅ 3.141592653589793:
Approximating π ≅ 3.141592653589793:
31/10 = [3; 10]
31/10 = [3; 10]
314/100 = [3; 7, 7]
314/100 = [3; 7, 7]
3141/1000 = [3; 7, 10, 1, 5, 2]
3142/1000 = [3; 7, 23, 1, 2]
31415/10000 = [3; 7, 14, 1, 8, 2]
31416/10000 = [3; 7, 16, 11]
314159/100000 = [3; 7, 15, 1, 25, 1, 7, 4]
314159/100000 = [3; 7, 15, 1, 25, 1, 7, 4]
3141592/1000000 = [3; 7, 15, 1, 84, 6, 2]
3141593/1000000 = [3; 7, 16, 983, 4, 2]
31415926/10000000 = [3; 7, 15, 1, 243, 1, 1, 9, 1, 1, 4]
31415927/10000000 = [3; 7, 15, 1, 354, 2, 6, 1, 4, 1, 2]
314159265/100000000 = [3; 7, 15, 1, 288, 1, 2, 1, 3, 1, 7, 4]
314159265/100000000 = [3; 7, 15, 1, 288, 1, 2, 1, 3, 1, 7, 4]
3141592653/1000000000 = [3; 7, 15, 1, 291, 1, 75, 1, 2, 9, 1, 3, 3]
3141592654/1000000000 = [3; 7, 15, 1, 293, 11, 1, 1, 7, 2, 1, 3, 3, 2]
31415926535/10000000000 = [3; 7, 15, 1, 292, 1, 1, 6, 2, 13, 3, 1, 12, 3]
314159265358/100000000000 = [3; 7, 15, 1, 292, 1, 1, 1, 1, 1, 12, 1, 1, 4, 1, 1, 4, 1, 9, 1, 11]


Approximating ϕ ≅ 1.618033988749895:
Approximating ϕ ≅ 1.618033988749895:
16/10 = [1; 1, 1, 2]
16/10 = [1; 1, 1, 2]
161/100 = [1; 1, 1, 1, 1, 3, 2, 2]
162/100 = [1; 1, 1, 1, 1, 1, 2, 2]
1618/1000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]
1618/1000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]
16180/10000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]
16180/10000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]
161803/100000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 6, 2]
Actual: [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]

1618033/1000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 129]
Approximating e ≅ 2.718281828459045:
16180339/10000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 10, 15, 1, ...]
161803398/100000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, ...]
271828/100000 = [2; 1, 2, 1, 1, 4, 1, 1, 6, 10, 1, 1, 2]
1618033988/1000000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, ...]
2718282/1000000 = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 3, 141]
16180339887/10000000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]
27182818/10000000 = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 11, 1, 2, 10, 6, 2]
161803398874/100000000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]
271828183/100000000 = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 2, 1, 1, 17, 6, 1, 1, 1, ...]
Actual: [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]
Actual: [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, ...]
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Continued_fraction/Arithmetic/Construct_from_rational_number"