implementing an algorithm to transform a real number to a continued fraction in #F

Question

i am trying to implement a recursive function which takes a float and returns a list of ints representing the continued fraction representation of the float (https://en.wikipedia.org/wiki/Continued_fraction) In general i think i understand how the algorithm is supposed to work. its fairly simply. What i have so far is this:

let rec float2cfrac (x : float) : int list = 
    let q = int x
    let r = x - (float q)
    if r = 0.0 then
         []
    else 
         q :: (float2cfrac (1.0 / r ))

the problem is with the base case obviously. It seems the value r never does reduce to 0.0 instead the algorithm keeps on returning values which are the likes of 0.0.....[number]. I am just not sure how to perform the comparison. How exactly should i go about it. The algorithm the function is based on says the base case is 0, so i naturally interpret this as 0.0. I dont see any other way. Also, do note that this is for an assignment where i am explicitly asked to implement the algorithm recursively. Does anyone have some guidance for me? It would be much appreciated

Taylor Wood · Accepted Answer · 2018-03-17T13:11:34.533

It seems the value r never does reduce to 0.0 instead the algorithm keeps on returning values which are the likes of 0.0.....[number].

This is a classic issue with floating point comparisons. You need to use some epsilon tolerance value for comparisons, because r will never reach exactly 0.0:

let epsilon = 0.0000000001
let rec float2cfrac (x : float) : int list =
  let q = int x
  let r = x - (float q)
  if r < epsilon then
    []
  else 
    q :: (float2cfrac (1.0 / r))

> float2cfrac 4.23
val it : int list = [4; 4; 2; 1]

See this MSDN documentation for more.

You could define a helper function for this:

let withinTolerance (x: float) (y: float) e =
  System.Math.Abs(x - y) < e

Also note your original solution isn't tail-recursive, so it consumes stack as it recurses and could overflow the stack. You could refactor it such that a float can be unfolded without recursion:

let float2cfrac (x: float) =
  let q = int x
  let r = x - (float q)
  if withinTolerance r 0.0 epsilon then None
  else Some (q, (1.0 / r))

4.23 |> Seq.unfold float2cfrac // seq [4; 4; 2; 1]

implementing an algorithm to transform a real number to a continued fraction in #F

1 Answers1