continued fraction
Mathworld





a

0


+









b

1












a

1


+









b

2












a

2


+









b

3












a

3


+
⋱

















{\displaystyle a_{0}+{\cfrac {b_{1}}{a_{1}+{\cfrac {b_{2}}{a_{2}+{\cfrac {b_{3}}{a_{3}+\ddots }}}}}}}


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, using the following coefficients:

For the square root of 2, use 




a

0


=
1


{\displaystyle a_{0}=1}

 then 




a

N


=
2


{\displaystyle a_{N}=2}

. 




b

N




{\displaystyle b_{N}}

 is always 



1


{\displaystyle 1}

.







2


=
1
+








1









2
+








1









2
+








1









2
+
⋱

















{\displaystyle {\sqrt {2}}=1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2+\ddots }}}}}}}


For Napier's Constant, use 




a

0


=
2


{\displaystyle a_{0}=2}

, then 




a

N


=
N


{\displaystyle a_{N}=N}

. 




b

1


=
1


{\displaystyle b_{1}=1}

 then 




b

N


=
N
−
1


{\displaystyle b_{N}=N-1}

.





e
=
2
+








1









1
+








1









2
+








2









3
+








3









4
+
⋱






















{\displaystyle e=2+{\cfrac {1}{1+{\cfrac {1}{2+{\cfrac {2}{3+{\cfrac {3}{4+\ddots }}}}}}}}}


For Pi, use 




a

0


=
3


{\displaystyle a_{0}=3}

 then 




a

N


=
6


{\displaystyle a_{N}=6}

. 




b

N


=
(
2
N
−
1

)

2




{\displaystyle b_{N}=(2N-1)^{2}}

.





π
=
3
+








1









6
+








9









6
+








25









6
+
⋱

















{\displaystyle \pi =3+{\cfrac {1}{6+{\cfrac {9}{6+{\cfrac {25}{6+\ddots }}}}}}}




See also

   Continued fraction/Arithmetic for tasks that do arithmetic over continued fractions.


object CF extends App {
  import Stream._
  val sqrt2 = 1 #:: from(2,0) zip from(1,0)
  val napier = 2 #:: from(1) zip (1 #:: from(1))
  val pi = 3 #:: from(6,0) zip (from(1,2) map {x=>x*x})
 
  // reference values, source: wikipedia
  val refPi     = "3.14159265358979323846264338327950288419716939937510"
  val refNapier = "2.71828182845904523536028747135266249775724709369995"
  val refSQRT2  = "1.41421356237309504880168872420969807856967187537694"
 
  def calc(cf: Stream[(Int, Int)], numberOfIters: Int=200): BigDecimal = {
    (cf take numberOfIters toList).foldRight[BigDecimal](1)((a, z) => a._1+a._2/z)
  }
 
  def approx(cfV: BigDecimal, cfRefV: String): String = {
    val p: Pair[Char,Char] => Boolean = pair =>(pair._1==pair._2)
    ((cfV.toString+" "*34).substring(0,34) zip cfRefV.toString.substring(0,34))
      .takeWhile(p).foldRight[String]("")((a:Pair[Char,Char],z)=>a._1+z)
  }
 
  List(("sqrt2",sqrt2,50,refSQRT2),("napier",napier,50,refNapier),("pi",pi,3000,refPi)) foreach {t=>
    val (name,cf,iters,refV) = t
    val cfV = calc(cf,iters)
    println(name+":")
    println("ref value: "+refV.substring(0,34))
    println("cf value:  "+(cfV.toString+" "*34).substring(0,34))
    println("precision: "+approx(cfV,refV))
    println()
  }
}