Эффективный алгоритм для нахождения общего делителя, ближайшего к некоторому значению?

Question

У меня есть два числа, x1 и x2. Для числа y я хочу вычислить общий делитель x1 и x2 как можно ближе к y.

Есть ли эффективный алгоритм для этого?

---

Я считаю, что пришло время перефразировать мою проблему и быть более ясным . Это не о целых числах ... Итак, скажем, у нас есть два числа x1 и x2. Скажем, пользователь вводит число y. То, что я хочу найти, - это число y', близкое к y, так что x1 % y' и x2 % y' очень малы (например, меньше, чем 0.02, но давайте назовем этот номер LIMIT). Другими словами, мне не нужен оптимальный алгоритм, но хорошее приближение.

Я благодарю всех за потраченное время и усилия, это очень мило!

Answer 1

Я полагаю, что не существует известного эффективного (полиномиального) алгоритма для этой задачи, поскольку существует полиномиальное сокращение времени от целочисленной факторизации до этой проблемы.Поскольку не существует известного алгоритма полиномиального времени для целочисленной факторизации, также не может быть известного алгоритма для вашей задачи, поскольку в противном случае у нас действительно был бы алгоритм полиномиального времени для целочисленной факторизации.

Чтобы увидеть, как это работаетПредположим, у вас есть номер n, который вы хотели бы принять.Теперь, используя любой алгоритм, который вы хотите, найдите общий множитель n и n, ближайший к √n.Поскольку нетривиальный делитель числа n не может быть больше, чем √n, он находит либо (1) наибольшее целое число, которое делит n, либо (2) число 1, если n простое число.Затем вы можете разделить n на это число и повторить, чтобы получить все факторы n.Поскольку n может иметь не более O (log n) факторов, для этого требуется не более полиномиального количества итераций решателя для вашей задачи, поэтому мы имеем сокращение за полиномиальное время от целочисленной факторизации до этой задачи.Как упомянуто выше, это означает, что, по крайней мере в открытой литературе, не существует известного эффективного классического алгоритма для решения этой проблемы.Кто-то может существовать, но это будет действительно очень важный результат.

Извините за отрицательный ответ, и надеюсь, что это поможет!

Answer 2

Это эффективно, поскольку я могу получить это:

from fractions import gcd
primes=[i for i in range(2,1000) if all(i%j!=0 for j in range(2,i))] #ensure you have enough primes.. (can improve efficency here)


def f(x1,x2,y):
    _gcd=gcd(x1,x2)
    if _gcd==1:
        return 1
    factors=(i for i in range(2,_gcd+1) if _gcd%i==0) #can improve efficiency here.. e.g. only go up to root(gcd)
    r1=999999999
    r2=999999999
    for i in factors:
        r1=min(r1,y%i)
        r2=min(r2,i-y%i)
    return y-r1 if r1<=r2 else y+r2


print f(8,4,3)
print f(16,12,5)
print f(997,53,44)
print f(2300*2,2300*3,57)

"""
2
4
1
56
"""

Answer 3

Я думаю, что вы можете сделать это с помощью жадного алгоритма, сначала найдите GCD с помощью общих алгоритмов, назовите его d (который вычисляется в логарифмическом времени), затем найдите коэффициенты d каждый раз, делите d на наименьший доступный коэффициент ( создайте d') и сравните |d'-y| с |d-y|, если меньше, продолжайте таким же образом (и замените d' на d), иначе умножьте d' на наименьший исключенный коэффициент и снова сравните его расстояние к тебе

Answer 4

1. Найти GCD из x1 и x2.
2. Если GCD <= Y, вернуть GCD
3. Текущий лучший ответ - GCD, с наилучшим расстоянием GCD - y.
4. Итерация по всем числам Y +/ - [0 ... наилучшее расстояние]
5. Возвращает первое целое число, кратное x1 и x2

Чтобы найти GCD

public int getGCD( int a, int b )
{
   return (b==0) ? a : gcd(b, a%b);
}

Чтобы найти ближайший к y делитель ...

public int closestDivisor( int a, int b, int y ){
    int gcd = getGCD( a, b );
    if( gcd <= y ) return gcd;
    int best = gcd - y;
    for( int i = 0; i < best; i++ )
    {
        if( gcd % (i-y) == 0 ) return i - y;
        if( gcd % (i+y) == 0 ) return i + y;
    }
    return gcd;
}

Я полагаю, что единственной доступной дополнительной оптимизацией будет факторизация gcd (возможно, с использованием сита?), Как предложено @trinithis.