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
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 unfold
ed 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]