Fermat's factorization w C++

Question

Dla zabawy, wprowadzałem trochę matematyki w C++, a ja próbowałem implementować Fermats Factorisation Method, jednak nie wiem, że rozumiem, co ma powrócić. Ta implementacja, którą mam, zwraca 105 dla numeru przykładu 5959 podanego w artykule w Wikipedii.

pseudokod w Wikipedia wygląda następująco:

próbuje różnych wartości a, mając nadzieję, że jest kwadratem.

FermatFactor(N): // N should be odd 
    a → ceil(sqrt(N)) 
    b2 → a*a - N 
    while b2 isn't a square: 
     a → a + 1 // equivalently: b2 → b2 + 2*a + 1 
     b2 → a*a - N //    a → a + 1 
    endwhile 
    return a - sqrt(b2) // or a + sqrt(b2) 

Moja implementacja C++ wyglądać następująco:

int FermatFactor(int oddNumber) 
{ 
    double a = ceil(sqrt(static_cast<double>(oddNumber))); 
    double b2 = a*a - oddNumber; 
    std::cout << "B2: " << b2 << "a: " << a << std::endl; 

    double tmp = sqrt(b2); 
    tmp = round(tmp,1); 
    while (compare_doubles(tmp*tmp, b2)) //does this line look correct? 
    { 
     a = a + 1; 
     b2 = a*a - oddNumber; 
     std::cout << "B2: " << b2 << "a: " << a << std::endl; 
     tmp = sqrt(b2); 
     tmp = round(tmp,1); 
    } 

    return static_cast<int>(a + sqrt(b2)); 
} 

bool compare_doubles(double a, double b) 
{ 
    int diff = std::fabs(a - b); 
    return diff < std::numeric_limits<double>::epsilon(); 
} 

Co to ma wrócić? Wydaje się, że właśnie wracasz a + b, co nie jest czynnikiem 5959?

EDIT

double cint(double x){ 
    double tmp = 0.0; 
    if (modf(x,&tmp)>=.5) 
     return x>=0?ceil(x):floor(x); 
    else 
     return x<0?ceil(x):floor(x); 
} 

double round(double r,unsigned places){ 
    double off=pow(10,static_cast<double>(places)); 
    return cint(r*off)/off; 
} 

Answer 1

Należy zauważyć, że należy wykonywać te wszystkie obliczenia na liczbach całkowitych, a nie na typach zmiennoprzecinkowych. Byłoby znacznie, znacznie prostsze (i prawdopodobnie bardziej poprawne).

---

Twoja funkcja compare_doubles jest nieprawidłowa. diff powinien być double.

A kiedy to naprawisz, musisz naprawić swoją linię testową. compare_doubles zwróci true, jeśli jego wejścia będą "prawie równe". Musisz zapętlić, dopóki nie są "prawie równe".

Więc:

bool compare_doubles(double a, double b) 
{ 
    double diff = std::fabs(a - b); 
    return diff < std::numeric_limits<double>::epsilon(); 
} 

I:

while (!compare_doubles(tmp*tmp, b2)) // now it is 
{ 

I będzie Ci poprawny wynik (101) do tego wejścia.

Musisz również zadzwonić pod numer round z 0 jako "miejsca", jak vhallac wskazuje - nie powinieneś zaokrąglać do jednej cyfry po przecinku dziesiętnym.

Link do artykułu w Wikipedii ma równanie, które umożliwia identyfikację b z N i a-b.

Answer 2

dwa czynniki są (a + b) i (a-b). Zwraca jeden z nich. Możesz łatwo zdobyć drugą.

N = (a+b)*(a-b) 
a-b = N/(a+b) 

Answer 3

Istnieją dwa problemy w kodzie:

1. compare_doubles return true, gdy są one wystarczająco blisko. Tak więc warunek pętli while jest odwrócony.
2. Funkcja round wymaga liczby cyfr po przecinku dziesiętnym. Więc powinieneś użyć round(x, 0).

Jak zasugerowałem, łatwiej jest używać int dla swoich typów danych. Here's działający kod zaimplementowany przy użyciu liczb całkowitych.