实现一种算法，将实数转换为 #F 中的连分数

Question

我正在尝试实现一个递归函数，它接受一个浮点数和 returns 一个表示浮点数连续分数表示的整数列表（https://en.wikipedia.org/wiki/Continued_fraction）一般来说，我想我理解算法应该工作。它相当简单。我到目前为止是这样的：

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 ))

问题显然出在基本案例上。似乎值 r 永远不会减少到 0.0，而是算法继续返回类似 0.0.....[number] 的值。我只是不确定如何进行比较。我到底应该怎么做。该函数所基于的算法说基本情况是 0，所以我自然地将其解释为 0.0。我没有看到任何其他方式。另外，请注意，这是针对我被明确要求以递归方式实现算法的分配。有人对我有指导吗？将不胜感激

Answer 1

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].

这是浮点数比较的经典问题。您需要使用一些 epsilon 公差值进行比较，因为 r 永远不会达到 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]

有关更多信息，请参阅 this MSDN documentation。

您可以为此定义一个辅助函数：

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

另请注意，您的原始解决方案不是 tail-recursive，因此它会在递归时消耗堆栈并可能溢出堆栈。您可以重构它，这样 float 就可以 unfolded 而无需递归：

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]

实现一种算法，将实数转换为 #F 中的连分数

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

recursion

f#

continued-fractions