测试十进制是否足够接近有理数
给定一个十进制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