OCaml浮点转分数函数异常：3.142857143陷入无限递归求助

无限递归且无栈错误的原因 #

• 浮点数精度限制：输入的3.142857143是22/7（≈3.142857142857...）的近似值，并非精确相等。浮点数的二进制存储无法精确表示所有十进制小数，导致x * y永远无法严格等于其向下取整的值，r(y)始终为假，递归永远不会终止。
• 尾递归优化：你的f函数是尾递归（递归调用是函数的最后一个操作），OCaml会将尾递归优化为循环，不会消耗栈空间，因此不会触发栈溢出错误。

现有代码的其他问题 #

• 未约分问题：f函数仅找到满足x*y为整数的最小y，但不会对结果约分，比如f 0.14得到(35.0,250.0)，未约分为(7.0,50.0)。
• 约分函数g的缺陷：使用浮点数运算判断整除性，同样会受精度问题影响；且递归逻辑冗余，效率低下。

解决方案 #

核心思路：用精确整数运算替代浮点数判断 #

浮点数的精度问题是核心痛点，应该将浮点数转换为精确的整数分子分母对，再进行约分。

实现代码 #

1. 整数版最大公约数（GCD）函数

let rec gcd a b =
  if b = 0 then a else gcd b (a mod b)

2. 浮点数转约分后的分子分母（整数对）

let float_to_fraction x =
  let integer_part = int_of_float x in
  let fractional_part = x -. float_of_int integer_part in
  (* 处理纯整数情况 *)
  if fractional_part = 0.0 then
    (integer_part, 1)
  else
    (* 找到足够多的10的幂次，将小数部分转为整数 *)
    let rec find_multiplier m =
      let scaled = fractional_part *. float_of_int m in
      if scaled = float_of_int (int_of_float scaled) then m
      else find_multiplier (m * 10)
    in
    let multiplier = find_multiplier 10 in
    let numerator = integer_part * multiplier + int_of_float (fractional_part *. float_of_int multiplier) in
    let denominator = multiplier in
    (* 约分 *)
    let common_divisor = gcd numerator denominator in
    (numerator / common_divisor, denominator / common_divisor)

3. 测试示例

float_to_fraction 0.2;;
(* - : int * int = (1, 5) *)

float_to_fraction 3.14;;
(* - : int * int = (157, 50) *)

float_to_fraction 0.14;;
(* - : int * int = (7, 50) *)

float_to_fraction (22. /. 7.);;
(* - : int * int = (22, 7) *)

处理近似浮点数的补充方案 #

如果输入是无理数或无法精确表示的有理数近似值（如3.142857143），可以设置精度阈值，判断乘积与整数的差值是否足够小：

let float_to_fraction_with_tolerance x tolerance =
  let integer_part = int_of_float x in
  let fractional_part = x -. float_of_int integer_part in
  if fractional_part < tolerance then
    (integer_part, 1)
  else
    let rec find_y y =
      let product = x *. y in
      let rounded = float_of_int (int_of_float (product +. 0.5)) in
      if abs_float (product -. rounded) < tolerance then
        (int_of_float rounded, int_of_float y)
      else
        find_y (y +. 1.0)
    in
    let (num, den) = find_y 1.0 in
    let common_divisor = gcd num den in
    (num / common_divisor, den / common_divisor)

测试：

float_to_fraction_with_tolerance 3.142857143 1e-6;;
(* - : int * int = (22, 7) *)

内容的提问来源于stack exchange，提问作者Iter