我正在寻找一种将浮点数转换为有理数的算法，以保证有理数返回到原始浮点数，并且分母最小化。
一个简单的算法可以将浮点数的实际值返回为 X / 2 N，但是对于任何不是有限二进制分数的东西来说，2 N往往是相当大的。例如，数字 0.1，当存储在双精度浮点数中时，实际上近似为 ³⁶⁰²⁸⁷⁹⁷⁰¹⁸⁹⁶³⁹⁷⁄₃₆₀₂₈₇₉₇₀₁₈₉₆₃₉₆₈ ） （分母为 2 55 但是，将 0.1 转换为 ¹⁄₁₀ 显然更好，并且 ¹⁄₁₀ 将评估为 ³⁶⁰²⁸⁷⁹⁷⁰¹⁸⁹⁶³⁹⁷⁄₃₆₀₂₈₇₉₇₀₁₈₉₆₃₉₆₈
一个相关的问题是用最少的数字打印十进制浮点数（本文描述了一些技术），这可以被认为是这个问题的一个特殊版本，具有一个额外的约束，即分母必须是 10 的幂。
有一个现有的问题，可能更多，但它们没有转换后的有理数必须评估为原始浮点数的约束。
让我们从一个定义开始，该定义准确地确定在任何特定情况下我们正在寻找的分数：
定义。 假设一个分数比另一个分数
a/b更简单c/d（两个分数都用最低术语写，分母为正）如果b <= d,abs(a) <= abs(c)，并且这两个不等式中至少有一个是严格的。
例如5/7比 更简单6/7，并且5/7比 更简单5/8，但两者2/5都不3/4比另一个更简单。（我们这里没有总订购量。）
然后有了这个定义，有一个不是立即显而易见的定理，它保证我们正在寻找的分数总是存在的：
定理。给定
J包含至少一个分数的实数子区间，J包含唯一的最简单 分数。换句话说，有一个独特的分数f，使得
f在J并且，- 对于 中的任何其他分数
g，都比 更简单。Jfg
特别是，如问题所要求的，区间中最简单的分数总是具有最小可能的分母。定理中的“包含至少一个分数”条件是为了排除像闭区间这样的退化情况[√2, √2]，它根本不包含任何分数。
我们的工作是编写一个函数，该函数接受一个有限浮点输入，并以目标浮点格式返回与 最接近的浮点数的x最简单分数。假设一个合理的浮点格式和舍入模式，四舍五入的实数集将形成实线的非空子区间，具有有理端点。所以我们的问题自然分解为两个子问题：n/dxn/dx
问题 1.给定x目标浮点格式的浮点数，描述在x该浮点格式规则下四舍五入的所有值的间隔。这涉及识别该区间的端点并确定该区间是开放的、封闭的还是半开放的。
问题 2.给定具有有理端点的实线的非空子区间J，计算该子区间中的最简单分数。
第二个问题更有趣，对平台和语言细节的依赖更少；让我们先解决这个问题。
假设 IEEE 754 浮点格式和默认的舍入到偶数舍入模式，对给定浮点数的区间舍入将是开放的或封闭的；对于其他舍入模式或格式，它可能是半开的（一端打开，另一端关闭）。所以对于本节，我们只关注开区间和闭区间，但适应半开区间并不难。
假设它J是具有有理端点的实线的非空子区间。为简单起见，我们假设它J是正实线的子区间。如果不是，那么它要么包含0（在这种情况下0/1是最简单的分数），J要么是负实数线的子区间，我们可以求反，找到最简单的分数，然后取反。
然后下面给出了一个简单的递归算法来找到 中的最简单的分数J：
1，则1/1是 中最简单的分数JJ是 的子区间(0, 1)，则 中的最简分数J是1/f，其中f是 中的最简分数1/J。（这是从“最简单”的定义中直接得出的。）J必须是 的子区间(1, ∞)，并且 中的最简分数J是q + f，其中是仍在正实数范围内q的最大整数，并且是 中的最简分数。J - qfJ - q对于最后一个陈述的证明草图：如果a / b是 中的最简单的分数，J并且c / d是 中的最简单的分数J - q，则a / b比或等于 更简单(c + qd) / d，并且c / d比或等于 更简单(a - qb) / b。所以b <= d, a <= c + qd,d <= b和c <= a - qb, 然后是 ,b = d和a = c + qd, 所以c / d = a / b - q。
在类似 Python 的伪代码中：
def simplest_in_interval(J):
# Simplest fraction in a subinterval J of the positive reals
if J < 1:
return 1 / simplest_in_interval(1/J)
else if 1 < J:
q = largest_integer_to_the_left_of(J)
return q + simplest_in_interval(J - q)
else:
# If we get here then J contains 1.
return 1
要看到算法必须总是终止并且不能进入无限循环，注意每一个反演步骤后面必须跟着一个J - q步骤，并且每J - q一步都会减少区间左右端点的分子。具体来说，如果区间的端点是a/b和c/d，则和abs(a) + abs(c) + b + d是一个正整数，随着算法的进行而稳步减小。
要将上述内容转换为真正的 Python 代码，我们必须处理一些细节。首先，我们现在假设这J是一个封闭区间；我们将适应下面的开放区间。
我们将用它的端点left和来表示我们的区间right，这两个都是正fraction.Fraction实例。然后下面的 Python 代码实现了上述算法。
from fractions import Fraction
from math import ceil
def simplest_in_closed_interval(left, right):
"""
Simplest fraction in [left, right], assuming 0 < left <= right < ∞.
"""
if right < 1: # J ⊂ (0, 1)
return 1 / simplest_in_closed_interval(1 / right, 1 / left)
elif 1 < left: # J ⊂ (1, ∞):
q = ceil(left) - 1 # largest q satisfying q < left
return q + simplest_in_closed_interval(left - q, right - q)
else: # left <= 1 <= right, so 1 ∈ J
return Fraction(1)
这是一个示例运行：
>>> simplest_in_closed_interval(Fraction("3.14"), Fraction("3.15"))
Fraction(22, 7)
原则上，开区间的代码同样简单，但实际上有一个复杂的问题：我们可能需要处理无限区间。例如，如果我们的原始区间是J = (2, 5/2)，那么第一步将该区间移动2得到(0, 1/2)，然后将该区间倒置得到(2, ∞)。
所以对于开区间，我们将继续用它的一对(left, right)端点来表示我们的区间，但现在right要么是一个fractions.Fraction实例，要么是一个特殊的常量INFINITY。而不是简单地1 / left用来取左端点的倒数，我们需要一个辅助函数来计算分数或 的倒数INFINITY，以及另一个用于减法的辅助函数，确保INFINITY - q给出INFINITY。以下是这些辅助功能：
#: Constant used to represent an unbounded interval
INFINITY = "infinity"
def reciprocal(f):
""" 1 / f, for f either a nonnegative fraction or ∞ """
if f == INFINITY:
return 0
elif f == 0:
return INFINITY
else:
return 1 / f
def shift(f, q):
""" f - q, for f either a nonnegative fraction or ∞ """
if f == INFINITY:
return INFINITY
else:
return f - q
这是主要功能。注意ifandelif条件中不等式的变化，以及我们现在想要使用floor(left)而不是ceil(left) - 1找到q位于区间左侧的最大整数的事实：
from fractions import Fraction
from math import floor
def simplest_in_open_interval(left, right):
"""
Simplest fraction in (left, right), assuming 0 <= left < right <= ∞.
"""
if 1 <= left: # J ⊆ (1, ∞):
q = floor(left)
return q + simplest_in_open_interval(shift(left, q), shift(right, q))
elif right != INFINITY and right <= 1: # J ⊆ (0, 1)
return 1 / simplest_in_open_interval(reciprocal(right), reciprocal(left))
else: # left < 1 < right, so 1 ∈ J
return Fraction(1)
上面的代码是为了清晰而不是效率而优化的：它在大复杂度方面相当有效，但在实现细节方面却不是。我把它留给读者转换成更有效的东西。第一步是使用整数分子和分母，而不是fractions.Fraction实例。如果您对它的外观感兴趣，请查看我在 PyPI 上的simplefractions包中的实现。
现在我们可以找到给定区间内的最简单分数，我们需要解决问题的另一半：找到四舍五入到给定浮点数的区间。这样做的细节在很大程度上取决于语言、使用的浮点格式，甚至是使用的舍入模式。
在这里，我们概述了一种在 Python 中执行此操作的方法，假设 IEEE 754 binary64 浮点格式具有默认的舍入到偶数舍入模式。
为简单起见，假设我们的输入浮点数x是正数（并且是有限的）。
Python >= 3.9 提供了一个函数math.nextafter，允许我们从x. 下面是一个对最接近 π 的浮点数执行此操作的示例：
>>> import math
>>> x = 3.141592653589793
>>> x_plus = math.nextafter(x, math.inf)
>>> x_minus = math.nextafter(x, 0.0)
>>> x_plus, x_minus
(3.1415926535897936, 3.1415926535897927)
x（请注意，通常要做到这一点，我们还需要处理最大可表示浮点数并math.nextafter(x, math.inf)给出无穷大的特殊情况。）
四舍五入到的区间的边界在与相邻浮点数x的中间。xPython 允许我们将浮点数转换为相应的精确值作为分数：
>>> from fractions import Fraction
>>> left = (Fraction(x) + Fraction(x_minus)) / 2
>>> right = (Fraction(x) + Fraction(x_plus)) / 2
>>> print(left, right)
14148475504056879/4503599627370496 14148475504056881/4503599627370496
我们还需要知道我们是否有一个封闭或开放的区间。我们可以查看位表示来解决这个问题（这取决于浮点数的最低有效位是0还是1），或者我们可以测试一下我们的区间端点是否舍入x：
>>> float(left) == x
True
>>> float(right) == x
True
他们这样做了，所以我们有一个封闭的区间。通过查看浮点数的十六进制表示可以证实这一点：
>>> x.hex()
'0x1.921fb54442d18p+1'
所以我们可以找到四舍五入到xusing的最简单的分数simplest_in_closed_interval：
>>> simplest_in_closed_interval(left, right)
Fraction(245850922, 78256779)
>>> 245850922 / 78256779 == x
True
虽然核心算法很简单，但有足够多的极端情况需要处理（负值、开区间与闭区间sys.float_info.max等），以至于一个完整的解决方案最终有点过于混乱，无法在此答案中完整发布。前段时间，我整理了一个 Python 包simplefractions，用于处理所有这些极端情况。它在 PyPI 上可用。这是在行动：
>>> from simplefractions import simplest_from_float
>>> simplest_from_float(0.1)
Fraction(1, 10)
>>> simplest_from_float(-3.3333333333333333)
Fraction(-10, 3)
>>> simplest_from_float(22/7)
Fraction(22, 7)
>>> import math
>>> simplest_from_float(math.pi)
Fraction(245850922, 78256779)