Continued fraction

A number may be represented as a continued fraction (see Mathworld for more information) as follows:

cf=a_{1}+{\cfrac {b_{1}}{a_{2}+{\cfrac {b_{2}}{a_{3}+{\cfrac {b_{3}}{\mathrm {etc\ldots } }}}}}}

The task is to write a program which generates such a number and prints a real representation of it. The code should be tested by calculating and printing the square root of 2, Napier's Constant, and Pi.

For the square root of 2, $b_{N}$ is always $1$ . $a_{1}$ is $1$ then $a_{N}$ is $2$ .

For Napier's Constant, $a_{1}$ is $2$ , then $a_{N}$ is $N-1$ . $b_{1}$ is $1$ then $b_{N}$ is $N-1$ .

For Pi, $a_{1}$ is 3 then $a_{N}$ is always $6$ . $b_{N}$ is $(2N-1)^{2}$ .

Ada

<lang Ada>with Ada.Text_IO; use Ada.Text_IO; procedure ContFract is

  type FormType is (Sqrt2, Napier, Pi);
  type Floaty is digits 15;
  package FIO is new Ada.Text_IO.Float_IO (Floaty);

  procedure GetCoefs (form : FormType; n : Natural;
     coefA : out Natural; coefB : out Natural)
  is begin
     case form is
        when Sqrt2 =>
           if n > 0 then coefA := 2; else coefA := 1; end if;
           coefB := 1;
        when Napier =>
           if n > 0 then coefA := n; else coefA := 2; end if;
           if n > 1 then coefB := n - 1; else coefB := 1; end if;
        when Pi =>
           if n > 0 then coefA := 6; else coefA := 3; end if;
           coefB := (2*n - 1)**2;
     end case;
  end GetCoefs;

  function Calc (form : FormType; n : Natural) return Floaty is
     A, B : Natural;
     Temp : Floaty := 0.0;
  begin
     for ni in reverse Natural range 1 .. n loop
        GetCoefs (form, ni, A, B);
        Temp := Floaty (B) / (Floaty (A) + Temp);
     end loop;
     GetCoefs (form, 0, A, B);
     return Floaty (A) + Temp;
  end Calc;

begin

  FIO.Put (Calc (Sqrt2, 200), Exp => 0); New_Line;
  FIO.Put (Calc (Napier, 200), Exp => 0); New_Line;
  FIO.Put (Calc (Pi, 200), Exp => 0); New_Line;

end ContFract; </lang>

Output:

 1.41421356237310
 2.71828182845905
 3.14159262280485

Go

<lang go>package main

import "fmt"

type cfTerm struct {

   a, b int

}

// follows subscript convention of mathworld and WP where there is no b(0). // cf[0].b is unused in this representation. type cf []cfTerm

func cfSqrt2(nTerms int) cf {

   f := make(cf, nTerms)
   for n := range f {
       f[n] = cfTerm{2, 1}
   }
   f[0].a = 1
   return f

}

func cfNap(nTerms int) cf {

   f := make(cf, nTerms)
   for n := range f {
       f[n] = cfTerm{n, n - 1}
   }
   f[0].a = 2
   f[1].b = 1
   return f

}

func cfPi(nTerms int) cf {

   f := make(cf, nTerms)
   for n := range f {
       g := 2*n - 1
       f[n] = cfTerm{6, g * g}
   }
   f[0].a = 3
   return f

}

func (f cf) real() (r float64) {

   for n := len(f) - 1; n > 0; n-- {
       r = float64(f[n].b) / (float64(f[n].a) + r)
   }
   return r + float64(f[0].a)

}

func main() {

   fmt.Println("sqrt2:", cfSqrt2(20).real())
   fmt.Println("nap:  ", cfNap(20).real())
   fmt.Println("pi:   ", cfPi(20).real())

}</lang>

Output:

sqrt2: 1.4142135623730965
nap:   2.7182818284590455
pi:    3.141623806667839

Haskell

<lang haskell>import Data.List (unfoldr) import Data.Char (intToDigit)

-- continued fraction represented as a (possibly infinite) list of pairs sqrt2, napier, myPi :: [(Integer, Integer)] sqrt2 = zip (1 : [2,2..]) [1,1..] napier = zip (2 : [1..]) (1 : [1..]) myPi = zip (3 : [6,6..]) (map (^2) [1,3..])

-- approximate a continued fraction after certain number of iterations approxCF :: (Integral a, Fractional b) => Int -> [(a, a)] -> b approxCF t =

 foldr (\(a,b) z -> fromIntegral a + fromIntegral b / z) 1 . take t

-- infinite decimal representation of a real number decString :: RealFrac a => a -> String decString frac = show i ++ '.' : decString' f where

 (i,f) = properFraction frac
 decString' = map intToDigit . unfoldr (Just . properFraction . (10*))

main :: IO () main = mapM_ (putStrLn . take 200 . decString .

             (approxCF 950 :: [(Integer, Integer)] -> Rational))
            [sqrt2, napier, myPi]</lang>

Output:

1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572735013846230912297024924836055850737212644121497099935831413222665927505592755799950501152782060571
2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019
3.141592653297590947683406834261190738869139611505752231394089152890909495973464508817163306557131591579057202097715021166512662872910519439747609829479577279606075707015622200744006783543589980682386

Python

<lang python># The continued Fraction def CF(a, b, t):

 if 0 < t:
   a1 = next(a)
   b1 = next(b)
   z  = CF(a, b, t-1)
   return (a1*z[0] + b1*z[1], z[0])
 return (1,1)

Convert the continued fraction to a string

def pRes(cf, d):

 res = str(cf[0] // cf[1])
 res += "."
 x = cf[0] % cf[1]
 while 0 < d:
   x *= 10
   res += str(x // cf[1])
   x = x % cf[1]
   d -= 1
 return res

Test the Continued Fraction for sqrt2

def sqrt2_a():

 yield 1
 while (True):
   yield 2

def sqrt2_b():

 while (True):
   yield 1

cf = CF(sqrt2_a(), sqrt2_b(), 950) print(pRes(cf, 200))

1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147

Test the Continued Fraction for Napier's Constant

def Napier_a():

 yield 2
 n = 1
 while (True):
   yield n
   n += 1

def Napier_b():

 n=1
 yield n
 while (True):
   yield n
   n += 1

cf = CF(Napier_a(), Napier_b(), 950) print(pRes(cf, 200))

2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193200305992181741359662904357290033429526059563073813232862794349076323382988075319525101901

Test the Continued Fraction for Pi

def Pi_a():

 yield 3
 while (True):
   yield 6

def Pi_b():

 x = 1
 while (True):
   yield x*x
   x += 2

cf = CF(Pi_a(), Pi_b(), 950) print(pRes(cf, 10))

3.1415926532</lang>