测试十进制是否足够接近有理数

给定一个十进制x,我想测试x是否在分母9999或更小的有理数的10^-12之内。显然,我可以通过查看x,2x,3x等来查看它们是否足够接近整数。但是有没有更高效的算法?测试十进制是否足够接近有理数

回答:

有一种算法叫做continued fraction algorithm,它会给你一定的意义上的“最佳”有理逼近。当分母超过9999时,可以停止,然后返回到前一个收敛,并比较它是否足够接近。当然,如果小数点是一个足够小的有理数,算法会提前终止。

回答:

所以,几件事情:

我认为用“十进制X”你指的是一些浮点表示X。也就是说,你打算以某种格式来实现这个功能,而这种格式实际上不能完全代表.1或1/3等。如果你是通过手工或其他方式来表达小数的方式,不适用。

其次,您是否与这些具体的分母和容差相关联?我问,因为如果你对2的幂是可以的(例如分母高达8192,容忍度为2^-35),你可以很容易地利用IEEE-754风格浮点都是有理数的事实。使用指数来确定尾数中的哪个数字对应于2^-13,然后确保尾数的后22位数字为0(或者如果精度不够高,以至于超过该点,则包括22),则最多为22。如果是这样,你就明白了。

现在,如果你不想改变你的算法来使用基2,你至少可以用它来缩小它,并做一些消除。

回答:

我看到你已经接受了一个答案,但我仍然要去响一声。

蛮力法不需要检查每个分母。如果你反向工作,不仅可以消除你刚刚检查的数字,而且可以消除每个因素。例如,一旦你检查了9999,你不需要检查3333,1111,909,303,101,99,33,11,9,3或1;如果数字可以表示为其中一个数字的一​​小部分,那么它也可以表示为9999的一小部分。结果是5000以下的每个数字至少是一个数字5000到9999的因数,所以您已经切割了你的搜索空间减半。

编辑︰我发现这个问题足够有趣的代码在Python解决方案。

def gcd(a, b): 

if b == 0:

return a

return gcd(b, a % b)

def simplify(fraction_tuple):

divisor = gcd(fraction_tuple[0], fraction_tuple[1])

return fraction_tuple[0]/divisor, fraction_tuple[1]/divisor

def closest_fraction(value, max_denominator=9999, tolerance=1e-12, enforce_tolerance=False):

best_error, best_result = abs(value), (0,1)

for denominator in range(max_denominator/2+1, max_denominator+1):

numerator = round(value * denominator)

error = abs(value - (numerator/denominator))

if error < best_error:

best_error = error

best_result = int(numerator), denominator

if error <= tolerance:

break

if enforce_tolerance and best_error > tolerance:

return None

return simplify(best_result)

以上是 测试十进制是否足够接近有理数 的全部内容, 来源链接: utcz.com/qa/267313.html

回到顶部