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.