# F# and Continued Fractions

As an exercise in F# and a refresher on Continued Fractions, I decided to put together some functions in F# for converting scalar values into their (Simple) Continued Fraction form, and vice versa.

My approach for converting from Continued Fraction form to scalar was to utilize F#'s List.foldBack function to accumulate the denominators starting at the deepest level and moving "up". Rather than writing a special case for the terminal (innermost) fraction, I chose to seed the (general) accumulation with Double.MaxValue, amounting to 1.0 / (aLargeValue) or approximately 0 added to the innermost fraction.

For converting from a scalar value to Continued Fraction form, I devised a recursive function (which should, I hope, receive a tail recursion optimization) that constructs the sequence starting at the "top" and moving downward, following the basic algorithm outlined at the Wikipedia page. One of the exit conditions (if this were exact) is to check for a 0 fractional value, however due to numerical error I loosened this check to 0 + 0.1% of the most recent integer term.

## Code

(* functions *) /// <summary>Converts a number from continued fraction representation to a scalar (binary float) representation.</summary> let cfToScalar cf = List.foldBack (fun elem acc -> float elem + (1.0 / float acc)) cf System.Double.MaxValue /// <summary>Converts a number from scalar (binary float) representation to a continued fraction representation.</summary> let rec scalarToCF (s:float) (maxIters:int) = if maxIters = 0 then Seq.empty else let term = floor s let fraction = (s - term) if fraction < 0.001 * term then Seq.singleton (int term) else let fractionInv = 1.0 / fraction Seq.append (Seq.singleton (int term)) (scalarToCF fractionInv (maxIters-1))

## Test

(* testing *) open System let piAsCFFromWolframAlpha = Array.toList [|3; 7; 15; 1; 292; 1; 1; 1; 2; 1; 3; 1; 14; 2; 1; 1; 2; 2; 2; 2; 1; 84; 2; 1; 1;|] let piAsScalarFromDotNet = Math.PI printfn "π (.NET Framework): %f\n" piAsScalarFromDotNet printfn "π CF (WolframAlpha): %A\n" piAsCFFromWolframAlpha printfn "π (cfToScalar): %f\n" (cfToScalar piAsCFFromWolframAlpha) printfn "π (scalarToCF): %A\n" (Seq.toList (scalarToCF piAsScalarFromDotNet 10)) let rational = 17.0/24.0 let rationalAsCFFromWolframAlpha = Array.toList [|0;1;2;2;3|] printfn "17/24: %f\n" rational printfn "17/24 CF (WolframAlpha): %A\n" rationalAsCFFromWolframAlpha printfn "17/24 (cfToScalar): %f\n" (cfToScalar rationalAsCFFromWolframAlpha) printfn "17/24 (scalarToCF): %A\n" (Seq.toList (scalarToCF rational 10)) Console.WriteLine "Press any key." let x = Console.ReadKey() Console.Write ""

## Test Output

π (.NET Framework): 3.141593 π CF (WolframAlpha): [3; 7; 15; 1; 292; 1; 1; 1; 2; 1; 3; 1; 14; 2; 1; 1; 2; 2; 2; 2; 1; 84; 2; 1; 1] π (cfToScalar): 3.141593 π (scalarToCF): [3; 7; 15; 1; 292; 1; 1; 1; 2; 1] 17/24: 0.708333 17/24 CF (WolframAlpha): [0; 1; 2; 2; 3] 17/24 (cfToScalar): 0.708333 17/24 (scalarToCF): [0; 1; 2; 2; 3] Press any key.