Fermatic factorization in C ++

For fun, I implemented some mathematical things in C ++, and I tried to implement the Fomats Factorization Method , however, I don’t know that I understand what it should return. In this implementation, I returned 105for example the number 5959 given in the Wikipedia article.

The Wikipedia pseudocode is as follows:

You can try different values ​​of a, hoping that it is a square.

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)

My C ++ implementation is as follows:

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

What should he return? It seems to be just returning a + bwhat are not factors 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;
}
+5
source share
3 answers

, , . , (, , ).


compare_doubles . diff double.

, . compare_doubles true, " ". , " ".

:

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

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

(101) .

round 0 "", vhallac - .

Wikipedia, , , b N a-b.

+3

:

  • compare_doubles return true, . , while .
  • round . round(x, 0).

, int . , .

+3

Two factors: (a + b) and (ab). He returns one of them. You can easily find another.

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

All Articles