c++ - Fermat在C++中的分解

为了好玩，我一直在用C++实现一些数学知识，并且一直在尝试实现Fermats Factorisation Method，但是，我不知道我知道应该返回什么。我有此实现，为Wikipedia文章中给出的示例编号5959返回105。

维基百科中的伪代码如下所示:

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)

我的C++实现如下所示:

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

它应该返回什么？似乎只是返回a + b，这不是5959的因素吗？

编辑

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

最佳答案

请注意，您应该对整数类型而不是浮点类型进行所有这些计算。这会简单得多(甚至可能更正确)。

您的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函数，并在vhallac指出的情况下将0称为“位置”-您不应该舍入到小数点后一位。

您链接的Wikipedia文章具有使您能够从b和N识别a-b的等式。