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

<lang Go>package main

import (

"fmt"

"math"

"strings"

)

type NextFn func() (term int64, more bool)

type ContinuedFraction func() NextFn

func (cf ContinuedFraction) String() string {

var buf strings.Builder

next := cf()

t, more := next()

fmt.Fprintf(&buf, "[%d", t)

sep := "; "

const maxTerms = 20

for n := 0; more; n++ {

if n > maxTerms {

fmt.Fprint(&buf, ", ...")

break

}

t, more = next()

fmt.Fprintf(&buf, "%s%d", sep, t)

sep = ", "

}

fmt.Fprint(&buf, "]")

return buf.String()

}

type Rat struct {

N, D int64

}

func (r Rat) String() string {

return fmt.Sprintf("%d/%d", r.N, r.D)

}

func (r Rat) AsContinuedFraction() ContinuedFraction { return r.CFTerms }

func (r Rat) CFTerms() NextFn {

n, d := r.N, r.D

return func() (int64, bool) {

q := n / d

n, d = d, n-q*d

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

}

return 2, true

}

}

// Rosetta Code task explicitly asked for this function.

// We'll just use the types above instead.

func r2cf(n1, n2 int64) ContinuedFraction { return Rat{n1, n2}.CFTerms }

func main() {

cases := [...]Rat{

{1, 2},

{3, 1},

{23, 8},

{13, 11},

{22, 7},

{-151, 77},

}

for _, r := range cases {

fmt.Printf("%7s = %s\n", r, r.AsContinuedFraction())

}

for _, tc := range [...]struct {

name string

approx float64

cf ContinuedFraction

}{

{"√2", math.Sqrt2, Sqrt2},

{"π", math.Pi, nil},

{"ϕ", math.Phi, Phi},

} {

fmt.Printf("\nApproximating %s ≅ %v:\n", tc.name, tc.approx)

for d := int64(10); d < 1e12; d *= 10 {

n := int64(math.Floor(tc.approx * float64(d)))

r := Rat{n, d}

fmt.Println(r, "=", r.AsContinuedFraction())

}

if tc.cf != nil {

fmt.Println("Actual:", tc.cf)

}

}

}</lang>

{{out}}

<pre>

1/2 = [0; 2]

3/1 = [3]

23/8 = [2; 1, 7]

13/11 = [1; 5, 2]

22/7 = [3; 7]

-151/77 = [-1; -1, -24, -1, -2]

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]

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]

14142135/10000000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 594]

141421356/100000000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 1, 1, 2, 6, 8]

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:

31/10 = [3; 10]

314/100 = [3; 7, 7]

3141/1000 = [3; 7, 10, 1, 5, 2]

31415/10000 = [3; 7, 14, 1, 8, 2]

314159/100000 = [3; 7, 15, 1, 25, 1, 7, 4]

3141592/1000000 = [3; 7, 15, 1, 84, 6, 2]

31415926/10000000 = [3; 7, 15, 1, 243, 1, 1, 9, 1, 1, 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]

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:

16/10 = [1; 1, 1, 2]

161/100 = [1; 1, 1, 1, 1, 3, 2, 2]

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]

161803/100000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 6, 2]

1618033/1000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 129]

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, ...]

1618033988/1000000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, ...]

16180339887/10000000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]

161803398874/100000000000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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, ...]

</pre>