5

为了好玩，我一直在用 C++ 实现一些数学东西，并且我一直在尝试实现Fermats Factorisation Method，但是，我不知道我理解它应该返回什么。我有这个实现，返回105维基百科文章中给出的示例编号 5959。

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

尝试各种 a 的值，希望它是一个正方形。

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

3 回答 3

3

您的代码中有两个问题：

  1. compare_doubles当它们足够接近时返回 true。因此，while 循环条件被反转。
  2. 该round函数需要小数点后的位数。所以你应该使用round(x, 0).

正如我所建议的，它更容易int用于您的数据类型。这是使用整数实现的工作代码。

于 2012-05-06T21:18:29.213 回答
3

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

你的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此输入的正确结果 ( )。

正如vhallac指出的那样，您还需要使用“位置”来调用您的round函数- 您不应该四舍五入到小数点后的一位数。0

您链接的维基百科文章具有允许您b从N和识别的等式a-b。

于 2012-05-06T21:18:37.143 回答
2

这两个因素是（a+b）和（ab）。它正在返回其中之一。你可以很容易地得到另一个。

N = (a+b)*(a-b)
a-b = N/(a+b)
于 2012-05-06T20:57:32.613 回答