高效的算法找到一个最大公约数最接近一定的价值？ [英] Efficient algorithm for finding a common divisor closest to some value?

问题描述

我有两个数字， X1 和 X2 。对于一些是，我想计算 X1 和 X2 尽可能接近到是。

I have two numbers, x1 and x2. For a number y, I want to calculate the common divisor of x1 and x2 as close as possible to y.

是否有一个有效的算法呢？

Is there an efficient algorithm for this?

我认为是时候改写我的问题，并得到更清晰的的。这是不是整数？ 所以，说我们有两个号 X1 和 X2 。这样说来，用户输入一个数是。我想找到，是一个数 Y'靠近是让 X1％ Y'和 X2％Y 非常小（小于 0.02 ，例如小，但让拨打此号码限制）。换句话说，我并不需要一个最佳的算法，但是一个很好的近似。

I believe it's time to rephrase my problem and be more clear. This is not about integers... So, say we have two numbers x1 and x2. Say, the user inputs a number y. What I want to find, is a number y' close to y so that x1 % y' and x2 % y' are very small (smaller than 0.02, for example, but lets call this number LIMIT). In other words, I don't need an optimal algorithm, but a good approximation.

我感谢大家的时间和精力，这真有种！

I thank you all for your time and effort, that's really kind!

推荐答案

我相信，没有已知的高效（多项式时间）算法对于这个问题，因为是从的整数分解这个问题。由于没有已知的多项式时间算法整数分解，不可能有一个已知的algortihm你的问题，或者，否则我们确实有一个多项式时间的算法为整数分解。

I believe that there is no known efficient (polynomial-time) algorithm for this problem because there is a polynomial-time reduction from integer factorization to this problem. Since there is no known polynomial-time algorithm for integer factorization, there cannot be a known algortihm for your problem either, since otherwise we would indeed have a polynomial-time algorithm for integer factorization.

要看到这是如何工作的，假设你有一个数n，你要的因素。现在，使用任何算法你想，发现n的共同因素和正最接近＆拉迪奇; N。由于n的不平凡除数可以大于＆拉迪奇; N，这个发现任一（1）的最大整数除以n或（2）的数目1，如果n是素数。然后您可以将N的这个数字，重复生产n的全部因素。由于n可以最多有O（log n）的因素，这需要最多多项式许多求解你的问题的重复，因此我们必须从整数分解一个多项式时间减少到了这个问题。如上所述，这意味着，至少在公开文献中，没有任何已知的有效的经典算法用于解决该问题。有人可能会存在，但它是一个非常非常重要的结果。

To see how this works, suppose you have a number n that you'd like to factor. Now, using whatever algorithm you'd like, find the common factor of n and n closest to √n. Since no nontrivial divisor of n can be greater than √n, this finds either (1) the largest integer that divides n, or (2) the number 1 if n is prime. You can then divide n by this number and repeat to produce all the factors of n. Since n can have at most O(log n) factors, this requires at most polynomially many iterations of the solver for your problem, so we have a polynomial-time reduction from integer factorization to this problem. As mentioned above, this means that, at least in the open literature, there is no known efficient classical algorithm for solving this problem. One might exist, but it would be a really hugely important result.

抱歉了否定的回答，并希望这有助于！

Sorry for the negative answer, and hope this helps!

这篇关于高效的算法找到一个最大公约数最接近一定的价值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！