Реализация алгоритма для преобразования действительного числа в непрерывную дробь в #F

Question

Я пытаюсь реализовать рекурсивную функцию, которая принимает число с плавающей точкой и возвращает список целых чисел, представляющих непрерывное дробное представление числа с плавающей запятой ( 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..... [число]. Я просто не уверен, как выполнить сравнение. Как именно я должен идти об этом. Алгоритм, на котором основана функция, говорит, что базовый случай равен 0, поэтому я естественно интерпретирую это как 0.0. Я не вижу другого пути. Кроме того, обратите внимание, что это для назначения, где меня явно просят рекурсивно реализовать алгоритм. У кого-нибудь есть руководство для меня? Это будет высоко ценится

Answer 1

Кажется, значение r никогда не уменьшается до 0,0, а алгоритм продолжает возвращать значения, подобные 0,0..... [число].

Это классическая проблема со сравнениями с плавающей запятой. Вам нужно использовать какое-то значение толерантности эпсилон для сравнения, потому что r никогда не достигнет точно 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]

См. Эту документацию MSDN для получения дополнительной информации.

Вы можете определить вспомогательную функцию для этого:

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

Также обратите внимание, что ваше оригинальное решение не является хвостово-рекурсивным, поэтому оно потребляет стек по мере его повторения и может переполнить стек. Вы можете изменить его так, чтобы float может быть unfoldредактируется без рекурсии:

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]