Factorización de Fermat en C++

Question

Por diversión, he estado implementando algunas cosas de matemáticas en C++, y he estado intentando implementar Fermats Factorisation Method, sin embargo, no sé si entiendo lo que se supone que debe devolver. Esta implementación que tengo, devuelve 105 para el número de ejemplo 5959 dado en el artículo de Wikipedia.

El pseudocódigo en Wikipedia se parece a esto:

Uno trata de varios valores de a, la esperanza de que es un cuadrado.

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) 

Mi C++ aplicación, el siguiente aspecto:

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

¿Qué se supone para volver? Parece que solo está devolviendo a + b, que no son los factores de 5959?

EDITAR

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

Tenga en cuenta que debe hacer todos esos cálculos en tipos enteros, no en los tipos de coma flotante. Sería mucho, mucho más simple (y posiblemente más correcto).

---

Su función compare_doubles es incorrecta. diff debe ser un double.

Y una vez que lo solucione, necesitará reparar su línea de prueba. compare_doubles devolverá verdadero si sus entradas son "casi iguales". Debe realizar un bucle mientras "no son casi iguales".

Así:

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

Y:

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

Y se obtendrá el resultado correcto (101) para esta entrada.

También tendrá que llamar a su función round con 0 como "lugares" como vhallac señala - que no se debe redondear a un dígito después del punto decimal.

El artículo de Wikipedia que vincula tiene la ecuación que le permite identificar b de N y a-b.

Answer 2

Los dos factores son: (a + b) y (a-b). Está volviendo uno de esos. Puedes obtener el otro fácilmente.

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

Answer 3

Hay dos problemas en su código:

1. compare_doubles retorno verdaderos cuando están lo suficientemente cerca. Por lo tanto, la condición while loop está invertida.
2. La función round requiere una cantidad de dígitos después del punto decimal. Entonces debería usar round(x, 0).

Como he sugerido, es más fácil usar int para sus tipos de datos. Here's código de trabajo implementado usando enteros.