Efektywny algorytm znajdowania wspólnego dzielnika najbliżej pewnej wartości?

Question

Mam dwie liczby, x1 i x2. Dla numeru y, chcę obliczyć wspólny dzielnik x1 i x2 jak najbliżej y.

Czy istnieje skuteczny algorytm dla tego?

---

Wierzę, że nadszedł czas, aby przeformułować mój problem i być bardziej jasne. Nie chodzi o liczby całkowite ... Więc, powiedzmy, mamy dwie liczby x1 i x2. Powiedzmy, że użytkownik wprowadza numer y. Co chcę znaleźć, to numer y' blisko y, więc x1 % y' i x2 % y' są bardzo małe (mniejsze niż 0.02, na przykład, ale pozwala zadzwonić pod ten numer LIMIT). Innymi słowy, nie potrzebuję optymalnego algorytmu, ale dobre przybliżenie.

Dziękuję wszystkim za poświęcony czas i wysiłek, to naprawdę miłe!

Answer 1

Wierzę, że nie ma znanego wydajnego algorytmu (wielomianowy czas) dla tego problemu, ponieważ istnieje wielomianowa redukcja czasu z integer factorization na ten problem. Ponieważ nie ma żadnego znanego algorytmu wielomianowego dla faktoryzacji całkowitej, nie może być również znanego algortihm dla twojego problemu, ponieważ w przeciwnym razie rzeczywiście mielibyśmy algorytm wielomianowy dla faktoryzacji całkowitej.

Aby zobaczyć, jak to działa, załóżmy, że masz liczbę n, którą chcesz uwzględnić.Teraz, używając dowolnego algorytmu, znajdź wspólny współczynnik n i n najbliżej √ n. Ponieważ żaden nietrywialny dzielnik n nie może być większy niż √ n, znajduje on albo (1) największą liczbę całkowitą, która dzieli n, albo (2) liczbę 1, jeśli n jest liczbą pierwszą. Następnie możesz podzielić n przez tę liczbę i powtórzyć, aby uzyskać wszystkie czynniki n. Ponieważ n może mieć co najwyżej współczynniki O (log n), wymaga to co najwyżej wielomianu wielu iteracji solwera dla twojego problemu, więc mamy redukcję wielomianową od rozkładu całkowitoliczbowego do tego problemu. Jak wspomniano powyżej, oznacza to, że przynajmniej w literaturze otwartej nie ma znanego skutecznego klasycznego algorytmu do rozwiązania tego problemu. Ktoś może istnieć, ale byłby to naprawdę bardzo ważny wynik.

Przepraszamy za negatywną odpowiedź i mamy nadzieję, że to pomoże!

Answer 2

1. Znajdź GCD x1 i x2.
2. Jeśli GCD <= Y następnie powrócić GCD
3. Obecny najlepszą odpowiedź jest GCD, z najlepszym odległości GCD - y.
4. iterację wszystkich liczb Y +/- [0 ... najlepiej odległość]
5. Powrót pierwsza liczba całkowita, która jest wielokrotnością zarówno x1 i x2

Aby znaleźć GCD

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

Aby znaleźć najbliższy dzielnik do 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; 
} 

Uważam, że o Dodatkową dostępną optymalizacją byłby czynnik gcd (być może za pomocą sita?), jak sugeruje @trinithis.

Answer 3

myślę, że można to zrobić przez algorytm zachłanny, najpierw znaleźć NWD wspólnymi algorytmów nazwać to d (która jest obliczalna w czasie logarytmicznym), a następnie znaleźć czynniki d każdym razem dzielić d do najmniejszego dostępnego czynnika (tworzenie d') oraz porównaj |d'-y| z |d-y|, jeśli jest mniejszy, kontynuuj w ten sposób (i zamień d' na d), w przeciwnym razie pomnóż d' z najmniejszym wyeliminowanym czynnikiem i ponownie porównaj jego odległość z y.

Answer 4

Jest skuteczny jak mogę go:

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 
"""