Is it possible to calculate the continued fraction of a negative number in f#?

Question

I'm trying to make a program that can calculate the calculated fraction of a real number. It works completely fine except when I'm trying to do it for a negative real number, ex "-71/23" or in decimals "-3,086...".

If I calculate the continued fraction of +71/23, I get [3; 11; 2]. This is correct. As far as I've understood, If I then try to do it for -71/23, I should get the same int list, but with the first element being negative (works by pen & paper). So that should be [-3; 11; 2]. But its not working out. I'm getting [-3; -11; -1; -1], which is every number negative plus one extra negative number.

I think that I need to make a branch where I tell the function that only the first number of the int list is allowed to be negative - the rest should be returned positive. I've tried different stuff, but I'm not sure how to work it out.

This is homework by the way.

Thanks in advance, Zebraboard

let rec float2cfrac (x : float) : int list =
    let q = int x
    let r = x - (float q)
    match x with 
    | _ when r < 0.000000001 && r > -0.000000001 -> [q]
    | _ when System.Math.Ceiling(x) - x <0.0001 -> [int (x + 1.0)]
    | _ when q < 0 -> [-q] // this is the line where I want to do it, not sure what to do tho 
    | _ -> q :: float2cfrac (1.0 / r)

printfn "%A" (float2cfrac (-71.0/23.0))

Edit: Moved code with comment and changed format of the code.

Edit: I have now found the solution after lots of work :D simply add an extra line that says that if x is negative then -q instead of q :) Also see the comment below that I have accepted as an answer, you need to change and add some functions :)

  | _ when x < 0.0 -> -q :: float2cfrac (1.0 / r)   

Answer 1

I would just take the absolute value, then apply the sign at the end:

let rec float2cfrac (x : float) : int list =
  let safeX = abs x
  let signX = sign x
  let q = int safeX
  let r = safeX - (float q)
  match x with 
  | _ when r < 0.000000001 && r > -0.000000001 -> [q]
  | _ when System.Math.Ceiling(safeX) - safeX <0.0001 -> [int (safeX + 1.0)]
  | _ -> q :: float2cfrac (1.0 / r)
  |> List.map ( fun rawQ -> rawQ * signX )

From fsi:

> float2cfrac (71./23.);;                                                                                                                    
  val it : int list = [3; 11; 2]                                                                                                                                                                                                                  
> float2cfrac (-71./23.);;                                                                                                                    
  val it : int list = [-3; -11; -2]                                                                                                                           

Answer 2

The code above is calculating correctly, but I think the problem is that the function has to get this output [-3; 11; 2], so only the first number will be negative :D Is there any way to do it? solved

Answer 3

Of course. In any language you can do that.

Once you know the coefficients of the positive rational then just a simple manipulation on it's coefficients would negate it. Keep in mind that in order to make it a legal CF all tailing coefficients (the ones after semicolon) should be positive.

However before jumping into the conclusion lets first see what is a negative fraction. Let x be a fraction with integral part w and fraction part f. We can write it like;

-x =  w + f where 0 < f < 1
 x = -w - f

However fractions are always expressed as a sum like w + f. I mean when we write like 2¾ we mean 2 + 3/4 where w is 2 and f is 3/4. In order to convert it to negated proper sum notation we do like;

 x = (-w - 1) + (1 - f)

which yields the negation of 2¾ to be (-2-1)+(1-3/4) = -3 + 1/4 right?

So now everything is straightforward. We already have the w part as -3. So lets calculate CF coefficients of the f part (1/4) and it is [0;4]. Now obviously we just need to add w to the a0 (the head) of the coefficients yielding [-3;4] which, as a side note, is also equivalent to [-3;3,1] but don't think about this now.

This is as simple as shown above however it gets even simpler. Remember i mentioned a direct manipulation of the input rational's coefficients to negate it. To keep the answer in reasonable length i will bypass the proof but the rule is like;

x is a continued fraction and [a0; a1, a2, ...an] are it's coefficients. Then

x = [a0, a1, a2, a3, ...] ⇒ −x = [−a0 − 1, 1, a1 − 1, a2, a3, ...]

So this is it. Coming back to your question. +71/23 is in fact 3 + 2/23 with coefficients like [3; 11, 2] then according to the above rule a negation would turn it's coefficients into [-3-1; 1, 11-1, 2] which is [-4;1,10,2] or [-4;1,10,1,1]. In sum notation -4 + 21/23.

Note: In the above negation formula, if the a1 - 1 term turns out to be 0 (if a1 = 1) then you can eliminate it (0) and add the previous value (1) with the next value (a2) and merge them. In general any continued fraction in the form of [a0, a1, 0, a3,..., an] should be written like [a0,a1+a3,a4,...,an].