Fattorizzazione di Fermat in C++

Question

Per divertimento, ho implementato alcune cose di matematica in C++ e ho tentato di implementare Fermats Factorisation Method, tuttavia, non so che capisco cosa dovrebbe restituire. Questa implementazione che ho, restituisce 105 per l'esempio numero 5959 indicato nell'articolo di Wikipedia.

Il pseudocodice in Wikipedia si presenta così:

Si cerca vari valori di una, sperando che è un quadrato.

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) 

mio implementazione C++, simile a questa:

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(); 
} 

Che cosa è supposto per tornare? Sembra che stia appena ritornando a + b, che non sono i fattori di 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

Si noti che si dovrebbero eseguire tutti quei calcoli su tipi di interi, non su tipi in virgola mobile. Sarebbe molto, molto più semplice (e probabilmente più corretto).

---

La tua funzione compare_doubles è errata. diff dovrebbe essere un double.

E una volta risolto, sarà necessario correggere la linea di test. compare_doubles restituirà true se i suoi input sono "quasi uguali". È necessario eseguire il ciclo mentre sono "non quasi uguali".

Quindi:

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

E:

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

E voi l'otterrà il risultato corretto (101) per questo ingresso.

Avrete anche bisogno di chiamare la funzione round con 0 come "luoghi", come vhallac sottolinea - non si dovrebbe essere arrotondati a una cifra dopo la virgola.

L'articolo di Wikipedia che colleghi ha l'equazione che ti permette di identificare b da N e a-b.

Answer 2

I due fattori sono (a + b) e (a-b). Sta restituendo uno di quelli. Puoi ottenere facilmente l'altro.

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

Answer 3

ci sono due problemi nel codice:

1. compare_doubles ritorno veri quando sono abbastanza vicini. Quindi, la condizione del ciclo while è invertita.
2. La funzione round richiede il numero di cifre dopo il punto decimale. Quindi dovresti usare round(x, 0).

Come ho suggerito, è più facile da usare int per i tipi di dati. Codice operativo Here's implementato utilizzando numeri interi.